运筹学－北京邮电大学-8PPT模板|运筹学－北京邮电大学-8PPT模版(幻灯片模板|Powerpoint模板)

运筹学－北京邮电大学-8

第八章 标准服务系统M/M/n 系统
鱼与熊掌兼得？
8.1 M/M/n 损失制
8.1.1 M/M/n 损失制，无限源 (M/M/n: %26#61605;/n/FIFO)
令从顾客源来的顾客到达率为 %26#61548;，每台的服务率为 %26#61549;
则有 %26#61548;j = %26#61548;, j=0,1, ... , n–1; %26#61548;n=0， %26#61549;j = j%26#61549;, j=0,1, ... , n
将%26#61548;j , %26#61549;j 代入生灭方程，得
式中 %26#61554;=%26#61548;/%26#61549; 称为业务量(traffic)，是无量纲量；表示单位时间内要求系统提供的服务时间； %26#61548; 和 %26#61549; 的单位必须一致；由于纪念Erlang，用爱尔兰作单位 (Erl)
系统的服务质量
系统的质量用顾客的损失率来度量，有两种度量方法
按时间计算的损失率 pn，即单位时间内服务台全被占用的时间
按顾客计算的损失率 B，即单位时间内损失的顾客数与到达顾客数之比
在本系统中有 B=pn=En(%26#61554;)，称为爱尔兰损失公式
不是所有系统都有 B=pn 的性质
工程上经常是已知 %26#61554;，给定 B，求所需最少的服务台 n
求 n 一般有三种方法：迭代计算，查图，查表
求所需服务台的方法
1、查图，如书上262页
2、迭代计算
无法由 En(%26#61554;) 给出 n 的逆函数，因此采用逐次试算的方法
注意， En(%26#61554;) 有较简单的递推公式
3、工程上经常采用查表的方法
爱尔兰表最左边一列为服务台数 n，最上面一行为服务质量的不同等级，即 B
爱尔兰表中元素的值为 %26#61554;，表示服务台数为 n，服务质量为 B时，系统最大所能承担的业务量；工程上经常用A表示 %26#61554; ，A 是加入话务量
爱尔兰损失表
n=3, B=0.01, 查表得 %26#61554;=0.455
已知 n 和 %26#61554; 如何求 B，线性内插法；例： n=3， %26#61554; =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

例1 M/M/n 损失制无限源系统，已知 n=3，%26#61548;=5人/小时，平均服务时长30分钟/人，试求：(1)系统中没有顾客的概率；(2)只有一个服务台被占用的概率；(3)系统的损失率
解：由题意可知 %26#61549;=60/30=2人/小时，所以 %26#61554;=%26#61548;/%26#61549; =2.5Erl
(1) p0=(1+2.5+2.52/2+2.53/3!)%26#61485;1=0.108
(2) p1= %26#61554; p0=2.5%26#61620;0.108=0.27
(3) B=E3(2.5)=p0 %26#61554;3/3!=0.108 %26#61620;2.604=0.28
例2 两市话局间的忙时平均呼叫次数为240，每次通话平均时长为 5 分钟，规定两局间中继线的服务等级为 B%26#61603; 0.01,问：(1) 应配备多少条中继线？(2)中继线群的利用率为多少？
解：中继线群上的加入话务量为 %26#61554;=240 %26#61620;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 %26#61620;(20%26#61485;19.034)/(20.337%26#61485;19.034)=0.008707
中继线群利用率 %26#61544; = %26#61554;(1%26#61485;B)/n=20(1-0.008707)/30=0.660862
服务台利用率与服务台数量的关系 %26#61544;%26#61485;n 图
当给定 n 和 B 后，系统所能承担的业务量 %26#61554; 可以通过爱尔兰公式求出，从而可计算出服务台利用率 %26#61544; ；若保持 B 不变，不断增加服务台数 n， %26#61544; 也会发生变化，就可以得到%26#61544;%26#61485;n 图如下；通过观察，有几点结论：
系统过负荷特性 %26#61537;%26#61485;B 图
过负荷是指系统加入的业务量 A%26#61602;, 超过给定服务质量所能承担的业务量 A
过负荷用过载业务量与标准应承担的业务量的比值来表示，即
%26#61537; = (A%26#61602;%26#61485;A)/A = %26#61508;A/A
En(A) = B, En(A%26#61602;) = B%26#61602;
由图可见，在同样标准的服务质量和同样的过负荷率下，大系统的质量劣化严重；说明效率与可靠性是矛盾的

例3 某服务部门把顾客分为两组，分别组成两个单独的服务系统。各系统的到达率分别为 %26#61548;1 =4人/小时， %26#61548;2 =8人/小时，每人的平均占用时长都为 6 分钟；给定损失率为 B %26#61603; 0.01 ，试求：(1)分组服务时每组应配备的服务台数；(2)合并为一个服务系统时，各种条件不变，应配备的服务台数；(3)比较两种组织方式的服务台利用率。
解：(1) 分组时： %26#61554;1=4 %26#61620;0.1=0.4Erl, %26#61554;2=8 %26#61620;0.1=0.8Erl
查爱尔兰表，得 n1=3台， n2=4台，共需 7台。
B1=0.005+0.005 %26#61620;(0.4%26#61485;0.349)/(0.455 %26#61485;0.349)=0.0074
B2=0.005+0.005 %26#61620;(0.8%26#61485;0.701)/(0.869 %26#61485;0.701)=0.00795
%26#61544; = [%26#61554;1(1 %26#61485; B1)+%26#61554;2(1 %26#61485; B2)]/(n1+n2)=0.17
(2) 合组时： %26#61554; =12 %26#61620;0.1=1.2Erl,
查爱尔兰表，得 n =5台，节省了 2台。
B =0.005+0.005 %26#61620;(1.2%26#61485;1.132)/(1.361%26#61485;1.132)=0.006485
%26#61544; = %26#61554;(1 %26#61485; B)/n=0.238
8.2.1 M/M/n 损失制，有限源 (M/M/n: N/n/FIFO)
例 交换机内部有 n 条绳路，N条入中继线，N%26gt; n；每条入中继线上的呼叫到达强度为 %26#61543;，且为波松分布，通话时长为负指数分布(参数为 m )，问入中继线上呼叫的损失率为多少？
上述例子就是一个 M/M/n 损失制，有限源系统。当已经接受绳路服务的中继线在通话中，该中继线上就不会有新的呼叫。因此，整个系统的呼叫到达率是与系统中被服务的中继线数相关的。这就是有限源系统的特点
显然，系统在各状态下的到达率和离去率分别为
%26#61548;j =(N– j)%26#61543;, j=0,1, ... , n–1, %26#61548;n=0， %26#61549;j = j%26#61549;, j=1, ... , n
将%26#61548;j , %26#61549;j 代入生灭方程，得
当 j=n 时，pn表示按时间计算的损失率
下面分析按顾客计算的损失率 B
B=单位时间平均损失顾客数/单位时间平均到达顾客数
在有限源系统中，顾客到达率随系统状态变化，因此有平均顾客到达率 %26#61548;，又称为有效到达率

可见，在有限源情况下，系统按时间计算的损失率 pn 和按顾客计算的损失率 B 是不相等的；其原因就是输入过程随系统状态而变
从一个极端情况看，若 N=n，则 B=0，但 pn %26#61625; 0
虽然爱尔兰损失公式和恩格谢特损失公式都是在负指数服务时长假设下推导出来的，但已证明服务时间是其它一般平稳分布，结论仍是正确的
服务台利用率：

例4 有一电话查询服务处集中答复三个查询点的所有查询事项。查询服务处与查询点之间用电话联系。查询服务处只有一名值班员答复所有的查询。已知每个查询点平均每小时有两次查询，每次平均通话12分钟，问：(1)值班员空闲的概率；(2)值班员打电话的概率；(3)查询时值班员忙的概率；(4)服务处查询电话的平均到达率；(5)值班员的工时利用率。
解：系统是有限源 M/M/1 损失制。q=%26#61543; /%26#61549; =(2/60)%26#61620;12=0.4Erl
(1) p0=1/(1+Nq)=0.4545
8.2 M/M/n 等待制，无限源，无限容量 (M/M/n: %26#61605;/%26#61605;/FIFO)
8.2.1 系统稳态概率及等待概率
令从顾客源来的顾客到达率为 %26#61548;，每台的服务率为 %26#61549;
则有 %26#61548;j = %26#61548;, j%26#61619;0; %26#61549;j = j%26#61549;, j%26lt;n； %26#61549;j = n%26#61549;, j%26#61619;n
将%26#61548;j , %26#61549;j 代入生灭方程，得

当 %26#61554; %26#61619; n 时，则 p0 中第二项不收敛，系统中队长将趋于无穷
当 %26#61554; %26lt; n 时，系统有稳态，处于动态平衡；无限容量等待制，每个顾客早晚都会得到服务，因此系统完成的业务量也是 %26#61554;
顾客进入系统必须排队等待的概率为
8.2.2 系统的各种指标
等待制系统的指标有：平均逗留队长；平均等待队长；平均逗留时长；平均等待时长和服务台利用率等
8.2.3 等待时间的概率分布
前面只推导了要等待的概率 D=P{W%26gt;0}，但在很多情况下我们希望知道等待时长的分布，即 P{W%26gt;t}
系统中有 j 个顾客， j%26#61619;n 时，新来顾客要排队等待，采用FIFO规则；令新顾客到达时为 0 时刻，显然，只有服务台上离去 j%26#61485;n个顾客时，新顾客才排到队首
当 n 个服务台连续服务时，顾客离去率为 n%26#61549;，因此服务台空出的过程是波松流，在(0, t)内空出 i 次的概率为
等待时长分布的推导

例6 某储蓄所内，已知忙时顾客到达率 %26#61548;=40人/小时，窗口营业员服务率为 %26#61549;=16人/小时，要求：(1)工时利用率不低于 60%；(2)顾客平均等待时间不超过 5 分钟；问：设几个窗口适当。
解：系统是无限源 M/M/n 等待制。%26#61554;= %26#61548; /%26#61549; =40/16=2.5Erl
(1) %26#61544; = %26#61554; /n %26#61619; 0.6，解出 n %26#61603; 4.17，故 n 可取值 3， 4
(2) n=3 时，p0=(1+%26#61554;+%26#61554;2/2! + (%26#61554;3/3!)(3/(3-2.5))%26#61485;1=0.045

例7 兴建一座港口码头，只有一个装卸泊位，要求设计泊位的生产能力，能力用日装卸船只数表示。已知单位装卸能力日平均生产费用为 a=2000元；船只到港后若不能及时装卸，逗留一日要损失运输费 b=1500元；预计船只的平均到达率为 %26#61548;=3 只/日。设船只到达的间隔时间和装卸时间都服从负指数分布，问港口生产能力设计为多大时，每天总费用最小？
解：系统是无限源 M/M/1 等待制，生产能力用 %26#61549; (只/日)表示
目标函数：min C= a%26#61549; +bLd
例8 M/M/1 等待制系统,无限队长,顾客到达与队长有关
该系统仍为无限源，但考虑到顾客对排队的心理，假设顾客到达率与队长成反比关系 即 %26#61548;j = %26#61548;0 /(1+j)， %26#61548;0 为队长为 0时的顾客到达率
从而系统的 %26#61548;j 和 %26#61549;j 为