运筹学第8章：标准服务系统MMn系统

©管理与人文学院忻展红1999，4第八章标准服务系统M/M/n系统鱼与熊掌兼得？28.1M/M/n损失制8.1.1M/M/n损失制，无限源(M/M/n:/n/FIFO)•令从顾客源来的顾客到达率为，每台的服务率为–则有j=,j=0,1,...,n–1;n=0，j=j,j=0,1,...,n•将j,j代入生灭方程，得•式中=/称为业务量(traffic)，是无量纲量；表示单位时间内要求系统提供的服务时间；和的单位必须一致；由于纪念Erlang，用爱尔兰作单位(Erl)njkjpkpppjpjppnkkjjnkknjjjjjjjjjj,,2,1!!!1!!0100000011120得由3系统的服务质量•系统的质量用顾客的损失率来度量，有两种度量方法–按时间计算的损失率pn，即单位时间内服务台全被占用的时间–按顾客计算的损失率B，即单位时间内损失的顾客数与到达顾客数之比–在本系统中有B=pn=En()，称为爱尔兰损失公式•不是所有系统都有B=pn的性质•工程上经常是已知，给定B，求所需最少的服务台n•求n一般有三种方法：迭代计算，查图，查表)(!!0nnnnkknnEppBknp4求所需服务台的方法1、查图，如书上262页2、迭代计算–无法由En()给出n的逆函数，因此采用逐次试算的方法–注意，En()有较简单的递推公式3、工程上经常采用查表的方法–爱尔兰表最左边一列为服务台数n，最上面一行为服务质量的不同等级，即B–爱尔兰表中元素的值为，表示服务台数为n，服务质量为B时，系统最大所能承担的业务量；工程上经常用A表示，A是加入话务量即为所求则迭代直到首次满足,)(1)()()()(011nBEEEnEEnnnn5爱尔兰损失表AnB0.0050.010.050.10.20.310.0050.0100.0530.1110.2500.42920.1050.1530.3810.5951.0001.44930.3490.4550.8991.2711.9302.63340.7010.8691.5252.0452.9453.89151.1321.3612.2182.8814.0105.18961.6221.9092.9603.7585.1096.51472.1572.5013.7384.6666.2307.85782.7303.1284.5435.5977.3699.21393.3333.7835.3706.5468.52210.579103.9614.4616.2167.5119.68511.953–n=3,B=0.01,查表得=0.455–已知n和如何求B，线性内插法；例：n=3，=2.5，由表可知B落在0.2~0.3之间，若假设在这区间所承担的业务量与B成线性关系，则有线性内插公式–B2.5=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.2816例1M/M/n损失制无限源系统，已知n=3，=5人/小时，平均服务时长30分钟/人，试求：(1)系统中没有顾客的概率；(2)只有一个服务台被占用的概率；(3)系统的损失率解：由题意可知=60/30=2人/小时，所以=/=2.5Erl(1)p0=(1+2.5+2.52/2+2.53/3!)1=0.108(2)p1=p0=2.50.108=0.27(3)B=E3(2.5)=p03/3!=0.1082.604=0.28例2两市话局间的忙时平均呼叫次数为240，每次通话平均时长为5分钟，规定两局间中继线的服务等级为B0.01,问：(1)应配备多少条中继线？(2)中继线群的利用率为多少？解：中继线群上的加入话务量为=2405/60=20Erl，(1)查262页图，n=30条；(2)查爱尔兰表可知：n=30，B=0.01时可承担A=20.337，B=0.005时可承担A=19.034，因此，E30(20)=0.005+0.005(2019.034)/(20.33719.034)=0.008707中继线群利用率=(1B)/n=20(1-0.008707)/30=0.6608627服务台利用率与服务台数量的关系n图•当给定n和B后，系统所能承担的业务量可以通过爱尔兰公式求出，从而可计算出服务台利用率；若保持B不变，不断增加服务台数n，也会发生变化，就可以得到n图如下；通过观察，有几点结论：210864122018161410203040506070800nB=0.01B=0.05B=0.10B=0.151、B不变时，随n增加；说明大电路群效率高2、n不变时，随B增加；说明效率与质量是矛盾的；(高效路由)3、具有边际递减规律4、越大，系统抗过负荷能力越差8系统过负荷特性B图•过负荷是指系统加入的业务量A,超过给定服务质量所能承担的业务量A•过负荷用过载业务量与标准应承担的业务量的比值来表示，即=(AA)/A=A/AEn(A)=B,En(A)=B•由图可见，在同样标准的服务质量和同样的过负荷率下，大系统的质量劣化严重；说明效率与可靠性是矛盾的0.0020n=50.0040.0060.0085101520n=10n=1525B'B=9例3某服务部门把顾客分为两组，分别组成两个单独的服务系统。各系统的到达率分别为1=4人/小时，2=8人/小时，每人的平均占用时长都为6分钟；给定损失率为B0.01，试求：(1)分组服务时每组应配备的服务台数；(2)合并为一个服务系统时，各种条件不变，应配备的服务台数；(3)比较两种组织方式的服务台利用率。解：(1)分组时：1=40.1=0.4Erl,2=80.1=0.8Erl查爱尔兰表，得n1=3台，n2=4台，共需7台。B1=0.005+0.005(0.40.349)/(0.4550.349)=0.0074B2=0.005+0.005(0.80.701)/(0.8690.701)=0.00795=[1(1B1)+2(1B2)]/(n1+n2)=0.17(2)合组时：=120.1=1.2Erl,查爱尔兰表，得n=5台，节省了2台。B=0.005+0.005(1.21.132)/(1.3611.132)=0.006485=(1B)/n=0.238108.2.1M/M/n损失制，有限源(M/M/n:N/n/FIFO)例交换机内部有n条绳路，N条入中继线，Nn；每条入中继线上的呼叫到达强度为，且为波松分布，通话时长为负指数分布(参数为)，问入中继线上呼叫的损失率为多少？•上述例子就是一个M/M/n损失制，有限源系统。当已经接受绳路服务的中继线在通话中，该中继线上就不会有新的呼叫。因此，整个系统的呼叫到达率是与系统中被服务的中继线数相关的。这就是有限源系统的特点•显然，系统在各状态下的到达率和离去率分别为–j=(N–j),j=0,1,...,n–1,n=0，j=j,j=1,...,n•将j,j代入生灭方程，得qqkNppqjNpjjNNNpnkkjjjj10000!)1()1(11•当j=n时，pn表示按时间计算的损失率nkknnqkNqnNp0•下面分析按顾客计算的损失率BB=单位时间平均损失顾客数/单位时间平均到达顾客数•在有限源系统中，顾客到达率随系统状态变化，因此有平均顾客到达率，又称为有效到达率njjnnjjpjNpnNBpjN00)()()(jNNjNjNqjNjNqnNnNBnjjn1)()()(0由12•可见，在有限源情况下，系统按时间计算的损失率pn和按顾客计算的损失率B是不相等的；其原因就是输入过程随系统状态而变•从一个极端情况看，若N=n，则B=0，但pn0•虽然爱尔兰损失公式和恩格谢特损失公式都是在负指数服务时长假设下推导出来的，但已证明服务时间是其它一般平稳分布，结论仍是正确的•服务台利用率：)(110恩格谢特损失公式得njjnqjNqnNBnjpnjj113例4有一电话查询服务处集中答复三个查询点的所有查询事项。查询服务处与查询点之间用电话联系。查询服务处只有一名值班员答复所有的查询。已知每个查询点平均每小时有两次查询，每次平均通话12分钟，问：(1)值班员空闲的概率；(2)值班员打电话的概率；(3)查询时值班员忙的概率；(4)服务处查询电话的平均到达率；(5)值班员的工时利用率。解：系统是有限源M/M/1损失制。q=/=(2/60)12=0.4Erl(1)p0=1/(1+Nq)=0.45455455.0)5(/91.423)()4(444.04.0214.02212)3(5455.01)2(1101010001ppppjNqjqBNqpqpNpjjejj小时次148.2M/M/n等待制，无限源，无限容量(M/M/n://FIFO)8.2.1系统稳态概率及等待概率•令从顾客源来的顾客到达率为，每台的服务率为–则有j=,j0;j=j,jn；j=n,jn•将j,j代入生灭方程，得nnnnnnnnnjppnjpnnpnjpjpjpnkknnjnjjnjnjjnjjnjjnjjjjjjj!!!!!1!!!011000000得由15•当n时，则p0中第二项不收敛，系统中队长将趋于无穷•当n时，系统有稳态，处于动态平衡；无限容量等待制，每个顾客早晚都会得到服务，因此系统完成的业务量也是•顾客进入系统必须排队等待的概率为11000!!,,1/,nnnjppnnjnj有才收敛时只有注意nnnjnnnwpDpnnnpwpnnjjnnnjj!!!}0{!}0{100即•D爱尔兰等待公式•排队等待的概率是等待制系统的重要指标之一•n=1时，D=•公式D的记忆法168.2.2系统的各种指标•等待制系统的指标有：平均逗留队长；平均等待队长；平均逗留时长；平均等待时长和服务台利用率等nLnDLWLWnnpLnDpnjLnDjpLnqqddndnjjqjjd//)()!1()(12011服务台利用率服务台平均占用数平均等待时长平均逗留时长平均等待队长平均逗留队长•n=1时，D=，Ld=/(1)，Lq=2/(1)，Wq=/()•例5书上273页178.2.3等待时间的概率分布•前面只推导了要等待的概率D=P{W0}，但在很多情况下我们希望知道等待时长的分布，即P{Wt}•系统中有j个顾客，jn时，新来顾客要排队等待，采用FIFO规则；令新顾客到达时为0时刻，显然，只有服务台上离去jn个顾客时，新顾客才排到队首•当n个服务台连续服务时，顾客离去率为n，因此服务台空出的过程是波松流，在(0,t)内空出i次的概率为tnnjjjnjitnijtniieWPtWPtwPptWPjeitntWPtWeitntP)(0}0{}{}{}{,,!)(}{,!)()(经推导