第五部分排队论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五部分 排队论,特征:,有请求服务的人或物，我们统称它们为“顾客”。,有为顾客服务的人或物，我们叫它们为“服务员”或“服务台”。服务系统是由顾客和服务员组成的。,顾客在随机的时刻，一个（批）一个（批）地来到服务系统。每位顾客需要的服务时间不一定是确定的。服务过程的随机性造成某个阶段顾客排队长，而某些时候服务员又闲聊无事。,研究内容,:,性态问题。研究各种排队系统的概率规律性。主要是研究队长分布，等待时间分布和忙期分布等，包括瞬态和稳态两种情形。,最优化问题。最优化又分静态最优和动态最优，前者指最优设计；后者指现有排队系统的最优运营。,排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。,第十三章,排队论的基本知识,1,排队系统的组成,顾客源,顾客到达,按一定排队规则形成的等待线,服务规则,服务机构,顾客,离去,排队系统,图13-1 排队系统,输入过程,顾客源的组成，可能是有限的，如工厂待修理的机器；可能是无限，如某一商店的顾客流可以看成是无限的。,顾客到达的方式，可能是单个到达，也可能是成批到达。例如，到餐厅就餐就有单个到达的顾客和受邀请来参加宴会的成批顾客。,顾客相继到达的间隔时间,T,可以是确定的，即定长输入，每隔一段固定时间到达一个顾客。在排队论中主要讨论的输入过程是随机型的。,顾客到达可以是相互独立的，即在某一时刻以前顾客的到达情况，不影响该时刻后顾客的到达，否则就是有关联的。,输入过程可以是平稳的，或称对时间齐次的。是指描述相继到达的间隔分布和所含参数（如期望值，方差等）都是与时间无关的。否则称为非平稳。对非平稳的过程数学处理很复杂。,排队规则,服务系统的分类,损失制,：即顾客到达此服务系统时，若服务员都不空闲，则顾客离去，另求服务。,等待制,：顾客到达本系统时，服务员都在为先到的顾客服务（即不空），则顾客排队等待服务，一直等到有空的服务员为他服务为止。,混合制,：在现实生活中，很多服务系统介于损失制和等待制之间，称为混合制系统。,当顾客到达时，服务员不空，且排队位置满座，顾客离去，这是排队长度有限的服务系统；,混合制的另一种情形，是顾客到达时，服务员不空，它就排队等待服务，当顾客等了一段时间后，仍轮不到为他服务，顾客离开排队队列，另求服务。这叫排队时间有限的服务系统。,服务规则,先到先服务,后到先服务,随机服务,有优先权的服务,队列的数目,单队列,多队列,服务机构,服务员的个数及结构,单个服务台、单队列,输入,队列,服务台,输出,多个服务台并列、单队列（多队列）,输入,队列,台1,台2,台,K,单队：,多队：,输入,队列,台,台,队列,多服务台串列,输入,队列,输出,多服务台混合,输入,队列,服务方式,对单个顾客进行,对成批顾客进行,对顾客的服务时间,确定型,随机型,2,排队模型的符号表示,特征中最主要、影响最大的因素：,顾客相继到达的间隔时间,服务时间的概率分布,服务员的个数,系统内顾客的容量，即排队系统内的顾客数,古典的排队模型：,A/B/n/m,A,表示顾客相继到达间隔时间的分布,B,表示服务时间的概率分布,n,表示服务员的数目,m,表示顾客排队允许的长度或系统内顾客的容量，,0,m,+,表示相继到达间隔时间和服务时间的各种分布的符号是：,M,负指数分布（,M,是,Markov,的字头，因为负指分布具有无记忆性，即,Markov,性）。,D,确定型（,Deterministic,）,E,k,K,阶爱尔朗Erlang,）,分布。,GI,一般相互独立（,General Independent,）,的随机分布。,G,一般（,General,）,随机分布。,3,服务系统的这行指标,单位时间内到达的顾客数约的期望值，记作,，,即为单位时间内的平均到达率。,单位时间内服务的顾客数的期望值，记作,，,即为单位时间内的平均服务率。,系统内的顾客数叫队长，其期望值记作,L,s,（,Length System,）。,或叫平均队长。,系统内排队等待的顾客数，叫队列长，它的期望值记作,L,q,（,Length Queue,）,或叫平均队列长。,顾客在系统逗留时间的期望值，记作,Ws,或算平均逗留时间。,顾客在系统中排队等待时间的期望值，记作,W,q,或算平均等待时间。由此看到顾客的平均逗留时间等于平均等待时间加上平均服务时间，即：,Ws=,W,q,+,平均服务时间,忙期（,Busy Period,）：,服务员在二次空闲之间连续工作的时间长度，它的期望值记作 （忙期的平均长度）。,闲期（,Idle Period,）：,服务员在二次工作之间连续空闲的时间长度，它的期望值记作 （闲期的平均长度）,L,s,、,L,q,、,W,s,、,W,q,是,顾客所关心的数量指标，而最关心的是等待时间,W,q,希望不太长。,L,s,、,L,q,同时也为系统的设计者设计排队场地提供依据。,是服务员关心的指标，它关系到服务员的工作强度，同时忙期及一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标。,4,排队系统的常见分布,泊松（,Poisson,）,分布,泊松流又叫简单流，它具有如下性质：,平稳性,在时间轴,ot,上，任意给定一个时间,t0,，,在（,t+,t,）,时间内，到达,k,个顾客的概率与起始时刻,t,无关，而只与,t,和,k,的大小有关。记此概率为：,无后效性,在时间轴,ot,上，互不相交的时间区段,t1,、,t2,内，到达的顾客数是相互独立的。换句话说，每个顾客来到系统的时刻互不相关。,普通性,即在充分小的间隔时间,t,内，有两个或两个以上顾客来到系统的概率（,t,）,极小，以改可以忽略不计。即：普通性表示在单位时间内顾客是一个一个地到达系统，而不是成批到达。,有限性,即在任意有限的时间区间内，到达有限个顾客的概率为,1,。即：,同时具备以上四个性质的流，称做最简单流。,负指数分布,当输入过程是泊松流时，我们研究两顾客相继到达的间隔时间,T,（,也是随机变量）的概率分布。,定理,若顾客到达形成参数为,的泊松流，则两顾客相继到达的间隔时间,T,服从参数为,的负指数分布。即,T,的分布函数：,（,t,0,）,分布密度：,（,t,0,）,表示单位时间内平均到达的顾客数，故1/,就表示相继顾客到达的平均间隔时间。,服务时间,v,的分布。对一个顾客的服务时间也就是在忙期中相继离开系统的两顾客的间隔时间。,表示单位时间能被服务完的顾客数（期望值），称为平均服务率。1/,表示一个顾客的平均服务时间。,服务强度,，,我们知道，,为平均到达率；,为平均服务率。,有着重要的意义：,1,，,说明单位时间内顾客来到系统的平均数,，,大于单位时间内顾客平均服务数,。,所以，,1,的等待制系统一般不属地讨论之到。,=1,，,即,=,。,这时系统服务率为,100%,；或者说，当一个顾客正在接受服务的时候，平均也只有一个顾客来到系统。,在等待制系统中我们讨论的有关运行指标主要是在,1,的情况。,第十四章,排队系统的分析,对随机型排队系统，在给定的输入和服务的条件，我们主要是研究系统的运行指标：,系统中的顾客数（即队长）的期望值,L,s,；,在系统内排队等待的顾客数（即队列长）的期望值,L,q,；,顾客在系统内逗留时间的期望值,W,s,；,顾客在系统内排队等待时间的期望值,W,q,。,而计算上述数量指标的基础是系统的状态概率,P,n,（,t,），,即：,P,n,（,t,）,=P,任一时刻,t,，,系统的状态,=,n,所谓系统的状态即为系统中的顾客数。,显然，在单服务台的情形下：,状态,n,1,，,即为繁忙。,状态,n=0,，,即为空闲。,若繁忙的概率大，则,L,s,、,L,q,、,W,s,、,W,q,一般较大，反之则较小。,1,单服务台的,M/M/1,模型,M/M/1,模型即指输入过程服从泊松流，即顾客相继到达间隔时间服从负指数分布，服务时间从负指数分布，单服务台的情况。,若用符号表示，则为：,M/M/1/,/,M/M/1,/N,M/M/1/m/N,（,m,N,）,其符号含义：,M/M/1/,顾客源顾客总数,/,最大队长,M/M/1/,模型,M/M/1/,/,，,又称为标准的,M/M/1,模型，是符合下列条件的排队系统：,输入过程：,顾客源是无限的，顾客单个到来，相互独立，顾客相继到达的间隔时间服从参数为,的负指数分布。,排队规则：,单队，且队长没有限制，先到先服务。,服务机构：,单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。,系统的状态概率：,n,0,（,3,）,有：,系统的繁忙（,Busy,）,与空闲（,Idle,）,（,1,）系统处在空闲状态的概率：,系统处在繁忙状态即系统处于忙期的概率：,（,2,）在繁忙状态条件下,队列中顾客平均数,顾客平均等待时间：,忙期（,Pmry,Period,）：,指服务台由空闲状态因顾客到来而开始忙碌到再度空闲为止的时间长度。,和闲期（,Idle Period,）：,闲期指由原有的顾客都被服务完了的时刻开始到下一个顾客到来为止的时间长度。,各忙期的平均长度为：,一个忙期所服务的顾客平均数为：,二、,M/M/1/N,模型,由于系统中排队等待的顾客数最多为,N-1,，,在某一时刻一顾客到达时，如果系统中已有,N,个顾客，那么该顾客就被拒绝进行系统。,N=1,时，为损失制系统；,N,时，为等待制系统，即,M/M/1/,情形；1,N,时，为混合制系统。这里讨论后一种情形，即,N,为有限数的情形。,1,系统的状态概率：,1,n,N,2,系统的主要运行指标,1,（,系统中的平均顾客数）,（在队列中等待的平均顾客数）,（,3,）单位时间内损失顾客的平均数,P,N,，,因为损失率为,P,N,。,（,4,）有效到达率,e,，,因为平均到达率,是指系统中顾客数不以,N,（,即系统有空）时的平均到达率，当系统已满即,n=N,，,则到达率为,0,，故要求出有效到达到,e,。,（顾客逗留时间的期望值）,（顾客等待时间的期望值）,它们之间的关系：,例：单人理发馆有六个椅子接待人们排队等待理发，当,6,个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率,3,人,/,小时，理发需时平均,15,分钟。则,N=7,为系统中最大的顾客数，,=3,人,/,小时，,=4,人,/,小时,解：（,1,）求某顾客一到达就能理发的概率。,这种情形相当于理发馆内没有顾客，所求概率：,（,2,）求需要等待的顾客数的期望值。,L,q,=L,s,-(1-P,0,)=2.11-(1-0.2778)=1.39,（,3,）求有效到达率,e,=（1-P,0,）=4（1-0.2778）=2.89,人/小时,（,4,）求一顾客在理发馆内逗留的期望时间,Ws=Ls/,e=2.11/2.89=0.73,小时,=43.8,分钟,（,5,）在可能到来的顾客中有百分之几不等待离开？,这就是求系统中有,7,个顾客的概率：,这也是理发馆的损失率。,