《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第7章 排队过程

龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,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) 于是存在可逆分布当且仅当λ<μ.在条件成立时,令 (7.10) NN 那么兀就是可逆分布.因此排队过程x是连续时间的 Markov链,在λ<μ时其转移矩阵 P(t)有极限,且 P(t →>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 < m . 在条件成立时, 令 p å å ¥ = + = + = 0 0 ( ) 1 ! 1 ( ) ! 1 1 j N j j k N k k N N m l m l m . (7.10) 那么p 就是可逆分布. 因此排队过程 Xt 是连续时间的 Markov 链，在l < m 时其转移矩阵 P (t) 有极限, 且 P p t T t ¾ ¾®1 ®¥ ( ) . 在达到稳定时，排队系统处于闲期的概率为p 0 , 处于忙期的概率为 1- p 0 . 由此我们也可以得到，在 m > 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 来到的顾客等待时间