排队论和案例分析专业知识讲座.ppt

文档来源于网络，文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,内容提要,1,排队服务系统的基本概念,2,等待制排队模型,3,损失制排队模型,4,混合制排队模型,5,闭合式排队模型,6,排队系统的最优化模型,1,排队服务系统的基本概念,排队论,(,Queueing Theory,),又称随机服务系统,是通过研究,各种服务系统等待现象中的概率特征，从而解决服务系,统最优设计与最优控制的一种理论,.,1.1,排队的例子,及基本概念,某维修中心在周末现只安排一名员工为顾客提供服务。新来,维修的顾客到达后，若已有顾客正在接受服务，则需要排队,等待。若排队的人数过多，势必会造成顾客抱怨，会影响到,公司产品的销售；若维修人员多，会增加维修中心的支出，,如何调整两者的关系，使得系统达到最优,.,例,1,排队的例子,它是一个典型的排队的例子,关于排队的例子有很多,例如：,上下班坐公共汽车,等待公共汽车的排队,;,顾客到商店购物形,成的排队,;,病人到医院看病形成的排队,;,售票处购票形成的排,队等,;,另一种排队是物的排队，例如文件等待打印或发送,;,路,口红灯下面的汽车、自行车通过十字路口等等,.,排队现象是由两个方面构成，一方要求得到服务，另一方设,法给予服务。我们把要求得到服务的人或物（设备）统称为,顾客,给予服务的服务人员或服务机构统称为服务员或服务,台。顾客与服务台就构成一个排队系统，或称为随机服务系,统。显然缺少顾客或服务台任何一方都不会形成排队系统,.,对于任何一个排队服务系统，每一名顾客通过排队服务系统,总要经过如下过程：顾客到达、排队等待、接受服务和离,去，其过程如下图所示,:,顾客总体,队 伍,输出,输入,服务台,服务系统,输入过程,顾客源总体：顾客的来源可能是有限的，也可,能是无限的,1.2,排队服务系统的基本概念,到达的类型：顾客是单个到达，或是成批到达,相继顾客到达的间隔时间：通常假定是相互独,立、同分布的，有的是等距间隔时间，有的是,服从Poisson分布，有的是服从k阶Erlang分布,输入过程是描述顾客来源及顾客是按怎样的规律抵达排队系统,排队规则,损失制排队系统：顾客到达时,若所有服务台均被占,服务机,构又不允许顾客等待,此时该顾客就自动,离去,1.2,排队服务系统的基本概念,等待制排队系统：顾客到达时若所有服务台均被占，他们,就排队等待服务。在等待制系统中,服务,顺序又分为：先到先服务,即顾客按到达,的先后顺序接受服务；后到先服务,.,混合制排队系统：损失制与等待制的混合，分为队长,(,容量,),有限的混合制系统，等待时间有限的混,合制系统，以及逗留时间有限制的混合,系统,.,排队规则是指服务允许不允许排队，顾客是否愿意排队,服务机构,服务台的数目,:,在多个服务台的情形下，是串,联或是并联；,1.2,排队服务系统的基本概念,顾客所需的服务时间服从什么样的概率分布，,每个顾客所需的服务时间是否相互独立，是成,批服务或是单个服务等。常见顾客的服务时间,分布有：定长分布、负指数分布、超指数分,布、k阶Erlang分布、几何分布、一般分布等,.,1.3,符号表示,排队论模型的记号是,20,世纪,50,年代初由,D.G.Kendall(,肯,达尔,),引入的，通常由,3,5,个英文字母组成，其形式为,其中,A,表示输入过程，,B,表示服务时间，,C,表示服务台数目，,n,表示系统空间数。例如,:,M/M/S/,表示输入过程是,Poisson,流,服务时间服从负,指数分布,系统有,S,个服务台平行服务,系统容量为无穷的,等待制排队系统,.,(2),M/G/1/,表示输入过程是,Poisson,流，顾客所需的服务,时间为独立、服从一般概率分布，系统中只有一个服务,台，容量为无穷的等待制系统,.,GI/M/1/,表示输入过程为顾客独立到达且相继到达的间,隔时间服从一般概率分布，服务时间是相互独立、服从负指,数分布，系统中只有一个服务台，容量为无穷的等待制系统,1.3,符号表示,(4),E,k,/G/1/K,表示相继到达的间隔时间独立、服从,k,阶,Erlang,分布，服务时间为独立、服从一般概率分布，系统中只有一,个服务台，容量为,K,的混合制系统,.,(5),D/M/S/K,表示相继到达的间隔时间独立、服从定长分布、,服务时间相互独立、服从负指数分布，系统中有,S,个服务台,平行服务，容量为,K,的混合制系统,.,1.4,描述排队系统的主要数量指标,队长与等待队长,队长,(,通常记为,L,S,),是指在系统中的顾客的平均数,(,包括正在接受服务的顾客,),而等待队长,(,通常记为,L,q,),是指系统中排队等待的顾客的平均数，它们是顾客和服务机构双方都十分关心的数量指标。显然队长等于等待队长加上正在被服务的顾客数,.,顾客的平均等待时间与平均逗留时间,顾客的平均等待时间,(,通常记为,W,q,),是指从顾客进入系,统的时刻起直到开始接受服务止的平均时间。平均逗,留时间,(,通常记为,W,s,),是指顾客在系统中的平均等待时,间与平均服务时间之和。平均等待时间与平均服务时,间是顾客最关心的数量指标,.,1.4,描述排队系统的主要数量指标,系统的忙期与闲期,从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务机构的工作强度，是衡量服务机构利用效率的指标，即,与忙期对应的是系统的闲期，即系统连续保持空闲的时,间长度,.,服务机构,工作强度,用于服务顾客的时间,服务设施总的服务时间,1.5 Little,（利特尔）公式,用,表示单位时间内顾客到达的平均数,表示单位时间内,被服务完毕离去的平均顾客数，因此,1/,表示相邻两顾客到,达的平均时间，,1/,表示对每个顾客的平均服务时间,.,J.D.C.Little,给出了如下公式：,1.6,与排队论模型有关的,LINGO,函数,(1)peb(load,S),该函数的返回值是当到达负荷为,load,服务系统中有,S,个服务,器且允许排队时系统繁忙的概率,也就是顾客等待的概率,.,(2)pel(load,S),该函数的返回值是当到达负荷为,load,服务系统中有,S,个服务,器且不允许排队时系统损失概率,也就是顾客得不到服务离,开的概率,.,(3)pfs(load,S,K),该函数的返回值是当到达负荷为,load,顾客数为,K,平行服务,器数量为,S,时,有限源的,Poisson,服务系统等待或返修顾客数,的期望值,.,2,等待制排队模型,等待制排队模型中最常见的模型是,即顾客到达系统的相继到达时间间隔独立，且服从参数,为,的负指数分布,(,即输入过程为Poisson过程,),服务台,的服务时间也独立同分布,且服从参数为,的负指数分,布，而且系统空间无限，允许永远排队,.,2,.,1,等待制排队模型的基本参数,(1),顾客等待的概率,P,wait,其中,S,是服务台或服务员的个数，,load,是系统到达负荷，,即,load=,/,=R*T,式中,R,表示,T,表示,1/,R,表示,因此，在下面的程序中，,R,或,是顾客的平均到达率，,是顾客的平均被服务数，,T,就是平均服务时间,.,2,.,1,等待制排队模型的基本参数,(2),顾客的平均等待时间W,q,其中,T/(S-load),是一个重要指标，可以看成一个“合理的,长度间隔”。注意，当,loadS,时，此值趋于无穷。也就,是说，系统负荷接近服务器的个数时，顾客平均等待时,间将趋于无穷,.,当,load S,时,上式,W,q,无意义。其直观的解释是：当系统,负荷超过服务器的个数时,排队系统达不到稳定的状态,其队将越排越长,.,2,.,1,等待制排队模型的基本参数,顾客的平均逗留时间W,s,、队长L,s,和等待队长L,q,这三个值可由,Little,公式直接得到,2.2,等待制排队模型的计算实例,S=1,的情况,(,M/M/1/,),即只有一个服务台或一名服务员服务的情况,.,例,2,某维修中心在周末现只安排一名员工为顾客提供服,务。新来维修的顾客到达后，若已有顾客正在接受服务，,则需要排队等待。假设来维修的顾客到达过程为Poisson,流，平均4人/小时，维修时间服从负指数分布，平均需要,6分钟。试求该系统的主要数量指标。,解,按照式,上面分析,编写LINGO程序，其中R=4,T=6/60,load=R,.,T,S=1.程序名,:,exam1002.lg4,.,2.2,等待制排队模型的计算实例,由此得到：,(1),系统平均队长,L,s,=0.6666667,(2),系统平均等待队长,L,q,=0.2666667,(3),顾客平均逗留时间,W,s,=0.1666667(,小时,)=10(,分钟,),(4),顾客平均等待时间,W,q,=0.06666667(,小时,)=4(,分钟,),(5),系统繁忙概率,P,wait,=0.4,在商业中心处设置一台ATM机，假设来取钱的顾客平均每,分钟0.6个，而每个顾客的平均取钱的时间为1.25分钟，试,求该ATM机的主要数量指标,.,解,只需将上例LINGO程序作如下改动：R=0.6,T=1.25,即,可得到,结果,.,程序名,:,exam100,3,.lg4,.,计算结果见运行,例,3,即平均队长为,3,人，平均等待队长为,2.25,人，顾客平均逗留时间,5,分钟，顾客平均等待时间为,3.75,分钟，系统繁忙概率为,0.75.,S1,的情况,(,M/M/S/,),表示有多个服务台或多名服务员服务的情况,例,设打印室有,3,名打字员,平均每个文件的打印时间为,10,分钟，而文件的到达率为每小时,15,件，试求该打印室的主要数量指标,.,解,按照,上面分析,编写LINGO程序,程名,:,exam100,4,.lg4,.,计算结果分析,：即在打字室内现有的平均文件数为,6.011,件，等待打印平均文件数,3.511,件，每份文件在打字室平均停留时间为,0.400,小时（,24,分钟），排队等待打印的平均时间,0.234,小时,(14,分钟,),打印室不空闲的概率,0.702.,某售票点有两个售票窗口，顾客按参数,=8,人,/,分钟的,Poisson,流到达，每个窗口的售票时间均服从参数,=5,人,/,分钟的负指数分布，试比较以下两种排队方案的运行指标,.,(1),顾客到达后,以,1/,2的概率站成两个队列，如,右,图所示,：,例,5,(2),顾客到达后排成一个队列,顾客发现哪个窗口空时,他就,接受该窗口的服务，如,下,图所示,:,解,(1)实质上是两个独立的,M/M/1/,系统,其参数S=1,R=,1,=,2,=4,T=,1/,=,1/5=0.2,编写,其LINGO程序,，,程序,名,:,exam1005a.lg4,.,计算结果见运行,例,5,(,2,),是两个并联系统,其参数S=2,R,=,=8,T=,1/,=,1/5=0.2,编写,其LINGO程序,程序名,:,exam1005,b,.lg4,.,计算结果见运行,两种系统的计算结果,从上表中所列的计算结果可以看出,在服务台的各种性能指,标不变的情况下,采用不同的排队方式,其结果是不同的,.,从,表得到,采用多队列排队系统的队长为,4,而采用单排队系统,总队长为,4.444,也就是说每一个子队的队长为,2.222,几乎是,多列队排队系统的,1/2,效率几乎提高了一倍,.,例,5,比较分析,3,损失制排队模型,损失制排队模型通常记为,当,S,个服务器被占用后，顾客自动离去。其模型的基本,参数与等待制排队模型有些不同,我们关心如下指标：,(1),系统损失的概率,其中,load,是系统到达负荷,S,是服务台或服务员的个数,.,3,.,1,损失制排队模型的基本参数,(2),单位时间内平均进入系统的顾客数,(,e,或,R,e,),(3),系统的相对通过能力Q与绝对通过能力A,(4),系统在单位时间内占用服务台,(,或服务员,),的均值,L,s,注意,:,在损失制排队系统中,L,q,=0,即等待队长为,0.,(5),系统服务台（或服务员）的效率,(6),顾客在系统内平均逗留时间,(,由于W,q,=0,即为W,s,）,注意,:,在损失制排队系统中,W,q,=0,即等待时间为,0.,在上述公式中,引入,e,(,或,R,e,),是十分重要的,因为尽管,顾客的以平均,(,或,R),的速率到达服务系统,但当系统,被占满后,有一部分顾客会自动离去,因此,真正进入系,统的顾客输入率是,e,它小于,.,3.2,损失制排队模型的计算实例,S=1,的情况,(,M/M/1/1,),例,6,设某条电话线，平均每分钟有,0.6,次呼唤，若每次通话时间平均为,1.25,分钟，求系统相应的参数指标。,解,按照,上面分析,编写LINGO程序，其中,S=1,R=,=0.6,T=,1/,=1.25,程序名,:,exam100,6,.lg4,，结果见运行,系统的顾客损失率为,43%,即,43%,的电话没有接通,有,57%,的电话得到了服务,通话率为平均每分钟有,0.195,次,系统的,服务效率为,43%.,对于一个服务台的损失制系统,系统的服,务效率等于系统的顾客损失率,这一点在理论上也是正确的,.,S1,的情况,(,M/M/S/S,),例,7,某单位电话交换台有一台,200,门内线的总机，已知在上班,8,小时的时间内，有,20%,的内线分机平均每,40,分钟要一次外线电话，,80%,的分机平均隔,120,分钟要一次外线。又知外线打入内线的电话平均每分钟,1,次,.,假设与外线通话的时间为平均,3,分钟,并且上述时间均服从负指数分布,如果要求电话的通话率为,95%,问该交换台应设置多少条外线？,解,(1),电话交换台的服务分成两类,第一类内线打外线,其强度为,:,第二类是外线打内线，其强度为,2,=1*60=60.,因此，总强度为,=,1,+,2,=140+60=200.,(2),这是损失制服务系统,按题目要求,系统损失的概率不能超过,5%,即,(3),外线是整数，在满足条件下，条数越少越好。由上述三条，写出相应的LINGO程序，,程序名：exam1007a.lg4,.,例,7,经计算得到,即需要15条外线,在此条件下,交换台的顾客,损失率为3.65%,有96.35%的电话得到了服务,通话率为平,均每小时185.67次,交换台每条外线的服务效率为64.23%.,在前面谈过，尽量选用简单的模型让,LINGO,软件求解，而上述程序是解非线性整数规划,(,尽管是一维的,),但计算时间可能会较长,因此,我们选用下面的处理法,分两步处理,.,第一步,求出概率为,5%,的服务台的个数,尽管要求服务台是整数,但,pel(),可以给出实数解,.,写出,LINGO,程序,程序名：,exam1007b1.lg4,.,例,7,第二步,注意到pel(load,S)是S的单调递减函数,因此,对,S取整,(,采用只入不舍原则,),就是满足条件的最小服务台数,然后再计算出其他的参数指标。,写出,LINGO,程序,程序名：,exam1007b,2,.lg4,.,比较,两种,方法的计算结果，其答案是相同的，但第二种方法比第一种方法在计算时间上要少许多,.,4,混合制排队模型,混合制排队模型通常记为,即有,S,个服务台或服务员,系统空间容量为,K,当,K,个位置,已被顾客占用时,新到的顾客自动离去,当系统中有空位,置时,新到的顾客进入系统排队等待。,对于混合制排队模型,LINGO,软件并没有提供特殊的计,算函数,因此需要对混合制排队模型的基本公式进行计算,为此,先给出其基本公式,.,设,p,i,(,i=1,2,K,),是系统有i个顾客的概率,p,0,表示系统空,闲时的概率,因此,有,:,设,i,(i=1,2,K),为系统在,i,时刻的输入强度,i,(i=1,2,K),为系统在,i,时刻的服务强度,在平衡过下,可得到平衡方程,4.1,混合制排队模型的基本公式,对于混合制排队模型，人们关心如下参数：,(1),系统的损失概率,4,.,2,混合制排队模型的基本参数,(2),系统的相对通过,能力,Q,和单位时间,平均进入系统的顾,客数,e,(3),平均队长,L,s,和平均等待队长,L,q,(4),顾客在系统内平均逗留时间,W,s,和平均排队等待时间,W,q,这两个时间可由Little公式得到,注意,:,上面两,公式中，是除,e,而不是,其理由与损失,制系统相同,.,4,.,2,混合制排队模型的基本参数,S=1,的情况,(,M/M/1/K,),例,8,某理发店只有,1,名理发员,因场所有限,店里最多可容纳,4,名顾客,假设来理发的顾客按,Poisson,过程到达,平均到达率为每小时,6,人,理发时间服从负指数分布,平均,12,分钟可为,1,名顾客理发,求该系统的各项参数指标,.,解,按照,上面分析,其,参数,S=1,K=4,R=,=6,T=,1/,=12/60,再计算相应的损失概率,p,K,及各项参数指标,编写,出,LINGO程序，程序名,:,exam100,8,.lg4,，结果见运行,即理发店的空闲率为13.4%,顾客的损失率为27.9%,每小时,进入理发店的平均顾客数为4.328人,理发店内的平均顾客数,(,队长,),为2.359人,顾客在理发店的平均逗留时间是0.545小时,(,32.7分钟,),理发店里等待理发的平均顾客数,(,等待队长,),为,1.494人,顾客在理发店的平均等待时间为0.345小时,(,20.7分,),4,.,3,混合制排队模型的计算实例,S1,的情况,(,M/M/S/K,),例,9,某工厂的机器维修中心有,9,名维修工,因为场地限制,中心内最多可以容纳,12,台需要维修的设备,假设待修的设备按,Poisson,过程到达,平均每天,4,台,维修设备服从负指数分布,每台设备平均需要,2,天时间,求该系统的各项参数指标,.,解,其,参数,S=9,K=12,R=,=4,T=,1/,=2,再计算相应的损失概率,p,K,及各项参数指标,编写,出,LINGO程序，,程序名,:,exam100,9,.lg4,，结果见运行,经计算得到：维修中心的空闲率p,0,=0.033%$,设备的损失率,P,lost,=8.61%,每天进入维修中心需要维修的设备,e,=3.66台,维修中心内的平均维修的设备,(,队长,),L,s,=7.87台,待修设备在,维修中心的平均逗留时间W,s,=2.15天,维修中心内等平均待,维修的设备,(,等待队长,),L,q,=0.561天,待修设备在维修中心的,平均等待时间W,q,=0.153天,.,5,闭合式排队模型,设系统内有,M,个服务台,(,或服务员,),顾客到达系统的间隔,时间和服务台的服务时间均为负指数分布,而系统的容,量和潜在的顾客数都为,K,又顾客到达率为,服务台的,平均服务率为,这样的系统称为闭合式排队模型,记为,对于闭合式排队模型，我们关心的参数：,(1),平均队长,5,.,1,闭合式排队模型的基本参数,其中,load,是系统的负荷,其计算公式为,即,系统的负荷,=,系统的顾客数,X,顾客的到达率,X,顾客的服务时间,(2),单位时间平均进入系统的顾客数,e,或,R,e,.,(3),顾客处于正常情况的概率,(5),每个服务台,(,服务员,),的工作强度,(4),平均逗留时间,W,s,、平均等待队长,L,q,和 平均排队等待,时间,W,q,这三个值可由Little公式得到,S=1,的情况,(,M/M/1/K/K,),例,10,设有,1,名工人负责照管,6,台自动机床,.,当机床需要加料、发生故障或刀具磨损时就自动停车,等待工人照管,.,设平均每台机床两次停车的时间间隔为,1,小时,停车时需要工人照管的平均时间是,6,分钟,并均服从负指数分布,求该系统的各项指标,.,解,这是一个闭合式排队模型,M/M/1/6/6,其,参数为,S=1,K=6,R=,=1,T=,1/,=6/60,计算,出平均队长,再,计算出其他各项指标,写,出,LINGO程序,程序名,:,exam10,10,.lg4,结果见运行,.,机床的平均队长为0.845台,平均等待队长为0.330台,机床的,平均逗留时间为0.164小时,(,9.84分钟,),平均等待时间为0.064,小时,(,3.84分钟,),机床的正常工作概率为85.91%,工人的劳动,强度为0.515.,S1,的情况,例,11,(,继例,10.10),将例中的条件改为由,3,名工人联合看管,20,台自动机床,其他条件不变,求该系统的各项指标。,解,这是,M/M/3/20/20,闭合式排队模型,其,参数为,S=3,K=20,其余不变,写,出,LINGO程序,程序名,:,exam10,11,.lg4,结果见运行,.,5,.,2,闭合式排队模型的计算实例,从上表可以看出,在第二种情况下,尽管每个工人看管的机器数增加了,但机器逗留时间和等待维修时间却缩短了,机器的正常运转率和工人的劳动强度都提高了。,例,10,和例,11,的计算结果,比较,6,排队系统的最优化模型,排队系统中的优化模型，一般可分为系统设计的优化和,系统控制的优化。前者为静态优化，即在服务系统设置,以前根据一定的质量指标，找出参数的最优值，从而使,系统最为经济。后者称动态优化，即对已有的排队系统,寻求使其某一目标函数达到最优的运营机制。,本节的主要目的是利用,LINGO,软件求函数极值的功能,求系统的静态优化。,系统服务时间,T=1/,.,我们需要调整系统服务时间使系,统达到最优。,6,.,1,系统服务时间的确定,例,12,设某工人照管,4,台自动机床,机床运转时间,(,或各,台机床损坏的相继时间,),平均为负指数分布,假定平均每,周有一台机床损坏需要维修,机床运转单位时间内平均,收入,100,元,而每增加,1,单位,的维修费用为,75,元。求使,总利益达到最大的,*,.,例,12,解,这是一个闭合式排队系统,M/M/1/K/K,且K=4.设,L,s,是,队长,则正常运转的机器为,K-L,s,部,因此目标函数为,题意就是在上述条件下，求目标函数,f,的最大值,.,写,出,LINGO程序,程序名,:,exam10,12,.lg4,结果见运行,.,*=1.799.,最优目标值,f,*=31.49.,例,13,假定有一混合制排队系统,M/M/1/K,其顾客的到,达率为每小时,3.6,人,其到达间隔服从,Poisson,过程,.,系统服,务一个顾客收费,2,元,.,又设系统的服务强度为,(,=1/T,T,为服务时间,),服从负指数分布,其服务成本为每小时,0.5,元,.,求系统为每个顾客的最佳服务时间,.,题意就是在上述条件下，求目标函数,f,的最大值,.,写,出,LINGO程序,程序名,:,exam10,13,.lg4,结果见运行,.,解 系统的损失率为,p,K,则系统每小时服务的人数为,(1-p,K,),每小运行成本为,0.5,因此目标函数为,即,系统为每位顾客最佳服务时间是,0.2238,小时,(,13.43,分钟,),系统每小时盈利,3.70,元,.,6,.,2,系统服务台,(,员,),的确定,例,14,一个大型露天矿山,正考虑修建矿石卸位的个,数,.,估计运矿石的车将按,Poisson,流到达,平均每小时,15,辆,.,卸矿石时间服从负指数分布,平均,3,分钟卸一辆,.,又知,每辆运送矿石的卡车售价是,8,万元,修建一个卸位的投资,是,14,万元,.,问应建多少个矿山卸位最为适宜？,题意就是在上述条件下，求目标函数,f,的最小值,.,写,出,LINGO程序,程序名,:,exam10,14,.lg4,结果见运行,.,解 用等待制排队系统,M/M/S/,进行分析,其费用包括两,个方面,一个是建造卸位的费用,另一是卡车处于排队状,态不能工作的费用,因此目标函数为,例,14,即建,2,个卸位，总成本是,34.98,万元,.,