龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第7章排队过程简介 排队过程的描述 排队系统 排队模型是一种包含更新过程与生灭过程机制的,但是更为复杂的概率模型. 简单的排队过程是在两个相互独立的流作用下形成的,其中一个是要求服务的”顾客 流”,这时假定顾客是一个一个地到达的,其时间间隔组成一个更新流.另一个是当顾客进 入服务线后,接受服务的服务时间流.服务不一定一个接着一个地发生,在两次服务之间 可能有空隙,所以虽然各顾客接受的服务独立同分布的时间流.但是它不具有更新流的特 点.这些服务空隙成为排队系统的闲期.两个闲期之间的随机时间称为忙期.平均闲期长度 与平均忙期长度是排队系统设计中的重要指标我们如果无视闲期的存在,而虚拟地把服务 流一个接着一个接成更新流,那么,由服务时间流可以生成一个虚拟的更新过程 最简单的排队系统只有一条服务线,采取先到的顾客先接受服务的原则,并且有足够大 的空间(无限制)容纳等待服务的顾客.在时刻t等待服务与正接受服务的顾客数,是一个取 非负整值的随机变量,记为X整值随机过程{Xx,:≥0}称为排队过程,它是连续时间状 态离散的随机过程.顾客流与服务时间流都是 Poisson流(即指数流)的排队过程是最简单的 排队过程.由定理6.12知道,只有此种情形的排队过程才可能是连续时间的 Markov链 排队模型广泛地出现在各个应用领域,如服务系统,交通运输,电脑中信息流的存取 通信系统,商品物流等等. 1.2排队系统的一般框图,输入过程与输出过程 排队系统的一般框图如下: 输入过程(顾客流)「→排队过程X→输出过程(离去的顾客流) 值得注意的是,输入过程就是顾客流生成的更新过程,但是输出过程却不是服务时间流生成 的虚拟的更新过程.因为输出过程是输入过程与服务时间流共同作用的结果 记输入过程为N(即在(0中到达的顾客数),输出过程为N,(即在(0中离 开系统的顾客数).那么我们有 X-X=N (7.1 1.3可逆性引理 如果顾客流是 Poisson流,且在某个随机的初值x。时排队过程是可逆的平稳过程,即 对于任意T>0,随机过程{X,=X,:1≤7}与随机过程{X,:≤T}(前者称为后者的 逆过程)有相同的有限维分布族,则输出过程有如下的可逆性引理 引理7。1(可逆性引理)(具 Poisson输入的可逆排队系统的输出过程) 设排队系统的输入过程是强度为λ的 Poisson过程,而且排队过程是可逆的平稳过程
176 龚光鲁，钱敏平著 应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第 7 章 排队过程简介 1. 排队过程的描述 1. 1 排队系统 排队模型是一种包含更新过程与生灭过程机制的，但是更为复杂的概率模型. 简单的排队过程是在两个相互独立的流作用下形成的, 其中一个是要求服务的 ”顾客 流”, 这时假定顾客是一个一个地到达的, 其时间间隔组成一个更新流. 另一个是当顾客进 入服务线后, 接受服务的服务时间流． 服务不一定一个接着一个地发生，在两次服务之间 可能有空隙,所以虽然各顾客接受的服务独立同分布的时间流. 但是它不具有更新流的特 点．这些服务空隙成为排队系统的闲期. 两个闲期之间的随机时间称为忙期. 平均闲期长度 与平均忙期长度是排队系统设计中的重要指标.我们如果无视闲期的存在，而虚拟地把服务 流一个接着一个接成更新流，那么，由服务时间流可以生成一个虚拟的更新过程． 最简单的排队系统只有一条服务线, 采取先到的顾客先接受服务的原则, 并且有足够大 的空间(无限制)容纳等待服务的顾客. 在时刻t 等待服务与正接受服务的顾客数, 是一个取 非负整值的随机变量, 记为 Xt .整值随机过程{X : t ³ 0} t 称为排队过程, 它是连续时间状 态离散的随机过程. 顾客流与服务时间流都是Poisson流(即指数流)的排队过程是最简单的 排队过程. 由定理 6.１２知道, 只有此种情形的排队过程才可能是连续时间的 Markov 链. 排队模型广泛地出现在各个应用领域, 如服务系统, 交通运输, 电脑中信息流的存取, 通信系统, 商品物流等等. 1. 2 排队系统的一般框图,输入过程与输出过程 排队系统的一般框图如下: 输入过程(顾客流) ® 排队过程 Xt ® 输出过程(离去的顾客流) 值得注意的是，输入过程就是顾客流生成的更新过程, 但是输出过程却不是服务时间流生成 的虚拟的更新过程. 因为输出过程是输入过程与服务时间流共同作用的结果. 记输入过程为 (in) Nt ( 即在(0,t]中到达的顾客数), 输出过程为 (out) Nt ( 即在(0,t]中离 开系统的顾客数). 那么我们有 ( ) ( ) 0 out t in Xt - X = Nt - N . (7.1) 1. 3 可逆性引理 如果顾客流是 Poisson 流，且在某个随机的初值 X0时排队过程是可逆的平稳过程，即 对于任意T > 0, 随机过程{ : } ^ ( ) X XT t t T T t = - £ D 与随机过程{X :t T} t £ （前者称为后者的 逆过程）有相同的有限维分布族，则输出过程有如下的可逆性引理: 引理 7。1 （可逆性引理） (具 Poisson 输入的可逆排队系统的输出过程) 设排队系统的输入过程是强度为l 的 Poisson 过程, 而且排队过程是可逆的平稳过程
则排队系统的输出过程也是强度为λ的 Poisson过程. 证明由于{X,:≤T}每次增加1都发生在TnT时刻,其中{n}为参数为λ的指 数流的累次到达时刻,有可逆性可知{X;:【≤7}也应具有同样的性质.但是 X:t≤T}增加1的时刻正是{X,:1≤7}减少1的时刻,可见{X,t≤T}减少1的时 刻与{τn}同分布,也就是{X,:I≤T}减少1的时刻也是参数为λ的 Poisson流 [注]MMN排队系统(参见§2中的(2.2)段)是满足可逆性引理的典型例子. 最简单排队过程— Markov排队过程 2.1最简单的排队过程-M/M/系统 假定服务系统只有一个”服务员”,顾客到达的时间间隔相互独立同分布,且服从分布 exp,而每个顾客接受服务的时间长度也相互独立同分布,服从expa分布,并且与排队 系统的输入流相互独立.这种系统在排队论中记为M/M/Ⅰ系统,其中第一个”M”表 顾客流服从指数分布,第二个”M”表示服务时间长度流服从指数分布,最后一个数字 “1”表示只有1个“服务员”) 记在(0,]中到达的顾客数目为N2,则它是强度为λ的 Poisson过程.如果在t时刻的 排队过程X1≠0,则系统不在闲期,此时接受了服务的顾客的个数(我们将它记为L1)在 很短的时间内,是以强度为μ的 Poisson过程的规律相增加的.因此,当X;≠0且h很 小时,在(1,1+h]中接受了服务的顾客个数L满足 P(Lb≥2)=o(h),P(Lh=1)=h+o(h),P(L=0)=(1-h)+o(h).(7.2) (这里需要警觉的是:接受了服务的顾客个数L,并不总是顾客接受服务的时间长度流对 应的 Poisson过程M, 这是因为当队伍空时就不会出现服务.虽然服务流的计数过程 N{m):t≥0}总是与顾客流的计数过程{Nm:t≥0}独立的,但是{L1:t≥0}因为受排 队过程{X1t≥0)是否处于忙期的影响,从而也受{Nm:t≥0}的影响.所以,要想用服 务流的计数过程N来描述接受了服务的顾客个数,必须满足:X,≥服务线的数目, 且h很小 此系统的排队过程X的状态空间为S={0,1,…,n,…}·下面考察排队过程在(1+h
177 则 排队系统的输出过程也是强度为l 的 Poisson 过程. 证明 由于{X :t T} t £ 每次增加 1 都发生在t n ÙT 时刻, 其中{ }n t 为参数为l 的指 数流的累次到达时刻 , 有可逆性 可 知 { : } ( ) ^ X t T T t £ 也 应具有同样的性质 . 但 是 { : } ^ ( ) X t T T t £ 增加 1 的时刻正是{X :t T} t £ 减少 1 的时刻, 可见{X :t T} t £ 减少 1 的时 刻与{ }n t 同分布. 也就是{X :t T} t £ 减少 1 的时刻也是参数为l 的 Poisson 流. [注] M/M/N 排队系统（参见§2 中的(2. 2)段）是满足可逆性引理的典型例子. 2. 最简单排队过程— Markov 排队过程 2. 1 最简单的排队过程-- M / M /1系统 假定服务系统只有一个 ”服务员”, 顾客到达的时间间隔相互独立同分布, 且服从分布 l exp , 而每个顾客接受服务的时间长度也相互独立同分布, 服从 m exp 分布，并且与排队 系统的输入流相互独立. 这种系统在排队论中记为 M / M /1系统, 其中第一个 ”M ”表 示顾客流服从指数分布, 第二个 ”M ”表示服务时间长度流服从指数分布, 最后一个数字 “1”表示只有 1 个 “服务员” ) 记在(0,t]中到达的顾客数目为 Nt , 则它是强度为l 的 Poisson 过程. 如果在t 时刻的 排队过程 Xt ¹ 0 , 则系统不在闲期， 此时接受了服务的顾客的个数(我们将它记为 Lt )在 很短的时间内, 是以强度为 m 的 Poisson 过程的规律相增加的. 因此, 当 Xt ¹ 0 且h 很 小时, 在(t,t + h] 中接受了服务的顾客个数 Lh 满足 P(L 2) o(h) h ³ = , P(L 1) h o(h) h = = m + , P(L 0) (1 h) o(h) h = = - m + . (7.2) (这里需要警觉的是: 接受了服务的顾客个数 Lt , 并不总是顾客接受服务的时间长度流对 应的 Poisson 过程 (serve) Nt , 这是因为当队伍空时就不会出现服务. 虽然服务流的计数过程 { : 0} ( ) N t ³ serve t 总是与顾客流的计数过程{ : 0} ( ) N t ³ in t 独立的，但是{L : t ³ 0} t 因为受排 队过程{X : t ³ 0) t 是否处于忙期的影响, 从而也受{ : 0} ( ) N t ³ in t 的影响. 所以, 要想用服 务流的计数过程 (serve) Nh 来描述接受了服务的顾客个数, 必须满足: Xt ³ 服务线的数目, 且h 很小. 此系统的排队过程 Xt 的状态空间为 S = {0,1,L, n,L} . 下面考察排队过程在(t,t + h]
中的转移情况与例6.36类似,对转移速率q、(i≠我们有如下的流向图 0 由此得到排队过程X是转移速率矩阵为 (λ+p) Q λ+p) x1是连续时间的 Markov链.即是具有常数生长率λ与常数死亡率的单侧生灭过程.当 μ>λ时,它有可逆分布,此可逆分布是参数为一的几何分布(参见下一段) K=(o,…,丌n,…),丌n=(1--)-) M/M/1可逆系统在稳定时的平均排队长度,停留时间分布与服务员的等待时间的分布 当μ>λ时,M/M/1系统为可逆的,在系统达到稳定时有 (1)平均排队长度为 λ、.d L 2)停留时间T的分布为exp=x 为了验证这个事实,我们用随机变量s来记排队系统达到稳定时的队伍长度.那么 个顾客进入系统后的停留时间T是随机变量.当排队系统达到稳定时,P(T≤l|s=k) 是k+1个顾客(系统中的k个顾客与进入系统的顾客)连续接受服务的时间的分布函数,也 就是k+1个参数为的独立的指数分布随机变量的和的分布函数,故而应该是r(k+1,) 的分布函数.于是 P(T≤1)=∑P(T<ts=k)P(s=k)
178 中的转移情况. 与例６．３６类似, 对转移速率q ,(i j) ij ¹ 我们有如下的流向图: L L ¬¾¾ ¾® ¬¾¾ ¾® ¬¾¾ ¾® ¾® ¾® m l m l m l m l 0 1 n ． 由此得到排队过程 Xt 是转移速率矩阵为 Q ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ - + - + - = O O O m l m l m l m l l l ( ) ( ) . (7.3) Xt 是连续时间的 Markov 链． 即是具有常数生长率 l 与常数死亡率的单侧生灭过程. 当 m > l 时, 它有可逆分布, 此可逆分布是参数为 m l 的几何分布(参见下一段) k ( , , , ) = p 0 L p n L , n n (1 )( ) m l m l p = - . (7.4) M/M/1 可逆系统在稳定时的平均排队长度, 停留时间分布与服务员的等待时间的分布 当 m > l 时, M / M /1 系统为可逆的, 在系统达到稳定时有 (1) 平均排队长度为 = å = å - k k k k L k k (1 )( ) m l m l p m l l m l m l m l - = - = - dx x x= d )] 1 1 (1 )[ ( . (7.5) (2) 停留时间T 的分布为 m-l exp 为了验证这个事实，我们用随机变量V 来记排队系统达到稳定时的队伍长度．那么 ÷ ÷ ø ö ç ç è æ - L - L L L 1 ( ) (1 ) 0 ~ m l m l m V l n n . 一个顾客进入系统后的停留时间T 是随机变量. 当排队系统达到稳定时, P(T £ t | V = k ) 是k +1个顾客 (系统中的k 个顾客与进入系统的顾客)连续接受服务的时间的分布函数, 也 就是k +1个参数为 m 的独立的指数分布随机变量的和的分布函数, 故而应该是G(k +1,l) 的分布函数. 于是 ( ) ( | ) ( ) 0 P T t P T t k P k k £ = å < = = ¥ = V V
∑∫“,se“1--x)"=(1-)e=(76 k=00 即T~exp-x·这个结论非常符合直观的印象 (3)服务员的等待时间间隔S的分布为expx 事实上,服务员的等待时间的间隔S,是一个顾客离开系统时与前面的一个顾客离开系 统的时间的差,它也是随机变量.设前面的一个顾客离开系统时系统中的顾客数为s.那么 在排队系统达到稳定时s与5同分布这时P(S≤s>0)应该是exp的分布函数,而 P(S≥l|s=0)应是独立的expx随机变量与exp随机变量的和的分布函数,即 P(S≤ls'=0)= (1-e)=1 于是由全概率公式得到 P(S≤D)=P(S≤|s'>0)PGs'>0)+P(S≤t|s'=0)P(s'=0 可见S~exp 2.2N个服务员的简单排队过程一M/M/N系统 1.转移速率矩阵 假定服务系统有N个”服务员”,他们分别独立地服务.顾客到达的间隔仍为参数 的独立指数分布,且每个顾客接受服务的时间长度仍服从与之独立的,参数为的独立指 数分布.这种系统在排队理论中记为M/M/N系统,前两个字母表示指数分布,最后一个 数字“N”表示有N个“服务员” 排队过程x,的状态空间仍是S={01,…,n,…}.可以用如下的流向图来分析转移速 率qn,(i≠ ((n +1)AN)u 由此流向图可以得到
179 k s n t k k s e ds k (1 )( ) ! 1 0 0 m l m m m l = - - ¥ + = å ò e ds s t ( ) 0 ( ) m l m l - - = - ò . (7.6) 即 m -l T ~ exp . 这个结论非常符合直观的印象. (3) 服务员的等待时间间隔S 的分布为 l exp ． 事实上，服务员的等待时间的间隔 S , 是一个顾客离开系统时与前面的一个顾客离开系 统的时间的差, 它也是随机变量．设前面的一个顾客离开系统时系统中的顾客数为V ' . 那么 在排队系统达到稳定时V '与V 同分布. 这时 P(S £ t | V ' > 0) 应该是 m exp 的分布函数, 而 P(S ³ t | V ' = 0) 应是独立的 l exp 随机变量与 m exp 随机变量的和的分布函数. 即 P(S £ t | V ' = 0) e e duds u s u t s ( ) 0 0 - - - = × × ò ò l m l m e e ds s s t ( 1) ( ) 0 - - = × - - ò m m l m l m l (1 ) (1 ) t t e e l m m l l m l m - × - - - - - - = ( ) 1 1 t t e e - × - × × - × - = - l m m l m l . 于是由全概率公式得到 P(S £ t) = P(S £ t | V '> 0)P(V '> 0) + P(S £ t | V '= 0)P(V ' = 0) = - + - m m l (1 ) t e ( )](1 ) 1 [1 m l m l m l l m × - × - - - - ×t - ×t e e t e - × = - l 1 . (7.7) 可见 l S ~ exp . 2. 2 N 个服务员的简单排队过程 — M / M / N 系统 １. 转移速率矩阵 假定服务系统有 N 个 ”服务员”, 他们分别独立地服务. 顾客到达的间隔仍为参数l 的独立指数分布, 且每个顾客接受服务的时间长度仍服从与之独立的, 参数为 m 的独立指 数分布. 这种系统在排队理论中记为 M / M / N 系统, 前两个字母表示指数分布, 最后一个 数字 “N ”表示有 N 个 “服务员” . 排队过程 Xt 的状态空间仍是 S = {0,1,L, n,L} . 可以用如下的流向图来分析转移速 率q ,(i j) ij ¹ : L L ¬¾¾¾¾ ¾® ¬¾ ¾¾ ¾® ¬¾¾ ¾® ¾® ¾® Ù + Ù m l m l m l m l 2 ( ) (( 1) ) 0 1 n N n N n 。 由此流向图可以得到
-(λ+p) Q (n∧N)-[(n∧N)+A]元 它是互通的,且具有配称列μ=(40,12…),其中 (n∧N) (k∧N) 于是存在可逆分布当且仅当λ1丌 在达到稳定时,排队系统处于闲期的概率为丌。,处于忙期的概率为1-兀。 由此我们也可以得到,在μ>λ时M/M/N系统达到稳定时的平均排队长度 2.可逆M/M/N系统的特性 命题7.2若M/M/N排队过程的初值为可逆分布(或者任意初值,并经过时间充分 长后),那么 (1)正在系统中的人数与输出过程的过去情况相互独立. (2)给定顾客在此系统中所停留的时间,与他离开前的输出流独立 证明(1)输出过程的过去就是逆过程的输入过程的将来,这正是指数流的将来.由 指数流的性质,它应与在系统中的人数独立 (2)由引理7.1,逆过程的输入过程是指数流.再用(1),逆过程在进入系统时刻 以后的输入流就与已进入的顾客在系统中的停留时间独立.这就是说,顾客离开系统前的输 出流与他在系统中的停留时间独立 3.可逆M/M/N系统在稳定时的平均等待时间 设μ>λ.在达到稳定后(时间充分长,致使系统近似平稳),对于在时刻t来到排队系统 的顾客的平均等待时间,可以分析如下.由于排队系统平稳,对于在系统中的顾客(包括在 排队的与正在接受服务的顾客)数x,应有P(x,=1)=丌1记时刻t来到的顾客等待时间
180 Q ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ Ù - Ù + - + - = O O O O O m l l m l m l l l ( ) [( ) ] ( ) n N n N . (7.8) 它是互通的, 且具有配称列 m ( , , ) = m0 m1 L , 其中 m0 = 1, 1 1 1 ( ) 1 ( ) + = - ÷ ÷ ø ö ç ç è æ Ù = Ù = Õ n n k n n k N n N m l m m l m . (7.9) 于是存在可逆分布当且仅当 l l 时 M / M / N 系统达到稳定时的平均排队长度. 2. 可逆 M / M / N 系统的特性 命题 7．2 若M / M / N 排队过程的初值为可逆分布(或者任意初值, 并经过时间充分 长后), 那么 (1) 正在系统中的人数与输出过程的过去情况相互独立. (2) 给定顾客在此系统中所停留的时间，与他离开前的输出流独立. 证明 (1) 输出过程的过去就是逆过程的输入过程的将来, 这正是指数流的将来．由 指数流的性质，它应与在系统中的人数独立. (2) 由引理７.１，逆过程的输入过程是指数流. 再用（１）, 逆过程在进入系统时刻 以后的输入流就与已进入的顾客在系统中的停留时间独立. 这就是说, 顾客离开系统前的输 出流与他在系统中的停留时间独立. 3. 可逆 M / M / N 系统在稳定时的平均等待时间 设m > l . 在达到稳定后(时间充分长,致使系统近似平稳)，对于在时刻 t 来到排队系统 的顾客的平均等待时间，可以分析如下. 由于排队系统平稳, 对于在系统中的顾客(包括在 排队的与正在接受服务的顾客)数 Xt ，应有 t i P(X = i) = p . 记时刻 t 来到的顾客等待时间
为W.于是当i0)=r,_M (7.11) 2#平均等待时间为 NA EW=」P(W>s)kds= (7.12)
181 为W . 于是当i = 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)满足:λ11π,(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 / ¥ 系统的排队过程的矩