阿凡,阿凡四,阿凡,阿凡,发,地方,School of Business,ECUST,阿凡,阿凡四,阿凡,阿凡,发,地方,*,第,16,讲 排队论,I,School of Business,ECUST,本讲提纲,1.,概述,2.,排队系统的基本要素,3.,输入过程与服务过程的描述,4.,排队系统的符号表示,肯德尔记号,5.,排队系统的主要数量指标,School of Business,ECUST,1.,概述,排队是我们在日常生活中经常遇到的现象。有些排队是有形的，如车站上等待买票的旅客，在超市收银台等待结帐的顾客；有些排队是无形，如电话交换机接到的电话呼叫。,School of Business,ECUST,如果服务设施过少或服务效率太低，便会加剧拥挤，排队成龙。但增加服务设施便会增加服务成本或造成系统空闲，而有些服务设施如机场、港口泊位等一旦建成就不易改动。因此，有必要对排队系统的结构和运行规律加以研究，为排队系统的设计和调控提供依据。,排队论，又称随机服务系统理论，是研究系统拥挤现象和排队现象一门学科，具体旨在决定服务设施最佳设计。排队论的研究将有助于在服务机构的设施和顾客的等待服务时间之间取得平衡，从而使高质量低成本的服务和管理得以实现。,School of Business,ECUST,服务系统由服务设施和服务对象,(,统称顾客,),构成,School of Business,ECUST,2.,排队系统的基本要素,排队系统,School of Business,ECUST,一般的排队系统都有三个组成部分：,（,1,）输入过程,（,2,）排队规则,（,3,）服务机构,(,服务台,),School of Business,ECUST,(2),排队规则,排队规则指顾客是否进入队列，队列的结构以及顾客接受服务的先后次序。,顾客是否进入队列：分为损失制、等待制以及混合制等情况：,损失制：也称即时制，顾客到达时，如果所有的服务台都被占用，顾客随即离去，不再接受服务。,等待制：顾客到达时，如果所有的服务台都被占用，顾客排队等待服务。,混合制：混合制实际上是一种有限等待制，通常有下面两种形式：,队长有限制：由于空间的限制，有的系统要规定容量，当排队等待的顾客人数超过规定容量时，后来到达的顾客自动离去。,排队等待时间有限制：顾客因某种原因，在队列中等待服务的时间有限，如果等待时间过长，顾客就离队而去。,School of Business,ECUST,队列的结构：单列,/,多列,服务,台,服务,台,School of Business,ECUST,(3),服务机构,服务机构一般有以下几个特征参数：服务台的数量,(,单服务台,or,多服务台,),；若是多服务台，是串联还是并联；服务方式,(,对顾客是逐个服务还是成批服务,),；服务时间的描述。,School of Business,ECUST,服务方式：,指在某一时刻接受服务的顾客数，是单个服务还是成批服务。我们主要讨论一个服务台一次只能服务一个顾客的情形。,服务时间的描述：,当一个顾客接受服务时，从服务开始到结束这个时段长度称为服务时间,(service time),。,服务时间是固定的，还是随机的？如果是随机的，服从什么分布？,School of Business,ECUST,3.,输入过程与服务过程的描述,为了研究一个排队系统，需刻画顾客进入排队系统的过程和顾客接受服务,(,离开,),的过程，考虑顾客逐个进入系统，并且逐个接受服务的情形，关键问题是如何描述,两个相继顾客到达系统的时间间隔,，以及,顾客接受服务的时间,。,School of Business,ECUST,性质,1,：如果顾客以泊松流到达系统，则在长度为,t,的时间区间内到达系统的顾客数量,X,服从泊松分布,:,若,t,=1,，单位时间内到达系统的顾客数量,X,的分布：,单位时间平均到达的顾客数,(,顾客平均到达率或强度,),；,泊松流与泊松分布,School of Business,ECUST,泊松流与负指数分布,性质,2,：如果顾客的到达过程是泊松流,(,强度为,),，则顾客相继到达的间隔时间,T,服从参数为,的,负指数分布。其概率密度和分布函数分别为：,两个顾客相继到达的平均间隔时间,School of Business,ECUST,服务过程的描述,顾客接受服务时间的分布,设服务台对顾客的服务时间为,Ts,在排队论中用来描述,Ts,的常见分布有：,(1),定长分布,(D):,每个顾客接受服务的时间是一个确定的常数。,(2),负指数分布,(M):,每个顾客接受服务时间相互独立，服从参数为 的负指数分布：,E,T,s=1/,;Var,T,s=1/,2,1/,：,每个顾客的平均(期望)服务时间；,:,单位时间服务的平均顾客数，平均(期望)服务率,(,离去率,),；,School of Business,ECUST,(3),k,阶爱尔朗,(Erlang),分布,设顾客在系统内所接受的服务可以分为,k,个阶段，每个阶段的服务时间,T1,T2,.,Tk,相互独立，且,服从相同参数1/,k,的负指数分布，则顾客在系统内接受服务的时间之和,T=T1+T2+.+Tk,服从,k,阶爱尔朗分布,:,E,T,=1/,;Var,T,=1/(,k,2,),School of Business,ECUST,m,=,1,k,=,1,k,=,2,k,=,4,k,=,8,当,k,=1,Erlang,分布即为负指数分布；当,k,增大时，,Erlang,分布逐渐变成对称的；当,k=30,，,Erlang,分布,近似于正态分布,当,k,趋向无穷大时，,Var(T)=0,Erlang,分布变为定长分布。,School of Business,ECUST,后来，在1971,年关于排队论符号标准化的会议上决,定，将,Kendall,符号扩充为：,X/Y/Z/A/B/C,其中前三项意义不变,，,后三项的意义为：,A,处填写系统容量限制;,B,处填写顾客源中的顾客数目;,C,处填写服务规则,(,如先到先服务,FCFS，,后到先服务,LCFS)。,约定，如略去后三项，即指,X/Y/Z/FCFS,的情形。,后面我们只讨论,FCFS,的情形，所以略去第六项,.,School of Business,ECUST,(1),负指数分布,M,(2)k,阶爱尔朗分布,E,k,(3),确定型分布,(,定长分布,),D,(4),一般相互独立的到达时间间隔分布,GI,(5),一般(,General),分布,G,School of Business,ECUST,5.,排队系统的性状指标,对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。,下面介绍几种常用的数量指标：,School of Business,ECUST,3),逗留时间,：,一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间，它的期望值记作,W,4),等待时间,：一个顾客在系统中排队等待的时间称为等待时间，它的期望值记作,Wq,逗留时间等待时间服务时间,School of Business,ECUST,5),忙期：忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，服务机构连续忙的时间。,6),闲期：闲期是服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现。,