龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,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 过程, 而且排队过程是可逆的平稳过程