忻展红-运筹学-课件运筹九

1、管理与人文学院1999，4忻展红第九章特殊随机服务系统秩序影响服务质量9.1 M/G/1等待制，无限源，无限容量 G 表示一般独立分布，没有具体的分布函数，但知道该分布的数学期望 1/m 和方差 s2 设到达率为 l，平均服务时长为 h = 1/m ，则系统业务量为r = lh；同样，系统有稳态的条件是 r 0n+1YL= 0n+1nYn+1Ln. .第n个顾客Ln+1第n+1个顾客) = 1,Ln 0Ln = 0U ( L若令0,n= Ln + Yn+1 - U ( Ln )Ln+1(1)则由于Ln 与 Yn+1 独立,对上式两边取数学期望,得ELn+1 = ELn + EYn+1 - EU

2、 ( Ln )ELn+1 = ELn ,故系统稳态时有EYn+1 = EU ( Ln )(2) EYn+1 代表一个服务时长内到达系统的平均顾客数 EU(Ln) 代表系统中有顾客逗留的概率，也即服务台被占用的概率；服务台被占用的概率就是 r，所以有EU ( Ln ) = EYn+1 = r(3)对(1)式两边平方后再求数学期望,整理后得EY 2 - 2r 2 + rELn = n+1(4)2(1 - r )通过复杂的计算可得EY 2 = l2s 2 + r 2 + r3n+1 Ld，Lq 不但与 r 有关，而且与 s2 有关 (5),(6)式以数学家 朴拉切克欣钦 命名4对于定长分布, s 2

3、 = 0,有r (1 - r2)r 2Ld =1 - rLq = 2(1 - r )对于负指数分布,有s 2 = 1m 2 ,故rr 2Ld = 1 - rLq = 1 - r(方差越大队越长!)由此可得l2s 2 + r 2Ld = ELn =2(1 - r )+ r(5)l2s 2 + r 2Lq = Ld - r =2(1 - r )(6) 顾客等待的概率为 D=EU(Ln)=r，不需等待的概率为 1- r9.1.2 平均剩余服务时间 对于负指数服务时间分布，众所周知剩余服务时间仍服从原来的分布，即 h =1/m 但在M/G/1中，平均剩余服务时间 Tr 需要研究，它与顾客排队等待的时间

4、 Wq 有关；显然， Wq分为两部分：(1)等待服务台空出的平均时间，(2)排在队中所有顾客的服务时间5对于第(1)部分的平均等待时间T1 = 0(1 - r ) + Tr r = Tr r对于第(2)部分的平均等待时间T2 = hLq = lWqm = rWq对于k阶爱尔兰分布,有方差s 2 = 1km 2 , 因此1 + kr 21 + krLq =2k1 - rWq = Lql =2km - l 对于定长分布，e =1，Tr = h/2 对于负指数分布，e =2，Tr=h 对于 k 阶爱尔兰分布，e =？，Tr=？6由Wq = T1 + T2 = rTr + rWq1 - rs 2 +

5、h2整理得Tr =rWq =2h(7)等待服务台空出的平均等待时间为l(s 2 + h2 )T1 = rTr =2(8)一般Tr = h e2e称为Palm s formfactor ,反映服务时长离差程2e =M2=二阶矩= 1 + s (9)M 2(一阶矩)2 h 19.2 优先权服务系统9.2.1 M/G/1 非强占优先系统 设有 m 级顾客，1 级顾客为最高优先权，每级内采用FIFO 各级顾客到达率为 li，波松流，各级顾客的平均服务时长都为 hi，方差为 si2；系统总业务量 r = li hi， r 1 利用上节推导出的等待服务台空出的时间 T1，可知W1=T1/(1-r1)，递推

6、得第 k 级顾客的平均等待时间 Wk k 级顾客的平均等待时间与比之高级顾客的业务量有关 平均服务时间短的顾客有高优先权，可以减少总的排队时间 优先权级别不宜太多，插队现象就是增加等级，使总等待时7间增加k-21 - r iTT=m li (h2 + s 2 )Wk = i=1Wk-1 = 11 2iikkk-1i=11 - r i1 - r i 1 - r i (10)i=1i=1i=1例1在M/G/1 服务系统中，有两类顾客，都是波松到达过程。第一类顾客 l1= 2个/秒，定长服务 h1= 0.1秒/个；第二类顾客l2= 0.5个/秒，负指数服务 h2= 1.2秒/个，试求：(1)不分优先

7、权时的顾客平均等待时间；(2)非强占优先权，第一类顾客或第二类顾客优先时，各类顾客的平均等待时间。解： l1= 2，h1= 0.1，r1=0.2Erl，s 2=0；1l2= 0.5，h2= 1.2，r2=0.6Erl，s 2=h 2=1.22=1.4422(1) 不分优先权，属纯M/G/1 系统，由 T1 公式，得T1=(2/2)(0+0.12)+(0.5/2)(1.22+1.22)=0.73秒Wq=T1/(1-r )=0.73/(1-0.2-0.6)=3.65秒(2) 非强占优先，第一类顾客优先W1=T1/(1-r1 )=0.73/(1-0.2)=0.9125秒W2=T1/(1-r1 )(1

8、-r1-r2) =0.73/(1-0.2)(1-0.8)=4.563秒非强占优先，第二类顾客优先W2=T1/(1-r2 )=0.73/(1-0.6)=1.825秒W1=T1/(1-r2 )(1-r1-r2) =0.73/(1-0.6)(1-0.8)=9.125秒89.2.3M/M/n 服务系统，非强占优先权 与M/G/1 非强占优先权系统的基本假设大多数一样，但有n 个独立并联服务台，各级顾客的平均服务时间都是 h 各级顾客到达率为 li，系统总到达率 l = li，总业务量r= li h， r 0.02)，但当该中继线忙时，允许通过迂回路由接通呼叫；在高效路由上呼损而转移到迂回路由上的话务流

9、量称为溢流，如图所示 溢流具有突发性，不再是波松流，目前仍不清楚其分布 具有溢流的系统是一个部分利用度系统n溢流溢流通路963迂回路由高效直达路由11t2319.3.3 溢流通路的计算已知 A23和给定的 B23，可以用爱尔兰损失公式直接求 n23如何求溢流通路(2,1)的容量 n21，因为其上除直达业务量 A21， 还有(2,3)的溢出流量 Ao23 ，而 Ao23 不是波松流，不能简单迭加，因而也不能直接用爱尔兰损失公式求 n21威尔金森(R.I Wilkinson, 1956)提出了“等效随机流法”的近似计算方法就是给出一种溢出流的迭加方法，然后求一个等效波松流 A 和一个等效电路群 n

10、，使 A 通过 n 后的溢流等于原溢出流的迭加，如图所示Ao23ns2S AoiS s223Ao23.n23Ao2121oi.AoNs2 o21.A等效21N.nAo, s2o.AA 12oN等效随机流的计算方法与步骤1、计算(2,3)的溢流均值和方差由于 n23 是 A23 的专用通路，给定 B23，有威尔金森给出求溢流方差的公式2、计算各通路上的溢流总和的均值和方差注意，波松流自身的方差等于均值，即 A21=s2213、计算等效随机流 A 和等效通路数 n波松流 A 经过通路 n 都会有公式(1),(2)给出的溢流如何根据已知溢流(Ao, s 2) 反解 A 和 no拉普(Y.Rapp,

11、1964) 给出了反解公式13Ao = Aois 2 = s 2(3)ooiiio 2= A1 - A+Ai(2)oioi oin+ 1 + A- Aioii En( A23 ) B23Ao23 = A23En( A23 )(1)2323等效随机流的计算方法与步骤拉普公式4、计算溢流通路的电路数 N等效于将 A 加载到 n+N 的通路上， 给定 呼损 B，有5、计算各通路的呼损将最终呼损 AoN 按各通路的溢流分摊14ANi = Aoi AoNBi = ANi(7)AoAiEn+N ( A) BAoN = AEn+N ( A)(6)23s 2 s 2A = s o + o o - 1(4)Ao

12、 Aon = A - Ao - 1q = 1 -1(5)qs 2Ao + o Ao例1 求溢流通路(A,D)的电路数 NAD，要求 B0.011、计算(D,B)(D,C)的溢流 Ao1, s2o1查表，并利用线性内插，得2、计算(A,D)的总溢流 Ao, s2o3、计算等效流 A 和等效电路 nA = 12.624 + 3 12.624 12.624 - 1 = 13.011.35 11.35q = 1 -1= 0.92n =13- 11.35 - 1 = 1.7811.35 + 12.624 11.350.9215Ao = 2 1.425 + 8.5 = 11.35s 2 = 2 2.062

13、 + 8.5 = 12.624oE5 (5) = 0.2 + 0.1 5 - 4.010= 0.2855.189 - 4.010AoDB = AoDC = Ao1 = 5E5 (5) = 1.425o 2= 1.425- 1.425 +5o115 + 1 + 1.425 - 5 = 2.062AA=8.5BErlCN=?A=5ErlDA=5Erl n=5n=5例1 求溢流通路(A,D)的电路数 NAD，要求 B0.014、计算溢流通路(A,D)所需通路数 N5、计算(A,D),(D,B)(D,C)的呼损有不合理现象，级点间的呼损小于骨干上点间呼损16AN ( AD) = AoAD AoN =8.50.08835 = 0.0662Ao11.35AN ( DB) = 1.425 0.08835 = 0.011111.35BAD = 0.0662 = 0.0078,BDB = BDC = 0.0111 + BAB = 0.00222 + BAB8.55要求 En+ N (13) 0.01查表得 n + N = 22N = 20.22取N = 21由线性内差得E22 (13) = 0.0068AoN= 13 0.0068 = 0.08835AA=8.5BErlCN=21A=5ErlDA=5Er