CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第九章特殊随机服务系统 秩序影响服务质量
©管理与人文学院 忻展红 1999，4 第九章 特殊随机服务系统 秩序影响服务质量
9M/Gi/1等待制,无限源,无限容量 G表示一般独立分布,没有具体的分布函数,但知道该分布 的数学期望1/和方差a 设到达率为,平均服务时长为h=1/,则系统业务量为 p=和h;同样,系统有稳态的条件是p0 n+1 间的系统排队队长 n2+1 L=0 Yn+1为第n+1个顾客服务时 间内到达的顾客数
2 9.1 M/G/1 等待制，无限源，无限容量 • G 表示一般独立分布，没有具体的分布函数，但知道该分布 的数学期望 1/ 和方差 2 • 设到达率为 ，平均服务时长为 h = 1/ ，则系统业务量为 = h；同样，系统有稳态的条件是 < 1 9.1.1 系统中逗留顾客的平均数 • 由于服务时长不具有马氏性，不能套用生灭方程求稳态 pj • 以第 n 个顾客离去瞬间系统内顾客数表示系统状态，如图 • Ln 为第 n 个顾客离开系统瞬 间的系统排队队长 • Yn+1 为第 n +1 个顾客服务时 间内到达的顾客数第n个顾客 第n+1个顾客 Ln Yn+1 Ln+1 ... ... ... ... = + − = + + + 0 1 0 1 1 1 n n n n n n Y L L Y L L
若令U(Ln) Ln>o 0. L=0 n n+1 n n2+1 U(Ln) n 由于Ln与Yn+1独立,对上式两边取数学期望得 EILn+1=elLnl+elYn+1 -EIU(Ln)I 系统稳态时有ELn+l=ELnl,故 ElYn+1=EU(Ln) EYn代表一个服务时长内到达系统的平均顾客数 EU(L川代表系统中有顾客逗留的概率,也即服务台被占 用的概率;服务台被占用的概率就是p,所以有 EIU(Ln=Elm+1=p (3) 对(1)式两边平方后再求数学望整理后得 ElEnI E(2 11-2p2+p (4) 2(1-p) 通过复杂的计算可得EY1l=x2a2+p2+p
3 [ ] [ ( )] (2) [ ] [ ], [ ] [ ] [ ] [ ( )] , , ( ) (1) 0, 0 1, 0 ( ) 1 1 1 1 1 1 1 n n n n n n n n n n n n n n n n n E Y E U L E L E L E L E L E Y E U L L Y L L Y U L L L U L = = = + − = + − = = + + + + + + + 系统稳态时有 故 由 于 与 独 立 对上式两边取数学期望得 则 若 令 • E[Yn+1] 代表一个服务时长内到达系统的平均顾客数 • E[U(Ln )] 代表系统中有顾客逗留的概率，也即服务台被占 用的概率；服务台被占用的概率就是 ，所以有 = + + − − + = = = + + + 2 2 2 2 1 2 2 1 1 [ ] (4) 2(1 ) [ ] 2 [ ] (1) , [ ( )] [ ] (3) n n n n n E Y E Y E L E U L E Y 通过复杂的计算可得 对 式两边平方后再求数学期 望 整理后得
由此可得 d= ellul 2(1-p (5) x2a2+ (6) 2(1-p) Ld,Lq不但与p有关,而且与a2有关 (5),(6)式以俄国数学家朴拉切克欣钦命名 对于定长分布a2=0,有 p(1-p/2) 2(1-p) 对于负指数分布有a2=1/m2,故 q=1(方差越大队越长)
4 (6) 2(1 ) (5) 2(1 ) [ ] 2 2 2 2 2 2 − + = − = + − + = = q d d n L L L E L 由此可得 • Ld，Lq 不但与 有关，而且与 2 有关 • (5),(6)式以俄国数学家 朴拉切克—欣钦 命名 ( !) 1 1 , 1 , 1 2(1 ) (1 2) , 0, 2 2 2 2 2 方差越大队越长 对于负指数分布 有 故 对于定长分布 有 − = − = = − = − − = = d q d q L L L L
对于阶爱尔兰分布有方差σ2=1/km2,因此 I+k p 1+k 2k1 2kH-元 顾客等待的概率为D=EU(Ln)=p,不需等待的概率为1-p 912平均剩余服务时间 对于负指数服务时间分布,众所周知剩余服务时间仍服从 原来的分布,即h′=1/ 但在MG/中,平均剩余服务时间T需要研究,它与顾客 排队等待的时间W有关;显然,W分为两部分:(1)等待 服务台空出的平均时间,(2)排在队中所有顾客的服务时间 对于第1)部分的平均等待时间 71=0(1-p)+Tp=Trp 对于第2)部分的平均等待时间 T2=hLg =Walu=pW a
5 − + = = − + = = k k W L k k L k k q q q 2 1 2 1 1 , 1 , 2 对 于 阶爱尔兰分布 有方差 2 2 因 此 • 顾客等待的概率为 D=E[U(Ln )]=，不需等待的概率为 1− 9.1.2 平均剩余服务时间 • 对于负指数服务时间分布，众所周知剩余服务时间仍服从 原来的分布，即 h =1/ • 但在M/G/1中，平均剩余服务时间 Tr 需要研究，它与顾客 排队等待的时间 Wq 有关；显然， Wq分为两部分：(1)等待 服务台空出的平均时间，(2)排在队中所有顾客的服务时间 q q q r r T hL W W T T T = = = = − + = 2 1 (2) 0(1 ) (1) 对于第 部分的平均等待时间为 对于第 部分的平均等待时间为
由Wq=T+n2=pTr+pHq 整理得 +h 2h 等待服务台空出的平蟒待时间为 a(a2+h2) T=pTr (8) 般 h E称为 Palm' s form factor,反映服务时长离差程月 M2二阶矩 (9) 阶矩 对于定长分布,E=1,Tr=h/2 对于负指数分布,E=2,T=h 对于k阶爱尔兰分布,E=?,T=?
6 1 ( 9 ) ( ) ' , 2 ( 8 ) 2 ( ) ( 7 ) 2 1 2 2 2 12 2 2 1 2 2 1 2 = = = + = + = = + = − = = + = + M h M Palm s form factor h T h T T h h T W W T T T W r r r q q r q 一阶矩 二阶矩 称 为 反映服务时长离差程度 一 般 等待服务台空出的平均等待时间为 整理得 由 • 对于定长分布， =1 ， Tr = h/2 • 对于负指数分布， =2 ， Tr = h • 对于 k 阶爱尔兰分布 ， =？， Tr = ？
92优先权服务系统 921MG/1非强占优先系统 设有m级顾客,1级顾客为最高优先权,每级内采用FIFO 各级顾客到达率为41,波松流,各级顾客的平均服务时长 都为h,方差为σ2;系统总业务量p=∑41h1,p<1 利用上节推导出的等待服务台空出的时间T1,可知 W1=T1(1-p1),递推得第k级顾客的平均等待时间Wk ∑P 1=24 G2+) 2 ∑pa 1-∑p1∑P (10) k级顾客的平均等待时间与比之高级顾客的业务量有关 平均服务时间短的顾客有高优先权,可以减少总的排队时间 优先权级别不宜太多,插队现象就是增加等级,使总等待时 间增加
7 9.2 优先权服务系统 9.2.1 M/G/1 非强占优先系统 • 设有 m 级顾客，1 级顾客为最高优先权，每级内采用FIFO • 各级顾客到达率为 i，波松流，各级顾客的平均服务时长 都为 hi，方差为 i 2；系统总业务量 = i hi， <1 • 利用上节推导出的等待服务台空出的时间 T1，可知 W1=T1 /(1−1 )，递推得第 k 级顾客的平均等待时间 Wk ( ) (10) 2 1 1 1 1 1 2 2 1 1 1 1 1 1 1 2 1 − = = = − = − = = + − − = − − = m i i i i k i i k i i k k i i k i i k T T h W W • k 级顾客的平均等待时间与比之高级顾客的业务量有关 • 平均服务时间短的顾客有高优先权，可以减少总的排队时间 • 优先权级别不宜太多，插队现象就是增加等级，使总等待时 间增加
例1在MG/1服务系统中,有两类顾客,都是波松到达过程 第一类顾客λ1=2个秒,定长服务h1=0.秒个;第二类顾客 λ2=0.5个秒,负指数服务h2=1秒∧个,试求:(1)不分优先权 时的顾客平均等待时间;(2)非强占优先权,第一类顾客或第 二类顾客优先时,各类顾客的平均等待时间 解:41=2,h1=0.1,p1=02Er,a12=0 λ2=0.5,h2=1.2,p2=0.6Erl,a2=h2=1.22=144 (1)不分优先权,属纯M/G/系统,由T1公式,得 T1=(2/2)(0+0.12)+(0.5/2)(12+12)=073秒 WG=T/(1-p)=0.73(1-0.2-0.6=3.65秒 (2)非强占优先,第一类顾客优先 W1=T1(1-p1)=0.73/(1-0.2)=0.9125秒 W2=T/(1-1)(1-1-2)=0.73/1-0.2)-0.8)=4.563秒 非强占优先,第二类顾客优先 W2=T1(-p2)=0.73/1-0.6)=1825秒 W1=T1(1-p2)(1-p1-P2)=0.73(1-0.6(1-0.8)=9125秒8
8 例1 在 M/G/1 服务系统中，有两类顾客，都是波松到达过程。 第一类顾客 1= 2个/秒，定长服务 h1= 0.1秒/个；第二类顾客 2= 0.5个/秒，负指数服务 h2= 1.2秒/个，试求：(1)不分优先权 时的顾客平均等待时间；(2)非强占优先权，第一类顾客或第 二类顾客优先时，各类顾客的平均等待时间。 解： 1= 2，h1= 0.1，1=0.2Erl，1 2=0； 2= 0.5，h2= 1.2，2=0.6Erl，2 2=h2 2=1.22=1.44 (1)不分优先权，属纯 M/G/1 系统，由 T1 公式，得 T1=(2/2)(0+0.12 )+(0.5/2)(1.22+1.22 )=0.73秒 Wq =T1 /(1− )=0.73/(1−0.2−0.6)=3.65秒 (2) 非强占优先，第一类顾客优先 W1=T1 /(1−1 )=0.73/(1−0.2)=0.9125秒 W2=T1 /(1−1 )(1−1−2 ) =0.73/(1−0.2)(1−0.8)=4.563秒 非强占优先，第二类顾客优先 W2=T1 /(1−2 )=0.73/(1−0.6)=1.825秒 W1=T1 /(1−2 )(1−1−2 ) =0.73/(1−0.6)(1−0.8)=9.125秒
923MMm服务系统,非强占优先权 与MG/1非强占优先权系统的基本假设大多数一样,但有 n个独立并联服务台,各级顾客的平均服务时间都是h 各级顾客到达率为4,系统总到达率=ΣA1,总业务量B ∑λ;h, 上节(10)式仍成立,有 hL ahw W +们1 +们i n ∑p;1-∑p i=1 故T1 Wa p= ah q 令W为全体顾客的平由MMn等待制的W公式 均等待时间,Lq为平均 n+1 队长,则 Po (n-1)!(n-p) n+1 得T1= an! (n-p po
9 9.2.3 M/M/n 服务系统，非强占优先权 • 与 M/G/1 非强占优先权系统的基本假设大多数一样，但有 n 个独立并联服务台，各级顾客的平均服务时间都是 h • 各级顾客到达率为 i，系统总到达率 = i，总业务量 = i h， < n • 上节(10)式仍成立，有 − − = − = = 1 1 1 1 1 1 k i i k i i k T W • 令 Wq 为全体顾客的平 均等待时间，Lq 为平均 队长，则 0 1 1 0 2 1 1 1 1 !( ) ( 1)!( ) M/M/ 1 p n n T p n n W n W W h n T T n hW T n hL W n n q q q q q q − = − − = = = − = + = + + + 得 由 等待制的 公 式 故
93溢流通路计算 931部分利用度的概念 当服务台可以为所有进入系统的顾客服务时,称为全利用 度系统( Fully provided 当服务台部分分组使用,部分公用,则称为部分利用度系 统,如图际示 组1专用复接公用 回图服务台数n=6 每组的部分利 用度k=4 组2专用复接公用 全利用度系统利用率最高,但不易组织 分组专用效率低,但容易组织 部分利用度系统综合两者的优点
10 9.3 溢流通路计算 9.3.1 部分利用度的概念 • 当服务台可以为所有进入系统的顾客服务时，称为全利用 度系统(Fully provided) • 当服务台部分分组使用，部分公用，则称为部分利用度系 统，如图所示 1 2 3 4 1 2 组1专 用 组2专 用 复接公用 复接公用 5 6 服务台数 n=6 每组的部分利 用 度 k=4 • 全利用度系统利用率最高，但不易组织 • 分组专用效率低，但容易组织 • 部分利用度系统综合两者的优点