P(T≥+12小)P(T≥sT2s+)eeN=P(T20) 由结果知,此条件概率与s无关。这说明无论在泊松过程的什么时刻,即无 论取哪一时刻为起点,考察至下一位顾客到达所经过的时间,其概率(即 P(T≥s+17≥))与此时刻之前的最后一位顾客是什么时候到达的无关。它和 顾客相继到达的间隔时间都服从相同参数的负指数分布。 还可以指出的是,能满足无记忆性P(T≥s+1{T≥s)=P(T≥1)的分布,也 只能是负指数分布 下面讨论爱尔朗( Erlang)分布。 爱尔朗分布的密度函数是 ·() P()={(k-1) t>0 <0 其中参数>0,k称为阶数(k=0,12,)。 当k=1时,则爱尔朗分布也就是负指数分布。若随机变量r服从k阶爱尔朗 分布,则的期望值和方差分别为 E(r)=K, D()=k 可以证明,如果552,…5是k个相互独立具有相同的负指数分布(参数为 μ)的随机变量,则随机变量r=5+52+…+5服从k阶爱尔朗分布 在排队论中,常把顾客到达间隔时间及接受服务时间与爱尔朗分布联系起 来。如果顾客要连续接受串联的k个服务台服务,各服务台的服务时间相互独立, 且服从相同的负指数分布(参数为),那么顾客被这k个服务台服务完总共所 需的时间就服从爱尔朗分布。这里应说明的是在顾客接受连续的服务时,只有当 k个服务台都完成了对某个顾客的服务之后,下一个顾客才能进入这个串联服务 系统 913生灭过程 生灭过程也是一种马尔柯夫过程。在排队论中很多排队过程和这个过程相 仿。我们特别关心生灭过程在统计平衡时反映出来的稳态概率,并直接把这种稳 态概率应用于建立各种排队模型。 1.生灭过程的定义 一堆细菌,随时间推移,有的分裂为两个,有的死亡,经过一段时间之后, 细菌变为多少?这种细菌的分裂与死亡的过程就是典型的生灭过程的例子。设每 个细菌在△t时间内分裂成两个细菌的概率为A△r+0△n);而在△t时间内死亡
( ) ( , ) ( ) ( ) s t t s P T s T s t e P T s t T s e P T t P T s e λ λ λ − + − − ≥ ≥ + ≥ + ≥ = = = = ≥ ≥ ( ) 由结果知，此条件概率与 无关。这说明无论在泊松过程的什么时刻，即无 论取哪一时刻为起点，考察至下一位顾客到达所经过的时间，其概率（即 s P T( ≥ s +t T ≥ s)）与此时刻之前的最后一位顾客是什么时候到达的无关。它和 顾客相继到达的间隔时间都服从相同参数的负指数分布。 还可以指出的是，能满足无记忆性 P T( ≥ s +t T ≥ s) = P T( ≥t) 的分布，也 只能是负指数分布。 下面讨论爱尔朗（Erlang）分布。 爱尔朗分布的密度函数是 1 ( ) ( ) ( 1)! 0 k t t e p t k µ µ µ − − ⋅ = − t (9-12) 0 t 0 ≥ < 其中参数µ > 0，k 称为阶数( 0 k = ,1,2,⋅⋅⋅) 。 当k 时，则爱尔朗分布也就是负指数分布。若随机变量τ 服从 阶爱尔朗 分布，则 =1 k τ 的期望值和方差分别为 2 ( ) , ( ) k E D τ τ µ µ = = k t (9-13) 可以证明，如果ξ ξ 是 个相互独立具有相同的负指数分布（参数为 ）的随机变量，则随机变量 服从 阶爱尔朗分布。 1 2 , , , k ⋅⋅⋅ ξ k µ τ ξ1 2 k = +ξ +⋅⋅⋅+ξ k 在排队论中，常把顾客到达间隔时间及接受服务时间与爱尔朗分布联系起 来。如果顾客要连续接受串联的 个服务台服务，各服务台的服务时间相互独立， 且服从相同的负指数分布（参数为 ），那么顾客被这 个服务台服务完总共所 需的时间就服从爱尔朗分布。这里应说明的是在顾客接受连续的服务时，只有当 个服务台都完成了对某个顾客的服务之后，下一个顾客才能进入这个串联服务 系统。 k µ k k 9.1.3 生灭过程 生灭过程也是一种马尔柯夫过程。在排队论中很多排队过程和这个过程相 仿。我们特别关心生灭过程在统计平衡时反映出来的稳态概率，并直接把这种稳 态概率应用于建立各种排队模型。 1. 生灭过程的定义 一堆细菌，随时间推移，有的分裂为两个，有的死亡，经过一段时间之后， 细菌变为多少？这种细菌的分裂与死亡的过程就是典型的生灭过程的例子。设每 个细菌在+t 时间内分裂成两个细菌的概率为λ+t +0(+ )；而在+t 时间内死亡
的概率为1△+0△n),各个细菌在任一时间内分裂或死亡都是相互独立的。若 将细菌的分裂或死亡都看成是随机事件,那么在△t时间内发生两个时间的概率 等于下面三者之一:(A△t+0(△)2,(△t+0(△n),(A△r+0A)(p△r+0(△r) 所以在△t时间内发生两个或两个以上事件的概率为0△)。又设在时刻t有i个 细菌,则在时刻t+△有i+1个细菌的概率为入△r+0(△n),在时刻t+△t内有 i-1个细菌的概率为△t+0(△)。用(1)表示这堆细菌在时刻t的个数,并考 虑在[0,T)时间内细菌数的变化情况。因为对每个固定的t,ξ()都是随机变量, 故{()p∈[07)为一个随机过程,又因为它具有无后效性,故也是一个马尔柯 夫过程,把上述细菌分裂和死亡的过程称为生灭过程。 定义:设()p∈[0r)为一个随机过程,随机变量()的取值集合为 I=0,1,2,…,m}(或可列集Ⅰ={0,1,2…}),称此集合为状态集,设在时刻t时 (1)=j,那么在时刻t+△时,(t+△)=j+1的概率为入△r+0△),其中 入>0为与t无关的常数:在时刻t+△r时,(+△n)为/中其它元素的概率为 0(△)。满足上述随机过程()∈[0,m)称为生灭过程。 从上面的定义来看,如果把状态的变化理解为排队系统顾客的到达和离去, 则在时间增量△t内,只会有一个到达,或有一个离去,或既无到达也无离去(此 种情况的概率为1-入,△t-p1△t-0△n)),除此以外的其他到达、离去情况认为 是不可能发生的。并且,在△t内到达一个顾客的概率和△t的长短有关,而与 起始时刻t无关;到达一个的概率还与t时刻的顾客到达数j有关(因入与j有 关),而和t时刻以前的状态无关。同理,可进行△t时间内离开一个顾客的概率 情况分析 2.生灭过程的稳态概率 进一步考察生灭过程中时间T=+∞的情况。对生灭过程我们更关心的是极 imP(O)=八)。可以证明下面的定理。 定理3令 A1A2"'Ai 并设生灭过程()20的状态集为=0,2,…,m或=012…},那么, 当下列条件 丌;<+ 6入r 满足时,对于任意正数s和任意j∈l,i∈I,都有IimP((1)=j)= imP((s+1)=(s)=1)=P>0。当状态集为有限集/={01,2,m时
的概率为µ ，各个细菌在任一时间内分裂或死亡都是相互独立的。若 将细菌的分裂或死亡都看成是随机事件，那么在+ 时间内发生两个时间的概率 等于下面三者之一：( 。 所以在+ 时间内发生两个或两个以上事件的概率为0( 。又设在时刻t 有i 个 细菌，则在时刻t t 有 个细菌的概率为λ ，在时刻 内有 个细菌的概率为µ 。用 表示这堆细菌在时刻t 的个数，并考 虑在 时间内细菌数的变化情况。因为对每个固定的t ， 都是随机变量， 故 +t +0(+ ) λ t ++ i ) t t t 2 2 )) ,( + + + + t t + + 0( )) ,(µ+ + t t 0( λ λ +t +0( ))⋅(µ+t +0(+ )) +t) i +1 0( ) i t +t t ++t +t t +0(+ ) ξ(t) ξ(t) i−1 [0,T { ( 为一个随机过程，又因为它具有无后效性，故也是一个马尔柯 夫过程，把上述细菌分裂和死亡的过程称为生灭过程。 ξ t t ) ∈[0,T)} ξ t t ) ∈ 2, , } [0,T)} ξ( )t I {0,1, ⋅⋅⋅ m j t = ξ( )t λj > I ={0,1,2,⋅⋅⋅⋅⋅⋅} ++t ξ( ) t t + = + j 0( ) j +t + +t t ++t ) = 0 +1 (t t ++ I 0(+t) ξ t t ) ∈[0,T)} 0( ) j j − − λ + + t t µ − +t t t t t t j j j t P t( ) = t = +∞ li T=+ m (ξ ∞ j) 0 1 0 1 2 1, j j j λ λ λ π π µ µ µ ⋅⋅⋅ = = ⋅⋅⋅ j = ,2,⋅⋅⋅) ξ t t ) ≥ 0} I ={0,1,2,⋅⋅⋅,m} I ={0,1,2,⋅⋅⋅} 0 0 1 , j j j j j π λ π ∞ ∞ = = ∑ ∑ < +∞ = + s ∞ j ∈ I i, ∈ I lim ( ( ) ) t P t ξ j →+∞ = = limt→+∞ P s (ξ ξ ( + =t) j (s) = i) = 0 Pj > I ={0,1,2, m} 定义：设{ ( 为一个随机过程，随机变量 的取值集合为 （或可列集 ），称此集合为状态集，设在时刻t 时 ，那么在时刻t 时， 的概率为λ ，其中 为与 无关的常数；在时刻 时，ξ 为 中其它元素的概率为 。满足上述随机过程{ ( 称为生灭过程。 从上面的定义来看，如果把状态的变化理解为排队系统顾客的到达和离去， 则在时间增量+ 内，只会有一个到达，或有一个离去，或既无到达也无离去（此 种情况的概率为1 ），除此以外的其他到达、离去情况认为 是不可能发生的。并且，在+ 内到达一个顾客的概率和+ 的长短有关，而与 起始时刻 无关；到达一个的概率还与 时刻的顾客到达数 有关（因λ 与 有 关），而和 时刻以前的状态无关。同理，可进行+ 时间内离开一个顾客的概率 情况分析。 2. 生灭过程的稳态概率 进一步考察生灭过程中时间T 的情况。对生灭过程我们更关心的是极 限 。可以证明下面的定理。 定理 3 令 ( 1 并设生灭过程{ ( 的状态集为 或 ，那么， 当下列条件 满足时，对于任意正数 和任意 ，都有 。当状态集为有限集 ⋅⋅⋅, 时
Po P,=P0 P-1J=1,2,…,m 当状态集为无限集Ⅰ={0,1,}时 Po 丌 P=mB÷4 我们称P(=012…)为生灭过程在统计平衡时的概率,或称为稳态概率 对于生灭过程,因为时刻t时状态为j的概率分布P((1)=j)j∈I,将随时 间t的变化而变化,称之为瞬态解。瞬态解是很难求出的,即使求出来也难以利 用。因此,在实际应用中,我们更关心的是稳态概率P,j∈I。稳态概率的含义 是说,当运行时间t无限长时,状态的概率分将不随时间而变化,此时状态为j 的概率P是一个常数。需要指出,虽然在理论上由定理3知,生灭过程需经无限 长的时间才会进入稳态。但在实际应用中,对大多数问题来说,相应的生灭过程 总会很快达到稳态,不需要等到t→+∞之后 9.2一般排队系统结构 921排队模型结构 排队系统(或称为服务系统)可用于描述排队情况。即顾客为了获得某种服 务而到达服务台;若服务员在忙,顾客不能立即获得服务而又被允许排队等待, 则加入等待队列;获得服务之后则立即离开系统。整个过程如图9-1所示。 实际上每个具体的排队系统可能有所不同,但一般的排队系统都具有三个要 素,这就是输入过程;排队规则;服 务机构。由这三个要素便可以构造出 一个一般排队系统的结构模型。并由到达 此得到描述系统运行情况的数学模 等待线 服务台 型。下面对这三个要素再加以具体的 讨论。 图 1.输入过程
1 0 0 ( )j j p π ∞ − = = ∑ 1 0 1 j j j j j p p p λ π µ − = = − j =1,2,⋅⋅⋅,m 当状态集为无限集 I ={0,1,⋅⋅⋅}时 1 0 1 ( )j j p π ∞ − = = ∑ 1 0 1 j j j j j p p p λ π µ − = = − j =1,2,⋅⋅⋅ 我们称 P j j( 0 = ,1,2,⋅⋅⋅)为生灭过程在统计平衡时的概率，或称为稳态概率。 对于生灭过程，因为时刻t 时状态为 j 的概率分布 P t ( ( ξ ) = j) j ∈ I ，将随时 间 的变化而变化，称之为瞬态解。瞬态解是很难求出的，即使求出来也难以利 用。因此，在实际应用中，我们更关心的是稳态概率 。稳态概率的含义 是说，当运行时间t 无限长时，状态的概率分将不随时间而变化，此时状态为 t , P j j ∈ I j 的概率 是一个常数。需要指出，虽然在理论上由定理 3 知，生灭过程需经无限 长的时间才会进入稳态。但在实际应用中，对大多数问题来说，相应的生灭过程 总会很快达到稳态，不需要等到t 之后。 Pj → +∞ 9.2 一般排队系统结构 9.2.1 排队模型结构 排队系统（或称为服务系统）可用于描述排队情况。即顾客为了获得某种服 务而到达服务台；若服务员在忙，顾客不能立即获得服务而又被允许排队等待， 则加入等待队列；获得服务之后则立即离开系统。整个过程如图 9-1 所示。 实际上每个具体的排队系统可能有所不同，但一般的排队系统都具有三个要 素，这就是输入过程；排队规则；服 务机构。由这三个要素便可以构造出 一个一般排队系统的结构模型。并由 此得到描述系统运行情况的数学模 型。下面对这三个要素再加以具体的 讨论。 图 9-1 1. 输入过程 到达 等待线 1 服务台 离去
对于输入过程,我们需要了解的一个方面是顾客源的情况(顾客的总体可能 是有限集,也可能是无限集),但主要的方面是了解顾客到达服务系统的规律, 这种规律主要反映在顾客相继到达间隔时间的概率分布上。几种主要情况如下: (1)定长输入。顾客有规律的到达,每隔时间a到达一位顾客。例如自动生产 线上的装配件。顾客相继到达的间隔时间{Tn}的分布函数是 0 t<a P(Tn≤1)= 1t≥a (2)最简单流。即{}中各个T相互独立且都服从同一负指数分布 t>0 P(Tn≤1)= t<0 或者说,在[0,1)内到达的顾客数N()相应的随机过程是泊松过程,即N()的 概率分布为 P(N(1)=k)= k=0,1,2, (3)k阶爱尔朗分布。即{n}中各个T相互独立,且都具有相同的爱尔朗分布 密度: A() p()=(k-1) t>0 t<0 (4)一般独立分布。即中{n}各个T相互独立,且都具有相同的概率分布。 图92 2.服务机构 关于此要素需要明确的是:服务台的个数、服务台之间的串并联结构(图 9-2)、服务台为每位顾客服务所需的时间r的分布情况
对于输入过程，我们需要了解的一个方面是顾客源的情况（顾客的总体可能 是有限集，也可能是无限集），但主要的方面是了解顾客到达服务系统的规律， 这种规律主要反映在顾客相继到达间隔时间的概率分布上。几种主要情况如下： (1)定长输入。顾客有规律的到达，每隔时间α到达一位顾客。例如自动生产 线上的装配件。顾客相继到达的间隔时间{Tn}的分布函数是： 0 ( ) 1 P Tn t ≤ = t t α α < ≥ (2)最简单流。即{Tn}中各个Tn 相互独立且都服从同一负指数分布： 1 ( ) 0 t n e P T t −λ − ≤ = 0 0 t t ≥ < 或者说，在[0 内到达的顾客数 相应的随机过程是泊松过程，即 的 概率分布为： ,t) N t( ) N t( ) ( ) ( ( ) ) ! k t t PNt k e k λ −λ = = k = 0,1,2,⋅⋅⋅ (3) k 阶爱尔朗分布。即{ 中各个T 相互独立，且都具有相同的爱尔朗分布 密度： } Tn n 1 ( ) ( ) ( 1)! 0 k t t e p t k λ λ λ − − = − t 0 t 0 ≥ < (4)一般独立分布。即中{Tn}各个Tn 相互独立，且都具有相同的概率分布。 图 9-2 2. 服务机构 关于此要素需要明确的是：服务台的个数、服务台之间的串并联结构（图 9-2）、服务台为每位顾客服务所需的时间τn 的分布情况。 (c) (b) s 1 1 s (a) 1
下面介绍几种常见的服务时间分布: (1)定长分布每位顾客的服务时间rn均为常数,Tn的分布函数为 P(Tn≤1) 07n< (2)负指数分布{7n}中各个rn相互独立,且都服从相同的负指数分布 t<0 P(Tn≤1)= t>0 (3)k阶爱尔朗分布{rn}中各个r相互独立,且都具有相同的k阶爱尔朗分 布,其密度函数为 t<0 p()={(pan) t>0 (4)一般独立分布{rn}中各个rn相互独立,且都具有相同的概率分布 3.排队规则 排队规则可描述到达的顾客按照怎样的顺序接受服务。在不同的实际问题 中,排队规则是多样的。一般可分为损失制、等待制、混合制三类。 当一位顾客到达时,若所有的服务台均被占用,该顾客自动消失,具有这种 特点的排队规则称为损失制。例如,一位顾客到达某一旅馆,如果已经客满,他 就会离开这旅馆到别处投宿。 顾客到达时,若所有的服务台均被占用,顾客将排成队伍等待服务,具有这 种特点的排队规则称为等待制。接受服务的次序一般采用先到先服务规则。也可 以有其他规则,例如后到先服务、优先权先服务、随机服务(选取等待队列中任 一顾客进行服务)等等。后面讨论的排队模型都采用“先到先服务”的规则。 混合制是损失制和等待制兼而有之的情况。假定服务系统的容量有限,最多 只能容纳k个顾客(包括等待和正在接受服务的顾客),那么当顾客到达时,发 现服务系统已客满,该顾客将自动消失,否则就进入服务系统,这是一种情况。 此外,还可以有顾客等待服务时间有限的情况,即当超过一定时间时,顾客将自 动消失。 922排队系统的数量指标 一个服务系统,一方面是如果服务机构过小而不能满足顾客的需要。就会产 生拥挤现象并造成服务质量的下降。因此顾客希望机构大些好。另一方面,如果 服务机构过大,则人力、物力等方面的开支要增加,并有可能造成资源的浪费, 从这方面的分析来看,设置的服务机构过大未必能收到好的效果,因此希望机构 小些。研究排队系统的目的就是要在顾客的需要和服务机构的规模之间进行权衡
下面介绍几种常见的服务时间分布： (1)定长分布 每位顾客的服务时间τn 均为常数β , τn 的分布函数为 0 ( ) 1 P t n τ ≤ = n n τ β τ β < ≥ (2)负指数分布 {τn}中各个τn 相互独立，且都服从相同的负指数分布 0 ( ) 1 n t P t e µ τ − ≤ = − 0 0 t t < ≥ (3) k 阶爱尔朗分布 { 中各个 相互独立，且都具有相同的 阶爱尔朗分 布，其密度函数为 }n τ n τ k 1 0 ( ) ( ) ( 1)! k t p t t e k µ µ µ − − = − 0 0 t t < ≥ (4)一般独立分布 {τn}中各个τn 相互独立，且都具有相同的概率分布。 3. 排队规则 排队规则可描述到达的顾客按照怎样的顺序接受服务。在不同的实际问题 中，排队规则是多样的。一般可分为损失制、等待制、混合制三类。 当一位顾客到达时，若所有的服务台均被占用，该顾客自动消失，具有这种 特点的排队规则称为损失制。例如，一位顾客到达某一旅馆，如果已经客满，他 就会离开这旅馆到别处投宿。 顾客到达时，若所有的服务台均被占用，顾客将排成队伍等待服务，具有这 种特点的排队规则称为等待制。接受服务的次序一般采用先到先服务规则。也可 以有其他规则，例如后到先服务、优先权先服务、随机服务（选取等待队列中任 一顾客进行服务）等等。后面讨论的排队模型都采用“先到先服务”的规则。 混合制是损失制和等待制兼而有之的情况。假定服务系统的容量有限，最多 只能容纳 个顾客（包括等待和正在接受服务的顾客），那么当顾客到达时，发 现服务系统已客满，该顾客将自动消失，否则就进入服务系统，这是一种情况。 此外，还可以有顾客等待服务时间有限的情况，即当超过一定时间时，顾客将自 动消失。 k 9.2.2 排队系统的数量指标 一个服务系统，一方面是如果服务机构过小而不能满足顾客的需要。就会产 生拥挤现象并造成服务质量的下降。因此顾客希望机构大些好。另一方面，如果 服务机构过大，则人力、物力等方面的开支要增加，并有可能造成资源的浪费， 从这方面的分析来看，设置的服务机构过大未必能收到好的效果，因此希望机构 小些。研究排队系统的目的就是要在顾客的需要和服务机构的规模之间进行权衡