江西财经大学：《运筹学》课程教学资源（PPT课件）第八章 标准服务系统（M/M/n系统）

CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第八章标准服务系统 MM/n系统 鱼与熊掌兼得?

©管理与人文学院 忻展红 1999，4 第八章 标准服务系统 M/M/n 系统 鱼与熊掌兼得？

8MM损失制 81M/M/n损失制,无限源(MM/n:∞/m/FIFO) 令从顾客源来的顾客到达率为4,每台的服务率为 则有4=,户=0,1,…,n1;A=0,1=j厂,…, 将,代入生灭方程,得 10 Po l¨Hj-1j !u 由∑n=1得m=2pk =0 / n /k=0 pk/k j=1,2,,n 式中p=4称为业务量( raffic),是无量纲量;表示单位时间 内要求系统提供的服务时间;和的单位必须一致;由于 纪念 Erlang,用爱尔兰作单位(Er)

2 8.1 M/M/n 损失制 8.1.1 M/M/n 损失制，无限源(M/M/n: /n/FIFO) • 令从顾客源来的顾客到达率为 ，每台的服务率为  – 则有  j = , j=0,1, ... , n–1;  n=0， j = j, j=1, ... , n • 将 j , j 代入生灭方程，得 • 式中 =/称为业务量(traffic)，是无量纲量；表示单位时间 内要求系统提供的服务时间；  和  的单位必须一致；由于 纪念Erlang，用爱尔兰作单位 (Erl)  j n k j p p p k p j p j p p n k k j j n k k n j j j j j j j j j j 1,2, , ! ! 1 ! ! ! 0 1 0 0 0 0 0 0 1 1 0 2 1    = = = = = = =    = − = = − − −             由 得

系统的服务质量 系统的质量用顾客的损失率来度量,有两种度量方法 按时间计算的损失率pn,即单位时间内服务台全被占用的 时间 按顾客计算的损失率B,即单位时间内损失的顾客数与到 达顾客数之比 在本系统中有B→pn=En(),称为爱尔兰损失公式 p/n Pn /k=0 /k! B=Nn Pn=entp) 不是所有系统都有B=pn的性质 工程上经常是已知p,给定B,求所需最少的服务台n 求n一般有三种方法:迭代计算,查图,查表

3 系统的服务质量 • 系统的质量用顾客的损失率来度量，有两种度量方法 – 按时间计算的损失率 pn，即单位时间内服务台全被占用的 时间 – 按顾客计算的损失率 B，即单位时间内损失的顾客数与到 达顾客数之比 – 在本系统中有 B=pn =En ()，称为爱尔兰损失公式 • 不是所有系统都有 B=pn 的性质 • 工程上经常是已知 ，给定 B，求所需最少的服务台 n • 求 n 一般有三种方法：迭代计算，查图，查表 ( ) ! ! 0      n n n n k k n n p E p B k n p = = = =  =

求所需服务台的方法 1、查图,如书上262页 2、迭代计算 无法由En(p)给出n的逆函数,因此采用逐次试算的方洁 注意,En()有较简单的递推公式 E(p)=1 E0(p)=1 n+pEn-(p 迭代直到首次满足En()≤B,则n即为所求 3、工程上经常采用查表的方法 爱尔兰表最左边一列为服务台数n,最上面一行为服务 质量的不同等级,即B 爱尔兰表中元素的值为p,表示服务台数为n,服务质 量为B时,系统最大所能承担的业务量;工程上经常用 A表示p,A是加入话务量

4 求所需服务台的方法 1、查图，如书上262页 2、迭代计算 – 无法由 En () 给出 n 的逆函数，因此采用逐次试算的方法 – 注意， En () 有较简单的递推公式 3、工程上经常采用查表的方法 – 爱尔兰表最左边一列为服务台数 n，最上面一行为服务 质量的不同等级，即 B – 爱尔兰表中元素的值为 ，表示服务台数为 n，服务质 量为 B时，系统最大所能承担的业务量；工程上经常用 A表示  ，A 是加入话务量 迭代直到首次满足 ( ) , 则 即为所求 ( ) 1 ( ) ( ) ( ) 0 1 1 E B n E n E E E n n n n  = + = − −       

爱尔兰损失表 0.0050.010.050.10.2 0.3 0.0050.0100.0530.1110.2500.429 0.1050.1530.3810.5951.0001.449 0.3490.45508991.2711.9302.633 3456789 0.70108691.5252.0452.9453891 1.1321361221828814.0105.189 1.6221.90929603758|5.1096.514 2.1572.501|3.7384.6666.2307.857 2.7303.1284.5435.5977.3699213 3333|3.7835.37065468.52210.579 10 39614.4616.2167.511968511953 n=3,B=0.01,查表得p=0455 已知n和p如何求B,线性内插法;例:n=3,p=25 由表可知B落在0.2-0.3之间,若假设在这区间所承担 的业务量与B成线性关系,则有线性内插公式 B2.=0.2+(0.3-0.2)(25-1.930)(2633-1.930)=0.281

5 爱尔兰损失表 A n B 0.005 0.01 0.05 0.1 0.2 0.3 1 0.005 0.010 0.053 0.111 0.250 0.429 2 0.105 0.153 0.381 0.595 1.000 1.449 3 0.349 0.455 0.899 1.271 1.930 2.633 4 0.701 0.869 1.525 2.045 2.945 3.891 5 1.132 1.361 2.218 2.881 4.010 5.189 6 1.622 1.909 2.960 3.758 5.109 6.514 7 2.157 2.501 3.738 4.666 6.230 7.857 8 2.730 3.128 4.543 5.597 7.369 9.213 9 3.333 3.783 5.370 6.546 8.522 10.579 1 0 3.961 4.461 6.216 7.511 9.685 11.953 – n=3, B=0.01, 查表得 =0.455 – 已知 n 和  如何求 B，线性内插法；例： n=3，  =2.5， 由表可知 B 落在 0.2~0.3 之间，若假设在这区间所承担 的业务量与 B 成线性关系，则有线性内插公式 – B 2.5=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.281

例1MM损失制无限源系统,已知n=3,A=5人小时,平均服 务时长30分钟人,试求:(1)系统中没有顾客的概率;(2)只有 个服务台被占用的概率;(3)系统的损失率 解:由题意可知=6030=2人小时,所以p=4/=2Er (1)p0=(1+25+252/2+253/3!)-1=0.108 (2)p1=Pp0=2×0.108=0.27 (3)B=E3(25)=pp3/3=0.108×2604=0.28 例2两市话局间的忙时平均呼叫次数为240,每次通话平均时长 为5分钟,规定两局间中继线的服务等级为B≤0.01问:(1) 应配备多少条中继线?(2)中继线群的利用率为多少? 解:中继线群上的加入话务量为p=240×5/60=20Erl, (1)查262页图,n=30条; (2)查爱尔兰表可知:n=30,B=0.01时可承担A=20.337, B=0.005时可承担A=19.034,因此,E3(20)=0.005+0.005 ×(20-19.034)/(20.337-19034)=0008707 中继线群利用率m=p(1-B)=201-0.08707)30=06608626

6 例1 M/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.660862

服务台利用率与服务台数量的关系mn图 当给定n和B后,系统所能承担的业务量p可以通过爱尔 公式求出,从而可计算出服务台利用率m;若保持B不 变,不断增加服务台数n,η也会发生变化,就可以得到 n-n图如下;通过观察,有几点结论: B=0.151、B不变时,m随n增加; 80 B=0.10 说明大电路群效率高 70 B=0.05 60 2、n不变时,随B增加 B=0.01 说明效率与质量是矛盾 50 的;(高效路由) 40 30 3、η具有边际递减规律 20 4、η越大,系统抗过负荷 能力越差 0 2468101214161820n

7 服务台利用率与服务台数量的关系 −n 图 • 当给定 n 和 B 后，系统所能承担的业务量  可以通过爱尔 兰公式求出，从而可计算出服务台利用率  ；若保持 B 不 变，不断增加服务台数 n，  也会发生变化，就可以得到 −n 图如下；通过观察，有几点结论： 2 4 6 8 10 12 14 16 18 20 10 20 30 40 50 60 70 80 0 () n B=0.01 B=0.05 B=0.10 B=0.15 1、B不变时，  随 n 增加； 说明大电路群效率高 2、n 不变时，  随 B 增加； 说明效率与质量是矛盾 的；(高效路由) 3、 具有边际递减规律 4、 越大，系统抗过负荷 能力越差

系统过负荷特性a-B图 过负荷是指系统加入的业 B 务量A,超过给定服务质量 =15 0.008 所能承担的业务量A 10 过负荷用过载业务量与标 0.006 准应承担的业务量的比值 来表示,即 0.004 a=(4-4)A4=△41A B 0.002 En(4)=B,En(4)=B′ 由图可见,在同样标准的 510152025a(%)服务质量和同样的过负荷 率下,大系统的质量劣化 严重;说明效率与可靠性 是矛盾的

8 系统过负荷特性 −B 图 • 过负荷是指系统加入的业 务量 A , 超过给定服务质量 所能承担的业务量 A • 过负荷用过载业务量与标 准应承担的业务量的比值 来表示，即  = (A−A)/A = A/A En (A) = B, En (A) = B • 由图可见，在同样标准的 服务质量和同样的过负荷 率下，大系统的质量劣化 严重；说明效率与可靠性 是矛盾的 0.002 0 () n=5 0.004 0.006 0.008 5 10 15 20 n=10 n=15 25 B' B=

例3某服务部门把顾客分为两组,分别组成两个单独的服务系统。 各系统的到达率分别为41=4人小时,42=8人小时,每人的 平均占用时长都为6分钟;给定损失率为B≤0.01,试求:(1) 分组服务时每组应配备的服务台数;(2)合并为一个服务系统 时,各种条件不变,应配备的服务台数;(3)比较两种组织方 式的服务台利用率。 解:(1)分组时:=4×0.1=0.4Er,2=8×0.1=0.8Er 查爱尔兰表,得n1=3台,n2=4台,共需7台。 B1=0.005+0.005×0.4-0.349)/0.455-0.349)=0.0074 B2=0.005+0.005×(0.8-0.701)/(0.869-0.701)=0.00795 T=|P1(1-B1)+p2(1-B2)/(n1+n2)=0.17 (2)合组时:p=12×01=12Er, 查爱尔兰表,得n=5台,节省了2台。 B=0.005+0.005×(1.2-1.132)/(1.361-1132)=0.006485 7=p(1-B)/n=0.238

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.0074 B2=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.238

82IM/M/n损失制,有限源(MM/n:Nm/FIFO) 例交换机内部有n条绳略,N条入中继线,Nn;每条入中 继线上的呼叫到达强度为y,且为波松分布,通话时长为负 指数分布(参数为4),问入中继线上呼叫的损失率为多少? 上述例子就是一个MM/n损失制,有限源系统。当已经接 受绳路服务的中继线在通话中,该中继线上就不会有新的 呼叫。因此,整个系统的呼叫到达率是与系统中被服务的 中继线数相关的。这就是有限源系统的特点 ·显然,系统在各状态下的到达率和离去率分别为 1=(Njy产=0,1,…,n1,n=0,两=j户1,…,n 将,共代入生灭方程,得 N(N-1)…(一j+1)y N Po gPo j!u N P=|∑k

10 8.2.1 M/M/n 损失制，有限源(M/M/n: N/n/FIFO) 例 交换机内部有 n 条绳路，N条入中继线，N> n；每条入中 继线上的呼叫到达强度为 ，且为波松分布，通话时长为负 指数分布(参数为  )，问入中继线上呼叫的损失率为多少？ • 上述例子就是一个 M/M/n 损失制，有限源系统。当已经接 受绳路服务的中继线在通话中，该中继线上就不会有新的 呼叫。因此，整个系统的呼叫到达率是与系统中被服务的 中继线数相关的。这就是有限源系统的特点 • 显然，系统在各状态下的到达率和离去率分别为 –  j =(N– j), j=0,1, ... , n–1,  n=0， j = j, j=1, ... , n • 将 j , j 代入生灭方程，得     =                 =         = − − + = −  = q q k N p q p j N p j N N N j p n k k j j j j 1 0 0 0 0 ! ( 1)( 1)