为W.于是当i<N时有 P(W=0|Xx1=i)=1 而当i≥N时,此顾客的等待时间恰为t后,第i-N+1个顾客离开的时间(因为在这之 前,N条服务线忙于为排队在为前面的-N+1个顾客服务,只有当第i-N+1个顾客结 束服务后,这N条服务线中才有一条空出来).记t时间以后第k个顾客离开的时间为 t+ok,注意顾客与服务线的服务时间是相互独立的,当i≥N时就有 P(G1≥S|X,=1)=P(N条服务线无一在s前结束|X1=D)=(e)=eM 可见G1服从参数为Nμ的指数分布.再则,在i≥N+1时,当第1个顾客结束服务后,这N 条服务线各自需要多少时间结束已开始的服务,是与此前的情况相互独立的,而且仍相互独 立地服从参数为的指数分布。所以,当i≥N+k-1时,{o1-0}skk服从相互独立 的指数分布exp·故而ak~I(k,N)分布,即 P(oks)=Nu Nμ Nas(Nu·s) (k-1)! 最后,原来排队的i人在时刻t新来的顾客加入后成为1+1人,除去在接受服务的N人外, 需要等待i+1-N次服务,因此由丌,的表达式我们得到 PW≥s)=∑兀,P (N·4·s)y 丌xe 丌xe (NuS) I =丌xe 1- Ne Np-i)s Np Nu-λ 于是有下面的定理 定理7.3可逆M/M/N系统在稳定时有 1#需要等待的概率为 P>0)=r,_M (7.11) 2#平均等待时间为 NA EW=」P(W>s)kds= (7.12)
181 为W . 于是当i < N 时有 P(W = 0 | Xt = i) = 1． 而当i ³ N 时, 此顾客的等待时间恰为t 后, 第i - N +1个顾客离开的时间 ( 因为在这之 前, N 条服务线忙于为排队在为前面的i - N +1个顾客服务, 只有当第 i - N +1个顾客结 束服务后, 这 N 条服务线中才有一条空出来 ). 记t 时间以后第k 个顾客离开的时间为 k t +s , 注意顾客与服务线的服务时间是相互独立的, 当i ³ N 时就有 ( | ) ( | ) 1 P s X i P N s X i s ³ t = = 条服务线无一在 前结束 t = s N N s e e - × - × = = m m ( ) . 可见s1服从参数为 Nm 的指数分布. 再则，在 i ³ N +1时, 当第 1 个顾客结束服务后, 这 N 条服务线各自需要多少时间结束已开始的服务，是与此前的情况相互独立的, 而且仍相互独 立地服从参数为 m 的指数分布。 所以，当i ³ N + k -1时, j - j -1 1£ j£k {s s } 服从相互独立 的指数分布 m exp . 故而 s ~ (k, Nm) k G 分布, 即 ò ¥ - × - - × ³ = s N x k k e dx k N x P s N m m s m ( 1)! ( ) ( ) 1 å - = - × × = 1 0 ! ( ) k j j N s j N s e m m . 最后, 原来排队的 i 人在时刻t 新来的顾客加入后成为 i +1人, 除去在接受服务的 N 人外, 需要等待i +1- N 次服务, 因此由p i 的表达式我们得到: å ¥ = ³ = + - ³ i N P(W s) iP( i N s) p s 1 å ¥ = - = i N i N N N ( ) m l p å - = - ×× × × × i N j j N s j N s e 0 ! ( m ) m å å= ¥ = - × = l j j l l N s N j N s N e 0 0 ! ( ) ( ) m m l p m å å ¥ = ¥ = - = l j l j j N s N j N N s e ( ) ! ( ) 0 m m l p m m l m m l p m N j N s N e j j j N s N - = å ¥ = - × 1 1 ! ( ) ( ) 0 m l m p m l - = - - N N e N s N ( ) . 于是有下面的定理 定理７.３ 可逆M / M / N 系统在稳定时有 1 # 需要等待的概率为: m l m p - > = N N P W N ( 0) . (7.11) 2 # 平均等待时间为 ò ¥ - = > = 0 2 ( ) ( ) m l m p N N EW P W s ds N . (7.12)
特别当N=1时有丌1=-(1--),EW λ -元·同时也可得平均停留时间T 因为它是等待时间W与服务时间的和 2.3序贯排队与排队网络系统 1.简单的序贯排队模型 设排队系统由两个M/M/1子系统串联而成.设进入第一个子系统的顾客流为参数λ 的指数流,服务时间流为与之独立的,参数为H1的指数流.从第一个子系统离开的顾客进入 第二个子系统,其服务时间流是与前两个流独立的参数为2的指数流.假定H∧H2> 这时,第一个子系统有可逆分布,它的排队过程是空间齐次的单侧生灭过程,而且其转 移矩阵的每一行都趋于其可逆分布.于是不管什么初值,只要时间充分长,就可以认为可逆 性引理7.1的条件成立.由引理7.1,第一个子系统的输出过程(也就是第二个子系统的 输入过程)也是以λ为强度的 Poisson过程,并且第二个子系统也有同样的性质 2.简单的排队网络 假定服务网络系统设有n个服务点,每个服务点设置一条服务线,分别独立地服务.假 定在第(≤m)个服务点所需的服务时间为参数的指数流。令P=(P)为一个随机矩 阵,其中P在i≠j时表示:第i个服务点接受完服务后的顾客,转而再去第j个服务点的 概率.而p表示顾客在第i个节点(服务点)接受完服务后,离开此服务网络系统的概率.时 刻t在第个服务点的排队过程为X.定义x,=(X,…,X(),这个n维过程称为在此 服务网络系统中的排队过程.假定由系统外进入系统各个服务点的顾客流,是彼此相互独立 的,而且进入第个服务点的顾客流为参数x的指数流。再假定共比较大,以使每个服 务点上的排队过程是可逆的(在后面我们将会看到它们成立的条件) 由于顾客在各个服务点间有转移,所以进入第个服务点的实际强度(记为λ1)要比x0 大.由引理7.1,只要在第i个服务点的排队过程是可逆的,那么在时间充分长以后,在这个 服务点的输出流也应该是参数为1的指数流 记第j个节点(服务点接受到的外来顾客的时间间隔流为{70},而从节点i接受到 的顾客的时间间隔流为{r4”)}。由 Poisson过程的分流定理知道,T-en,而 且对于固定的k,T0),T)…,T相互独立.这使得在节点实际接受到的顾客的 时间间隔为 T0→)AT→
182 特别当 N =1时有 (1 ) 1 m l m l p = - , m m l l - = 1 EW . 同时也可得平均停留时间T ， 因为它是等待时间W 与服务时间的和. * 2. 3 序贯排队与排队网络系统 1. 简单的序贯排队模型 设排队系统由两个 M / M /1子系统串联而成. 设进入第一个子系统的顾客流为参数 l 的指数流, 服务时间流为与之独立的,参数为 m1的指数流. 从第一个子系统离开的顾客进入 第二个子系统, 其服务时间流是与前两个流独立的参数为 m2 的指数流. 假定 m1 Ù m2 > l . 这时, 第一个子系统有可逆分布, 它的排队过程是空间齐次的单侧生灭过程, 而且其转 移矩阵的每一行都趋于其可逆分布. 于是不管什么初值, 只要时间充分长, 就可以认为可逆 性引理７．１的条件成立. 由引理 7.1, 第一个子系统的输出过程(也就是第二个子系统的 输入过程)也是以l 为强度的 Poisson 过程, 并且第二个子系统也有同样的性质. 2．简单的排队网络 假定服务网络系统设有n 个服务点，每个服务点设置一条服务线，分别独立地服务．假 定在第i (i £ n) 个服务点所需的服务时间为参数 mi 的指数流。 令 P ( ) ij = p 为一个随机矩 阵，其中 ij p 在i ¹ j 时表示：第i 个服务点接受完服务后的顾客，转而再去第 j 个服务点的 概率．而 pii 表示顾客在第i 个节点（服务点）接受完服务后, 离开此服务网络系统的概率．时 刻t 在第i 个服务点的排队过程为 (i) Xt ．定义 ( , , ) (1) (n ) Xt Xt L Xt D = ，这个n 维过程称为在此 服务网络系统中的排队过程．假定由系统外进入系统各个服务点的顾客流，是彼此相互独立 的，而且进入第i 个服务点的顾客流为参数 (0) li 的指数流。 再假定 mi 比较大，以使每个服 务点上的排队过程是可逆的（在后面我们将会看到它们成立的条件）． 由于顾客在各个服务点间有转移，所以进入第i 个服务点的实际强度（记为 li ）要比 (0) li 大．由引理 7.1, 只要在第i 个服务点的排队过程是可逆的, 那么在时间充分长以后, 在这个 服务点的输出流也应该是参数为li 的指数流． 记第 j 个节点(服务点)接受到的外来顾客的时间间隔流为{ } (0 j) Tk ® ，而从节点 i 接受到 的顾客的时间间隔流为{ } (i j) Tk ® 。 由 Poisson 过程的分流定理知道， ij i p i j Tk l ~ exp ( ® ) . 而 且对于固定的k ， ( ) 1 (1 ) 1 (0 ) , , , n j k j k j Tk T T ® - ® - ® L 相互独立. 这使得在节点 j 实际接受到的顾客的 时间间隔为 ( ) 1 (1 ) 1 (0 ) n j k j k j Tk T T ® - ® - ® Ù ÙLÙ ij i i j l +å p l ~ exp (0) . (7.13)
于是顾客流的强度λ,应该满足流方程 (7.14) 这个网络排队过程转移速率矩阵Q较为复杂,但是Q的流向却可以简单表示为: (k…一1…一…,……人)(在,……“k+1…∴x) qk,…(……5)=1,q(…+1,(k…k,…A)=p 现在我们假定流方程的解{λ1,…λn)满足:λ1<H1,(i=1…,n)。那么仿照第6章中 的讨论,就可以得到Q有配称列兀=(…,丌4…k…A…),它是概率向量,其分量为 (7.16) 最后,用定理6.26就得到以Q为转移速率的,时间连续的 Markov链的转移矩阵P(m)满 足 P(t)→>1π,(t→∞) 并且遍历定理成立.由(7.16)可以看出,在各个服务点的排队过程是渐近地相互独立的 2.4M/M/∞排队系统 这时有∞条彼此独立地工作的服务线.排队过程X的转移速率矩阵为 -(+) (7.17) Nμ-(λ+N)元 它是互通的,具有可逆分布 而且也有 P(1) 下面我们进一步求x的分布P(1)=P(X1=k)的表达式 这时的 Master方程
183 于是顾客流的强度l j 应该满足流方程 ij i i l j = l j +å p l (0) . (7.14) 这个网络排队过程转移速率矩阵Q 较为复杂, 但是Q 的流向却可以简单表示为: ¬¾¾ ¾¾® - i i i n k k k m l ( , , 1, , ) L 1 L L ¬¾¾ ¾¾® j j i j n k k k k m l ( , , , , , ) 1 L L L (k1 ,L, ki ,L, k j + 1,L, kn )L, 即 k k k k k k i i n i n q( , , , ),( , , +1, , ) = l 1 L L 1 L L , k k k k k k i i n i n q( , , +1 , ),( , , , , ) = m 1 L L 1 L L . (7.15) 现在我们假定流方程的解{ , , ) l1 L ln 满足： ,(i 1, ,n) li < mi = L 。 那么仿照第 6 章中 的讨论，就可以得到Q 有配称列 p = ( , , ) ( , , , ) L p k1 L kiL k n L , 它是概率向量，其分量为 ÷ ÷ ø ö ç ç è æ - ÷ ÷ ø ö ç ç è æ = Õ= i i k i i n i k k k i i n m l m l p 1 1 ( , , , ) 1 L L . (7.16) 最后， 用定理 6.26 就得到以Q 为转移速率的，时间连续的 Markov 链的转移矩阵 P (t) 满 足 P (t) ® , (t ® ¥) T 1 p ， 并且遍历定理成立. 由(7.16)可以看出, 在各个服务点的排队过程是渐近地相互独立的. 2. 4 M／M／∞排队系统 这时有¥ 条彼此独立地工作的服务线. 排队过程 Xt 的转移速率矩阵为 Q ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç è æ - + - + - = O O O O O O m l m l m l m l l l ( ) ( ) N N , (7.17) 它是互通的, 具有可逆分布 p N N e ÷ ÷ ø ö ç ç è æ = - m m l l . (7.18) 而且也有 P t T t ¾ ¾®1 ®¥ ( ) p . 下面我们进一步求 Xt 的分布 p (t) P(X k ) k = t = 的表达式. 这时的 Master 方程
(P0'(D),P1'(1)…)=(P0(D),P1(1)2…)Q 的分量形式为 P0'(1)=-2P0(1)+{p,(t) (7.19) P(=k-4(1)-(2+k)P(1)+(k+1)k(D) 这组方程等价于X,的矩母函数 G(,2)=Ezx=∑P2(t)=2 满足如下的偏微分方程 t ∑p2"(t)2x=(x2-1(G-) +(-1))-(二-1)G=0 at 作变换G(t,)=e H(t,=),就简化为 H aH 两边乘以e,记函数对(H(t,-),(-1)e)关于(t,x)的 Jacobian行列式为 H,(z-1)e) (t,2),那么方程(7.22)就可改写成 a(H,(二-1)e-) 这就说明了H(t,)与(二-1)e函数相关.即存在一个函数h(x)使 H(1,)=h((=-1)e). (7.23) 设t=0时系统中的顾客数X0的分布为P(X0=k)=ak·那么 ,akz=G(0,-)=H (0,=)=h(二-1) 于是 h(二) a4(二+ 因此
184 ( '( ), '( ), ) p0 t p1 t L ( ( ), ( ), ) = p0 t p1 t L Q 的分量形式为 î í ì = - + + + = - + - + '( ) ( ) ( ) ( ) ( 1) ( ) '( ) ( ) ( ) 1 1 0 0 p t p t k p t k p t p t p t p t k k k k i l l m m l m . （７．１９） 这组方程等价于 Xt 的矩母函数 Xt G t z Ez D ( , ) = =å ¥ =0 ( ) k k pk t z （７．２０） 满足如下的偏微分方程: t G ¶ ¶ å ¥ = = 0 '( ) k k pk t z ( 1)( ) z G z G ¶ ¶ = - l - m . 即 t G ¶ ¶ ( 1) ) - ( - 1) = 0 ¶ ¶ + - z G z G m z l . （７．２１） 作变换 ( , ) ( , ) ( 1)(1 ) G t z e H t z t z e m m l - - - = , 就简化为 ( 1) = 0 ¶ ¶ + - ¶ ¶ z H z t H m . （７．２２） 两边乘以 t e -m , 记函数对 (H (t,z) , ( 1) ) t z e -m - 关 于 (t,z) 的 Jacobian 行列式为 ( , ) ( ,( 1) ) t z H z e t ¶ ¶ - -m , 那么方程（７．２２）就可改写成 0 ( , ) ( ,( 1) ) = ¶ ¶ - - t z H z e mt . （７．２２）＇ 这就说明了 H (t,z) 与 t z e -m ( -1) 函数相关. 即存在一个函数h(x) 使 H (t,z) (( 1) ) t h z e -m = - . （７．２３） 设ｔ＝０时系统中的顾客数 X0的分布为 ak P(X0 = k ) = . 那么 å ¥ k =0 k ak z = G(0,z) = H (0,z) = h(z - 1) . 于是 å ¥ = = + 0 ( ) ( 1) k k h z ak z . 因此
(t,=) a4(1+(二-1e-) (7.24) 显见G(L,x)的表达式完全依赖于初始资料G(0,z)的选取.当取G(0,)=z′时,我们把得 到的G(t,z)记为 ,)=∑P 由此可得下面的定理 定理7.4可逆M/M/∞系统排队过程的的转移函数为 1-e" P(=e (1 (-k) 于是 M4=-1(1-e-) Po/(1)=e 即当X0=1时,X,“C2ux 由此可见当t→>∞时x有极限分布exp,这就再 次求得了X的不变分布 [注1]以上的方法与结论可以推广到λ依赖于t的情形,只要假定λ(t)≤常数λ 这时有 t→ P(X,=k) 0 其中 A(s)a 即当t非常大的时候,排队过程X的分布与expM非常接近 [注2](成批顾客的排队系统) 上面的方法和结论,还可以推广到顾客有成批到达的情形.假定顾客在参数为A的 Poisson过程的跳跃 时刻上到达,但到达的顾客是成批的,即到达人数U是一个非负整值的随机变量,其母函数记为 B()=∑b2,(b=P(U=k) (7.27) 又假定服务时间仍为参数为的独立同分布的指数分布.那么用与推导M/M/∞系统的排队过程的矩
185 G(t,z) = å ¥ = - - - + - - 0 ( 1)(1 ) (1 ( 1) ) k t k k z e e a z e tt m m l m . （７．２４） 显见G(t,z) 的表达式完全依赖于初始资料 G(0,z) 的选取. 当取 i G(0,z) = z 时, 我们把得 到的G(t,z) 记为 å ¥ = D = 0 ( , ) ( ) j j i ij G t z p t z . 由此可得下面的定理 定理７.４ 可逆M / M / ¥ 系统排队过程的的转移函数为 ( )! (1 ) ( ) 2 0 (1 ) j k e e p t e C k t t i j k j k i j k i k e ij t - - ÷ ÷ ø ö ç ç è æ = - - + - - Ù = - - å - m m m l m l m . （７．２５） 于是 ! [ (1 )] ( ) (1 ) 0 j e p t e t j e j tt m m l m l m - - - - = - . （７．２６） 即 当 X0 = 1时, (1 ) ~ exp t e Xt m m l - - . 由此可见当t ® ¥ 时 Xt 有极限分布 m l exp , 这就再一 次求得了 Xt 的不变分布. [注 1] 以上的方法与结论可以推广到λ依赖于 t 的情形,只要假定 λ(ｔ)£常数λ0． 这时有 0 ! ( ) lim ( ) ( ) =÷ ÷ ø ö ç ç è æ D = - -L ®¥ k t P X k e k t t t , 其中 ò L = t t s ds 0 ( ) 1 ( ) l m . 即当t 非常大的时候, 排队过程 Xt 的分布与 ( ) exp D t 非常接近. [注 2] (成批顾客的排队系统) 上面的方法和结论，还可以推广到顾客有成批到达的情形. 假定顾客在参数为λ的 Poisson 过程的跳跃 时刻上到达, 但到达的顾客是成批的, 即到达人数u 是一个非负整值的随机变量, 其母函数记为 å ¥ = = = = 0 ( ) ,( ( )) k k k B z bk z b P u k D . （７．２７） 又假定服务时间仍为参数为 m 的独立同分布的指数分布. 那么用与推导 M / M / ¥ 系统的排队过程的矩