应用随机过程教程（二）：第7章-排队过程

176
龚光鲁,钱敏平著 应用随机过程教程及其在 算法与智能计算中的应用
清华大学出版社,2003
第 7 章 排队过程简介
1,排队过程的描述
1,1 排队系统
排队模型是一种包含更新过程与生灭过程机制的,但是更为复杂的概率模型,
简单的排队过程是在两个相互独立的流作用下形成的,其中一个是要求服务的,顾客流,,这时假定顾客是一个一个地到达的,其时间间隔组成一个更新流,另一个是当顾客进入服务线后,接受服务的 服务 时间 流,服务不一定一个接着一个地发生,在两次服务之间可能有空隙,所以虽然 各顾客 接受的服务独立同分布的时间流,但是 它不具有 更新流 的特点,这 些 服务 空隙成为排队系统的 闲期,两个闲期之间的随机时间称为 忙期,平均闲期 长度与平均忙期 长度 是排队系统设计中的重要指标,我们如果无视闲期的存在,而虚拟地把服务流一个接着一个接成更新流,那么,由服务时间流可以生成一个虚拟的更新过程,
最简单的排队系统只有一条服务线,采取先到的顾客先接受服务的原则,并且有足够大的空间 ( 无限制 ) 容纳等待服务的顾客,在时刻 t 等待服务与正接受服务的顾客数,是一个取非负整值的 随机变量,记为 tX,整值 随机过程 }0:{ ≥tX t 称为 排队过程,它是 连续 时间 状态离散的随机过程,顾客流与服务时间流都是 Poisson 流 ( 即指数流 ) 的排队过程是最简单的排队过程,由定理 6,１２ 知道,只有此种情形的排队过程才可能 是连续时间的 Markov 链,
排队模型广泛地出现在各个应用领域,如服务系统,交通运输,电脑中信息流的存取,
通信系统,商品物流等等,
1,2 排队系统的一般框图,输入过程与输出过程
排 队系统的一般框图如下,
输入过程 ( 顾客流 ) → 排队过程 tX → 输出过程 ( 离去的顾客流 )
值得注意的是,输入过程就是顾客流生成的更新过程,但是输出过程却 不是 服务时间流生成的 虚拟的 更新过程,因为输出过程是输入过程与服务时间流共同作用的结果,
记输入过程为 )(intN ( 即 在 ],0( t 中到达的顾客数 ),输出过程为 )(outtN ( 即 在 ],0( t 中离开系统的顾客数 ),那么我们有
)()(
0
out
t
in
tt NNXX?=?,(7.1)
1,3 可逆性引理
如果顾客流是 Poisson 流,且在某个随机的初值 0X 时排队过程是可逆的平稳过程,即对于任意,0>T 随 机 过程 }:{
^
)( TtXX
tT
T
t ≤=?
与随机过程 }:{ TtX t ≤ （ 前者称为后者的逆过程 ） 有相同的有限维分布族,则 输出过程有如下的可逆性引理,
引理 7 。 1 （ 可逆性引理 ） ( 具 Poisson 输入的可逆排队系统的输出过程 )
设排队系统的输入过程是强度为 l 的 Poisson 过程,而且排队过程 是可逆的平稳过程,
177
则 排队系统的输出过程也是强度为 l 的 Poisson 过 程,
证明 由于 }:{ TtX t ≤ 每次增加 1 都发生在 Tn ∧t 时刻,其中 }{ nt 为参数为 l 的指数流的累次到达时刻,有可逆性 可知 }:{
)(^
TtX
T
t ≤ 也 应具有同样的性质,但是
}:{
^
)( TtX T
t ≤ 增加 1 的时刻正是 }:{ TtX t ≤ 减少 1 的时刻,可见 }:{ TtX t ≤ 减少 1 的时刻与 }{ nt 同分布,也就是 }:{ TtX t ≤ 减少 1 的时刻也是参数为 l 的 P oisson 流,
[ 注 ] M/M/N 排队系统 （ 参见 § 2 中的 (2,2) 段 ） 是满足可逆性引理的典型例子,
2,最简单排队过程 — Markov 排队过程
2,1 最简单的排队过程 -- 1//MM 系统
假定服务系统只有一个,服务员,,顾客到达 的时间间隔相互独立同分布,且服从分布
lexp,而每个顾客接受服务的时间长度也相互独立同分布,服从 mexp 分布,并且与排队系统的输入流相互独立,这种系统在排队论中 记 为 1//MM 系统,其中第一个,M,表示顾客流服从指数分布,第二个,M,表示服务时间长度流服从指数分布,最后一个数字
“1,表示 只有 1 个,服务员,)
记 在 ],0( t 中到达的 顾客 数目为 tN,则它是强度为 l 的 Poisson 过程,如果 在 t 时刻的排队过程 0≠tX,则系统不在闲期,此时 接受了服务的顾客的个数 ( 我们 将 它记为 tL ) 在很短的时间内,是以强度为 m 的 Poisson 过程的规律相增加的,因此,当 0≠tX 且 h 很小时,在 ],( htt + 中接受了服务的顾客个数 hL 满足
)()2( hoLP h =≥,)()1( hohLP h +== m,)()1()0( hohLP h +?== m,(7.2)
( 这里需要警觉的是,接受了服务的顾客个数 tL,并不总是顾客接受服务的时间长度流对应的 Poisson 过程 )(servetN,这是因为当队伍空时就不会出现服务,虽然 服务流的计数过程
}0:{ )( ≥tN servet 总是与顾客流的计数过程 }0:{ )( ≥tN int 独立的,但是 }0:{ ≥tLt 因为受排队过程 )0:{ ≥tX t 是否处于忙期的影响,从而也受 }0:{ )( ≥tN int 的影 响,所以,要想用服务流的计数过程 )(servehN 来描述接受了服务的顾客个数,必须满足,≥tX 服务线的数目,
且 h 很小,
此 系统的排队过程 tX 的状态空间为 },,,1,0{ LL nS =,下面考察排队过程在 ],( htt +
178
中的转移情况,与例 ６,３６ 类似,对转移速率 )(,jiqij ≠ 我们有如下的流向图,
LL←?→←?→←?→→→?
m
l
m
l
m
l
m
l
n10,
由此得到 排队过程 tX 是转移速率矩阵为
Q
+?
+?
=
OOO
lmlm
lmlm
ll
)(
)(
,(7.3)
tX 是连续时间的 Markov 链,即是具有常数生长率 l 与常数死亡率的单侧生灭过程,当
lm > 时,它有可逆分布,此可逆分布是参数为 ml 的几何分布 ( 参见下一段 )
k ),,,( 0 LL npp=,nn ))(1( mlmlp?=,(7.4)
M/M/1 可逆系统在稳定时的平均排队长度,停留时间分布与服务员的等待时间的分布
当 lm > 时,1//MM 系统为可逆的,在系统达到稳定时有
(1) 平均排队长度为
∑ ∑?==
k k
k
k kkL ))(1( m
l
m
lp
lm
l
m
l
m
l
m
l?== =xxdx
d )]
1
1()[1(,(7.5)
(2) 停留时间 T 的分布为 lm?exp
为了验证这个事实,我们用随机变量 V 来记排队系统达到稳定时的队伍长度,那么
LL
LL
)1()(1
0
~
m
l
m
l
m
lV n
n
,
一个顾客进入系统 后的停留时间 T 是随机变量,当排队系统达到稳定时,)|( ktTP =≤ V
是 1+k 个顾客 (系统中的 k 个顾客与进入系统的顾客 )连续接受服务的时间的分布函数,也就是 1+k 个参数为 m 的独立的指数分布随机变量的和的分布函数,故而应该是 ),1( l+Γ k
的分布函数,于是
)()|()(
0
kPktTPtTP
k
==<=≤ ∑
∞
=
VV
179
nsk
kt
k
dsesk ))(1(!
1
00 m
l
m
lm m?=?+∞
=
∫∑ dse s
t
)(
0
)( lmlm= ∫,(7.6)
即 lm?exp~T,这个结论非常符合直观 的印象,
(3) 服务员的等待时间间隔 S 的分布 为 lexp,
事实上,服务员的等待时间的间隔 S,是一个顾客离开系统 时与前面的一个顾客离开系统的时间的差,它也是随机变量,设前面的一个顾客离开系统时系统中的顾客数为 'V,那么在排队系统达到稳定时 'V 与 V 同分布,这时 )0'|( >≤ VtSP 应该是 mexp 的分布函数,而
)0'|( =≥ VtSP 应是独立 的 lexp 随机变量与 mexp 随机变量的 和的 分布函数,即
)0'|( =≤ VtSP dudsee usu
st
)(
00
= ∫∫ ml ml dsee ss
t
)1( )(
0
=∫ lmm lm ml
)1()1( tt ee ml lm llm m= )(11 tt ee= ml lmlm,
于是 由全概率公式得到
)0'()0'|()0'()0'|()( ==≤+>>≤=≤ VVVV PtSPPtSPtSP
+?=? mlm )1( te )1)]((11[ mllmlm ml tt ee te= l1,(7.7)
可见 lexp~S,
2,2 N 个服务员的简单排队过程 — NMM // 系统
１,转移速率矩阵
假定服务系统有 N 个,服务员,,他们分别独立地服务,顾客到达的间隔仍为参数 l
的独立指数分布,且每个顾客接受服务的时间长度仍服从与之独立的,参数为 m 的独立指数分布,这种系统在排队理论中 记 为 NMM // 系统,前两个字母表示指数分布,最后一个数字,N,表示有 N 个,服务员,,
排队过程 tX 的状态空间仍是 },,,1,0{ LL nS =,可以 用如下的流向图来分析转移速率 )(,jiqij ≠,
LL←?→←?→←?→→→?
∧+∧ m
l
m
l
m
l
m
l
))1(()(2
10
NnNn
n 。
由此流向图 可以 得到
180
Q
+∧?∧
+?
=
OO
OOO
llm
lmlm
ll
])[()(
)(
NnNn
,(7.8)
它是互通的,且具有配称列 m ),,( 10 Lmm=,其中
10 =m,
1
1
1
)(
1
)(
+
=


∧
=∧=
∏
n
n
k
nn
NkNn m
lm
m
lm,(7.9)
于是存在可逆分布当且仅当 ml <,在条件成立时,令
p
∑∑ ∞
=
+
=
+
=
00
)(1!1)(!1
1
j
jN
j
k
N
k NNk m
l
m
l m,(7.10)
那么 p 就是可逆分布,因此 排队过程 tX 是连续时间的 Markov 链,在 ml < 时 其 转移矩阵
P )(t 有极限,且
P pTtt 1?→? ∞→)(,
在达到稳定时,排队系统处于闲期的概率为 0p,处于忙期的概率为 01 p?,
由此我们也可以得到,在 lm > 时 NMM // 系统达到稳定时的平均排队长度,
2,可逆 NMM // 系统的特性
命题 7,2 若 NMM // 排队过程的初值为可逆分布 ( 或者任意初值,并经过时间充分长后 ),那么
(1) 正在系统中的人数与输出过程的过去情况相互独立,
(2) 给定顾客在此系统中所停留的时间,与他离开前的输出流独立,
证明 (1) 输出过程的过去就是逆过程的输入过程的将来,这正是指数流的将来,由指数流的性质,它应与在系统中的人数独立,
(2) 由 引理 ７,１,逆过程的输入过程是指数流,再用 （ １ ）,逆过程在进入系统时刻以后的输入流就与已进入的顾客在系统中的停留时间独立,这就是说,顾客离开系统前的 输出流与他在系统中的停留时间独立,
3,可逆 NMM // 系统在稳定时的平均等待时间
设 lm >,在达到稳定后 ( 时间充分长,致使系统近似平稳 ),对于 在时刻 t 来到排队系统的顾客的平均等待时间,可以分析如下,由于排队系统平稳,对于在系统中的顾客 ( 包括在排队的与正在接受服务的顾客 ) 数 tX,应 有 it iXP p== )(,记时刻 t 来到的顾客等待时间
181
为 W,于是当 Ni < 时 有
1)|0( === iXWP t,
而当 Ni ≥ 时,此顾客的等待时间恰为 t 后,第 1+? Ni 个顾客离开的时间 ( 因为在这之前,N 条服务线 忙于 为排队在为前面的 1+? Ni 个顾客服务,只有当第 1+? Ni 个顾客结束服务后,这 N 条服务线中才有一条空出来 ),记 t 时间以后第 k 个顾客离开的时间为
kt s+,注意顾客与服务线的服务时间 是 相互独立 的,当 Ni ≥ 时 就有
)|()|( 1 iXsNPiXsP tt ===≥ 前结束条服务线无一在s sNNs ee == mm )(,
可见 1s 服从参数为 mN 的指数分布,再则,在 1+≥ Ni 时,当第 1 个顾客结束服务后,这 N
条服务线各自需要多少时间结束已开始的服务,是与此前的情况相互独立的,而且仍相互独立地服从参数为 m 的指数分布 。 所以,当 1?+≥ kNi 时,kjjj ≤≤ 11}{ ss 服从 相互独立的 指数分布 mexp,故而 ),(~ ms Nkk Γ 分布,即
∫
∞

=≥
s
xN
k
k dxek
xNNsP mmms
)!1(
)()( 1 ∑?
=
=
1
0 !
)(k
j
j
sN
j
sNe mm,
最后,原 来排队的 i 人在时刻 t 新来的顾客 加入后成为 1+i 人,除去在接受服务的 N 人外,
需要等待 Ni?+1 次服务,因此由 ip 的表达式我们得到,
∑∞
=
+ ≥=≥
Ni
Nii sPsWP )()( 1sp ∑∞
=
=
Ni
Ni
N N )( m
lp ∑?
=

Ni
j
j
sN
j
sNe
0 !
)( mm
∑∑
=
∞
=
=
l
j
j
l
l
sN
N j
sN
Ne 00 !
)()( m
m
lp m ∑∑ ∞
=
∞
=
=
jl
l
j
j
sN
N Nj
sNe )(
!
)(
0 m
lmp m
m
l
m
m
lp m
N
j
sN
Ne
j
j
j
sN
N
= ∑
∞
=

1
1
!
)()(
0 lm
mp lm
=

N
Ne sN
N
)(,
于是有 下面的定理
定理 ７,３ 可逆 NMM // 系统在稳定时有
1 # 需要等待的概率为,
lm
mp
=> N
NWP
N)0(,(7.11)
2 # 平均等待时间为
∫
∞
=>= 0 2)()( lm
mp
N
NdssWPEW
N,(7.12)
182
特 别当 1=N 时 有 )1(1 mlmlp?=,lmml?= 1EW,同时也可得平均 停留时间 T,
因为它 是等待时间 W 与服务时间的和,
* 2,3 序贯排队与排队网络系统
1,简单的 序贯排队模型
设排队系统由两个 1//MM 子系统串联而成,设 进入第一个子系统的顾客流为参数 l
的指数流,服务时间流为与之独立的,参数为 1m 的指 数流,从第一个子系统离开的顾客进入第二个子系统,其服务时间流是与前两个流独立的参数为 2m 的指数流,假定 lmm >∧ 21,
这时,第一个子系统有可逆分布,它的排队过程是空间齐次的单侧生灭过程,而且其转移矩阵的每一行都趋于其可逆分布,于是不管什么初值,只要时间充分长,就可以认为可逆性引理 ７,１ 的条件成立,由引理 7.1,第一个子系统的输出过程 ( 也就是第二个子系统的输入过程 ) 也是以 l 为强度的 Poisson 过程,并且第二个子系统也有同样的性质,
2,简单 的 排队网络
假定 服务网络系统设有 n 个服务点,每个服务点设置一条服务线,分别独立地服务,假定在第 i )( ni ≤ 个服务点所需的服务时间为参数 im 的指数流 。 令 P )( ijp= 为一个随机矩阵,其中 ijp 在 ji ≠ 时表示,第 i 个服务点接受完服务后的顾客,转而再去第 j 个服务点的概率,而 iip 表示顾客在第 i 个节点 （ 服务点 ） 接受完服务后,离开此服务网络系统的概率,时刻 t 在第 i 个服务点的排队过程为 )(itX,定义 ),,( )()1( nttt XXX L?=,这个 n 维过程称为在此服务网络系统中的排队过程,假定由系统外进入系统各个服务点的顾客流,是彼此相互独立的,而且进入第 i 个服务点的顾客流为参数 )0(il 的指数流 。 再假定 im 比较大,以使每个服务点上的排队过程是可逆的 （ 在后面 我们将 会 看到它们成立 的条件 ）,
由于顾客在各个服务点间有转移,所以进入第 i 个服务点的 实际 强度 （ 记为 il ） 要比 )0(il
大,由引理 7.1,只要在第 i 个服务点的排队过程是可逆的,那么 在时间充分长 以 后,在 这个服务点的输出流也 应该 是参数为 il 的指数流,
记第 j 个 节点 (服务点 )接受到的外来顾客的时间间隔流为 }{ )0( jkT →,而从节点 i 接受到的顾客的时间间隔流为 }{ )( jikT → 。 由 Poisson 过程的分流定理知道,
iijp
ji
kT lexp~
)( →,而且对于固定的 k,)( 1)1( 1)0(,,,jnkjkjk TTT →?→?→ L 相互独立,这使 得 在节点 j 实际接受到的顾客的时间间隔 为
)(
1
)1(
1
)0( jn
k
j
k
j
k TTT
→
→
→ ∧∧∧ L
iij
i
j p ll ∑+)0(exp~,(7.13)
183
于是顾客流的强度 jl 应该满足 流方程
iij
i
jj p lll ∑+= )0(,(7.14)
这个网络排队过程转移速率矩阵 Q 较为复杂,但是 Q 的流向 却 可以简单表示为,
←
→
i
i
ni kkk
m
l
),,1,,( 1 LLL
←
→?
j
j
nji kkkk
m
l
),,,,,( 1 LLL LLLL ),,1,,,,( 1 nji kkkk +,
即
ikkkkkk niniq l=+ ),,1,,(),,,,( 11 LLLL,ikkkkkk niniq m=+ ),,,,(),,1,,( 11 LLLL,(7.15)
现在我们假定流方程的解 ),,{ 1 nll L 满足,),,1(,niii L=< ml 。 那么仿照第 6 章中的讨论,就 可以得到 Q 有配 称列 p = ),,( ),,,(
1
LL LL
ni kkk
p,它是概率向量,其 分量为





= ∏
= i
i
k
i
i
n
i
kkk
i
ni m
l
m
lp 1
1
),,,( 1 LL,(7.16)
最后,用定理 6.26 就得到以 Q 为转移速率的,时间连续的 Markov 链的转移矩阵 P )(t 满足
P )(t )(,∞→→ tT p1,
并且遍历定理成立,由 (7.16)可以看出,在各个服务点的排队过程是渐近地相互独立的,
2,4 M ／ M ／ ∞ 排队系统
这时有 ∞ 条彼此独立地工作的服务线,排队过程 tX 的转移速率矩阵为
Q


+?
+?
=
OOO
OOO
lmlm
lmlm
ll
)(
)(
NN,(7.17)
它是互通的,具有可逆分布
Np
N
e

=?
m
lml,(7.18)
而且也有
P Ttt 1?→? ∞→)( p,
下面我们进一步求 tX 的分布 )()( kXPtp tk == 的表达式,
这时的 M aster 方程
184
)),('),('( 10 Ltptp )),(),(( 10 Ltptp= Q
的分量形式为

+++?=
+?=
+? )()1()()()()('
)()()('
11
00
tpktpktptp
tptptp
kkkk
i
mmll
ml,（ ７,１９ ）
这组方程等价于 tX 的矩母函数
tXEzztG
=),(
= ∑
∞
=0
)(
k
k
k ztp （ ７,２０ ）
满足如下的偏微分方程,
t
G
∑∞
=
=
0
)('
k
k
k ztp ))(1( z
GGz
= ml,
即
t
G
0)1())1( =
+ Gz
z
Gz lm,（ ７,２１ ）
作变换 ),(),( )1)(1( ztHeztG
tez m
m
l
=,就简化为
0)1( =+ zHztH m,（ ７,２２ ）
两边乘以 te m?,记函数对 ),(( ztH,))1( tez m 关于 ),( zt 的 Jacobian 行列式为
),(
))1(,(
zt
ezH t
m,那么方程 （ ７,２２ ） 就可改写成
0),( ))1(,( =
zt
ezH tm,（ ７,２２ ）＇
这就说明了 ),( ztH 与 tez m )1( 函数相关,即存在一个函数 )(xh 使
),( ztH ))1(( tezh m=,（ ７,２３ ）
设 ｔ＝ ０ 时系统中的顾客数 0X 的分布为 kakXP == )( 0,那么
∑∞
=0k
k
k za )1(),0(),0(?=== zhzHzG,
于是
∑∞
=
+=
0
)1()(
k
k
k zazh,
因此
185
=),( ztG ∑
∞
=
+
0
)1)(1( ))1(1(
k
kt
k
ez ezae tt mml m
,（ ７,２４ ）
显见 ),( ztG 的表达式完全依赖于初始资料 ),0( zG 的选取,当取 izzG =),0( 时,我们把得到的 ),( ztG 记为
∑∞
=
=
0
)(),(
j
j
iji ztpztG,
由此可得 下面的定理
定理 ７,４ 可逆 ∞//MM 系统排队过程的的转移函数为
)!(
)1()( 2
0
)1(
kj
eeCetp kjittkkjji
k
i
k
e
ij
t


=?+∧
=
∑? mmml
m
lm,（ ７,２５ ）
于是
!
)]1([
)( )1(0 j
e
etp
jt
e
j
tt
m
m
l m
l
m
=?
,（ ７,２６ ）
即 当 10 =X 时,
)1(
exp~ t
et
X m
m
l,由此可见当 ∞→t 时 tX 有极限分布
m
lexp,这就再一次求得了 tX 的不变分布,
[ 注 1] 以上的方法与结论可以推广到 λ 依赖于 t 的情形,只要假定 λ ( ｔ ) ≤常数 λ 0,
这时有
0!)()(lim )( =

= Λ?
∞→ k
tekXP kt
tt,
其中
∫=Λ
t
dsst
0
)(1)( lm,
即当 t 非常大的时候,排队过程 tX 的分布与 )(exp t? 非常接近,
[ 注 2] ( 成批顾客的排队系统 )
上 面 的方法 和 结论,还可以推广到顾客 有 成批到达 的情形,假定顾客 在参数为 λ 的 Poisson 过程的跳跃时刻上到达,但到达的顾客是成批的,即到达人数 u 是一个非负整值的随机变量,其母函数记为
∑∞
=
===
0
))((,)(
k
k
k
k kPbzbzB u
D
,（ ７,２７ ）
又 假定 服务时间仍为参数为 m 的独立同分布的指数分布,那么用与推导 ∞//MM 系统 的 排队过程的矩
186
母函数相似的方法,对于这里的成批排队系统的排队过程 tX 的矩母函数
tXEzztG
=),(
=∑
∞
=0
)(
k
k
k ztp,
可以得到
∫
=
+
z
tez
dststssB
t eezGztG m m
lm
m )1(1
)11ln1(1 )(11
))1(1,0(),(,（ ７,２８ ）
3,排队系统的一般概念
3,1 关于排队论的一般注记
排队系统是服务系统,交通运输,通讯 系统等 许多领域中的 问题简化后的数学模型,
由第 ２ 节 可以看出,即使是很简单的 排队系统的 数学模型,其数学处理的 也 是 很复杂 的,
应用 问题 中 的需要与数学的复杂 性的 矛盾 在排队系统中突出地尖锐,于是,不同 的实际工作者 在 各自 的 范围 使用自己的直观近似,对于同样问题的 看 法也不尽一致,至今关于排队论的文献已超过 10 万,而且每年还以近两千篇的数量增加,本章只是介绍一点简单的框架,
排队理论涉及了一个 复杂 系统,它包含,
1,输入过程,它 一般是一个更新流,称为 " 顾客 " 流,更广地,也 可以是每次 批 量 输入 的输入 流,
2,服务设备 ( 服务线或服务员 ) 的数目,可以有 1 个,Ｎ 个或 ∞ 个,它们之间是 彼此 独立地工作的,
3,服务设备对于不同顾客的服务时间是独立同分布的随机变量,它们与输入过程独立,
4,服务规则,最 常见的是先来先服务 ( 记为 FIFO,即 First In First Out),
除单个服务外还有成批服务 ( 顾客够一定数才启动服务 ),顾客接受服务 又可分三种 方式,
第一种是等待制,在服务设备全用上时,多余的顾客排队等候,这需要有充分的等候设施,这称为有无限空间等待的情形 ;
第二种是消失制,顾客见到所有服务设备都在忙就离去,例如电话通讯 ;
第三种是有限制的排队,即 每个 顾客看到队伍长度 超过了某个预定的 N 则离去 ( 等候设备有限制 ),
5,排队系统研究的主要 指标 有,
(1) 稳态时排队长度的不变分布与其平均值,方差 ( 在 等待制时用 作 设计等候室 的 参考 ),
(2) 设备在平稳状态下的平均忙期 长度,平均闲期 长度,
(3) 稳定时拒绝服务的概率 ( 消失制 ),
(4) 稳定时等待时间的分布与平均值,方差 ( 等候制时用以设置服务线 ),
(5) 稳定时的效率 ( 最高服务率时平均能服务的顾客数 ),
6,一个排队系统用下面的记号表示,输入流分布 ／ 服务流分布 ／ 服务线数目,
M,表示指数分布,
kE,表示 k 阶 Erlang 分布,即 ),( lkΓ 分布,
G,表示一般分布函数,记为 )( xG,在输入流中 G 有时也用 GI 表示,
D,表示流为常值,
187
常见的有排队系统有,1//MM,NMM //,∞//MM,1// MG,1//GM,
1//GGI ( 也记为 1//GG ) 等等,
7,描述排队系统的一个 最基本的 量是排队过程 tX,即时刻 ｔ 在系统中的顾客数 ( 包括正在被服务的顾客与排队的顾客 ),这是一个连续时间的取非负值的随机过程,除?//MM
系统以 外,一般的 排队过程 tX 并 不是 Markov 链,但是,有时加入 一些由 附加信息 提供 的 辅助随机 过程 后,可以使 它们合起来的向量过程有 Markov 性,也就是使排队过程成为某个高维 Markov 链的一个分量,
8,由于 在文献中已经证明了,在 ),0[ ∞ 上具有密度的随机变量的 任意的 分布函数,都可以用 Erlang 分布的分布函数的混合来近似,因此在实用中,总认为 可以 用混合 Erlang 流近似 任意更新流,
3,2 NMM // 消失制
消失制情形时没有得到服务的顾客都自动离去,所以此时的排队人数就是正在接受服务的人数,因此 排队的队伍长度不 超过 N,此时排队过程 tX 的转移速率矩阵为
Q


+
+?
+?
=
mm
lmlm
lmlm
lmlm
ll
NN
NN ))1(()1(
)2(2
)(
OOO,
它是互通的,而且有可逆分布 ( 这个稳态分布的公式,称为 Erlang 公式 )
p






=?
=
∑
NN
j j m
l
m
l
m
l,,,1
!
1 1
0
L,（ ７,２９ ）
此时仍有
P Ttt 1?→? ∞→)( p
这时,在 稳态 时 新来的顾客被拒绝,当且仅当在系统中的顾客数为 N,因而 我们得到下面的定理
定理 ７,５ 对于可逆 NMM // 系统,在稳定时 新来的顾客被拒绝的概率为
Np
NN
j j






=?
=
∑ mlml
1
0 !
1,（ ７,３０ ）
3,3 1//GM 排队系统
如果服务时间流不是指数流,而是一般的更新流 。 即服务时间为独立同分布,其分布函数为 )(tG,或分布密度为 )(xg （ 最简单的情形是 )(tG 为 ),( kErlang l 分布 ）,其它假定都与 1//MM 相同 。 这样的排队系统就是 1//GM,
系统 1//GM 的排队过程 tX,不再是时间连续的 Markov 链,这是 因为 服务时间不是
188
指数流,即 更新间隔的分布 不是无记忆的,所以,正在接受服务的顾客已经在服务线上已花费的时间,就应该是一个需要记忆的参数,在 次参数 给定时,系统中的排队人数 也 不具有
Markov 性,但是,如果只考虑顾客离开的时刻 s ( 注意它是随机的 ),由于此时正好完成了 一个服务周期,于是在这些时刻排队 人数 的变化只由输入决定,而 输入是指数流,我们 可以猜想 排队过程在这些时刻上具有 Markov 性,即只考虑 排队过程 在 顾客离开的时间列 }{ ns
上 就是离散时间的 Markov 链,我们把它表达为 下面的定理
定理 ７,６ 1//GM 系统的排队过程 nX 限制 在顾客离开的时间列 ns 上,得到的
n
Xs
是时间离散 的 Markov 链,它恰好记录了排队过程各个顾客刚离开后的排队队伍长度,其转移矩阵为
P
=
OOOMM
L
L
L
L
10
210
3210
3210
00
0
aa
aaa
aaaa
aaaa
,（ ７,３１ ）
其中
=ja dttgejt t
j
)(!)(
0
ll?
∞?
= ∫,（ ７,３２ ）
这个 Markov 链没有可逆分布,
证明 为了使讨论简单,我们不妨假定 )(tG 具有分布密度 )(tg,从直观上看,把第 n
个顾客离开的时刻记为 nσ,而记 此时在系统中还留下的排队人数为 nZ,nZ 是由此顾客在接 受服务期间进入系统的 （ 且与此顾客的服务 独立的 ） 指数顾客流决定的,我们把第 1?n
个顾客离开 ( 即第 n 个顾客接受服务 ) 至第 n 个顾客离开期间 ( 即 ],( 1 nn σσ?,它恰为一个服务周期 ) 进入系统的顾客数记为 1?nY,那么,1?nY 与 ),,( 11 ZZ n L? 独立,同时我们有

=
>?+=


)0(
0)(1
11
1-n1
nn
inn
n ZY
ZZYZ
若若,
在 0>i 时推得
),,|( 221 L === nnnn iZiZjZP ),,|1( 2211 L ==+?== nnnn iZiZijYP
)1( 1 +?==? ijYP n )|( 1 iZjZP nn ===?,
而 在 0=nZ 时,Markov 性是显然的,这就证明了 }{ nZ 是 Markov 链,我们进一步求它的转移矩阵,（ １ ） 当 1?< ij 时,显见 0)|( 1 ===? iZjZP nn,
（ ２ ） 在 0,1 >?≥ iij 的情形,由于 ],( 1 nn σσ? 对应 一个服务周期,而
189
11?
=?
nn
NNYn ss,)(~1 tgnnss,我们 用全期望公式求得转移概率
)|( 1 iZjZP nn ==? )1( 1 +?==? ijYP n
dttgtijNNP nnnn )()|1( 1
0
1 =?+?=?=?
∞
∫ ssss dttgtTijNP t )()'|1(
0
*
=+?== ∫
∞
∫∫
∞∞
=+?==
00
)()1( dttgijNP t dttgeij t t
ij
)()!1( )(
1
ll?
+?
+?
,
( 注 * 的严格推导要用 Poisson 过程的强再生性 ),
对 0=i 的情形,类似地可算出
)0|( 1 ==?nn ZjZP jt
j
adttgejt =?=?
∞
∫ )(!)(
0
ll,】
下面我们来求它存在不变分布的条件,
记平均服务时间为 v ( 它相当于 1//MM 系统中的 m1 ),那么
∫
∞
=
0
)( dtttgv,
注意,转移矩阵 P的首行是一个分布,记此分布的期望为 r,则
vdttgdttgejtjja t
j
j
j
j ∫∫ ∑∑
∞

∞ ∞
=
∞
=
==?==
00 10
)()(!)( lllr l,
受 1//MM 系统的启发,我们猜测并证明,当 nl 1< 时,即 1<r 时,}{ nZ 存在唯一不变分布 p ),,( 10 Lpp=,为此我们 只须 求出其母函数 ∑
∞
=
=
0
)(
j
j
j zz pp,记
∑∞
=
=
0
)(
j
j
j zazA,由 P的形式,用 p = p P的分量形式
∑+
=
+?+=
1
1
10
j
i
ijijj aa ppp,
便得
∑∑∞
=
+
=
+?+=
0
1
1
10 )()(
j
j
i
j
iji zazAz ppp,
其中后一个和数 为
190
∑ ∑∞
=
∞
=
+?
+?
1 1
1
1
1
i ij
ij
ij
i
i zazz p z
zAz )())(( 0pp?=,
最后得到
)(
)()1()( 0
zAz
zAzz
= pp,
由此得 rpp?= 1)1( 0,故而 rp?=10,于是 当 1<r 时,不变分布唯一地存在,容易验证它是互通的,由定理 ５,５０ 知道 }{ nZ 是正常返的,易见它还是非周期的,所以由该定理后面的注 1,有
P →n T1 p,
从而 p 代表了系统稳定时,在顾客离开系统时,还留在系统中的顾客数的分布,综上得到下面的定理
定理 ７,７ 对于排队系统 1//GM,在 满足条件 l1)(
0
<∫
∞
dtttg 时,排队过程 在顾客离开时刻上导出的离散时间 Markov 链存在 唯一的 不变分布 p,它的矩母函数为
)(
)()1)(1()(
zAz
zAzz
= rp,（ ７,３３ ）
其中
∑∞
=
=
0
)(
j
j
j zazA,∫
∞
=
0
)( dtttglr,（ ７,３４ ）
并且满足 P →n T1 p,】
经过较多的计算,还 可以得到 1//GM 系统的 平均忙期 为
dttgnte n
n
n
t )(
!
)( *
1
1
0 ∑∫
∞
=
∞?ll,（ ７,３５ ）
其中 ng * 为 g 的 n 次 卷积,
3,4 1// MG 排队系统
如果服务时间 服从 参数为 m 的 独立 指数 分布,而顾客到达的流是一个一般的更新流
( 即间隔时间为独立同分布的分 布函数 )(tG,或分布密度 )(tg ),其它假定都与 1//MM
相同,则这样的排队系统记为 1// MG,这个系统中顾客到达 时间的 间隔 并 不 服从 指数分布,因此 时间间隔的分布 不是无记忆的,也就是说,系统 等待顾客到达所花费的时间,是一个需要记忆的参数,在此参数给定时,系统中的排队人数不再具有 Markov 性,但是,如果限制于 考虑顾客到达的时刻 nt,由于此时正好完成了一个完整的,到达周期,,我们 可以
191
猜测 排队过程在时间列 nt 上有 Markov 性,这就是 下面的定理
定理 ７,８ 1// MG 系统的 排队过程 tX 限制 在顾客的到达的时刻 nt 上,得到的
n
Xt
是时间离散的 Markov 链,它恰好记录了排队过程各个顾客刚到时所看到的排队队 伍长度,
其转移矩阵为


=
∑
∑
∑
∑
∞
=
∞
=
∞
=
∞
=
OOOMM
O
L
L
L
123
4
012
3
01
2
0
1
0
00
bbbb
bbbb
bbb
bb
k
k
k
k
k
k
k
k
,（ ７,３６ ）
其中
=jb dttgejt t
j
)(!)(,
0
mm?
∞?
= ∫,（ ７,３７ ）
证明 与 M/G/1 排队系统对偶地,令
nZ
^
= 第 n 个顾客来到系统时见到在系统中的顾客数,
把区间 ],( 1 nn tt? 中离开排队系统的顾客个数记为 1
^
nY,那么
)0,1max( 1^1^^+= nnn YZZ,
与 M/G/1 系统类似地可以证明,nZ^ 是 Markov 链,服务时间指数流对应的更新过程为
Poisson 过程记为 tN',又设 }{ nT 是一个以 )(tg 为密度的更新流,且 ∑
=
=
n
k
kn T
1
t,我们 用全期望公式求得 }{ ^ nZ 的转移概率如下,
(1) 在 01 >≥+ ji 时,区间 ],( 1 nn tt? 中并未出现闲期,所以
)|( 1^^ iZjZP nn ==? )1( 1^ +?==? jiYP n
dttgtTjiNNP nnn )()|1( ''
0
1 =+?=?=?∫
∞
tt dttgtTjiNP nt )()|1'(
0
=+?== ∫
∞
∫∫
∞∞
=+?==
00
)()1'( dttgjiNP t dttgeji t t
ji
)()!1( )(
1
lm?
+?
+?
,)10( +≤< ij,
192
(2 ) 当 01^ >?nZ 时,若 0^ =nZ,则在 ],( 1 nn tt? 有 1+i 个顾客离开,而且还出现了闲期,于是在条件 }0{ ^ =nZ 下 }1{ 1^ +=? iY n 不是等价于 }1{ '' 1 += iNN nn tt,而是等价于
}1{ '' 1 +≥ iNN nn tt,所以,与上面类似地有
)|0( 1^^ iZZP nn ==? )1( 1^ +==? iYP n
dttgtTiNNP nnn )()|1''( 1
0
=+≥?=?ττ
∞
∫ ∫ ∑
∞ ∞
+=
=
0 1
)(!)( dttgkte
k
ik
t mm
jb=,
定理 ７,９ 对于排队系统 1// MG,在
∫ > m1)( dtttg （ ７,３８ ）
时,排队过程在顾客到达的时刻所导出的 Markov 链有形式如
p ),,,,1(1 1 LL nbbb?= （ ７,３９ ）
的不变分布,其中 b 是方程
∫
∞
=
0
)1( )( dttge tbmb （ ７,４０ ）
在 )1,0( 中的唯一解,而且此时有 P n pT1→,
证明 Markov 链
n
Xt 显见互通 且是非周期的,如果我们证明了它至少存在一个不变分布 p,那么它一定是正常返的,从而不变分布唯一,而且 P n pT1→,在 （ ７,３８ ） 条件下时,我们待定常数 b,使以 （ ７,３９ ） 定义的 p 是不变分布,而不变分布的条件
p＝ P p 即
∑∑ ∞
=

∞
=
==
0
1
)1(
1 j
j
jn
nk
nk
kn bb bbbb,
利用 （ ７,３７ ） 就得到 b 满足 （ ７,４０ ）,而 在 条件 （ ７,３８ ） 下,可以 用 分析方法证明 （ 因为 较繁,所以略去 ) 上面的方程在开区间 )1,0( 中存在唯一解,
[ 注 ] 在 3,3 段与 3,4 段中,若 )( xG 没有密度,那么,只要用 )(tdG 代替 dttg )(,即只要把普通积分改为 Stieltjes 积分,就使所有的结论保持正确,
193
3,5 关于 ∞//GM 系统的注记
∞//GM 系统与 1//GM 系统的唯一不同是,∞//GM 系统有 ∞ 条服务线,进入系统的每个顾客可以随机地 选取一条服务线,而各服务线的服务时间仍是服从分布函数 )(tG
的独立同分布随机变量,且与输入流彼此独立,为了在数学上简单些,我们仍假定 )(tG 有密度 )(tg,
我们来考虑 ∞//GM 系统的输出 ( 顾客 ) 流,由于有 ∞ 条服务线,进入系统的顾客立刻得到服务,顾客进入后,在经过时间 t 以前离开的概率就是服务时间不大于 t 的概率,即是
)(tG,若我们 把离开与还在接受服务看成顾客流的 随机 分流,那么这个分流的概率就是
)(tGp =,由 Poisson 过程的非时齐分流定理,我们立刻得到下述结论,
定理 ７,１０ ∞//GM 系统的输出流是强度为 )(tGl 的非齐次 Poisson 流,即对于第
n 个顾客离开系统的时间 nt,其计数过程 }:sup{ tnN nt ≤=? t 是强度为 )(tGl 的非时齐
Poisson 过程,
这时服务时间长度
~
iT 为独立同分布的任意分布函数 )(tG,只要 0
~ >=
iTEm
D
有限,那么经过并不复杂的推导 ( 参见,A,я,欣钦,公用事业理论的数学方法,科 学出版社 1958
年中译本,第 72 页 ),就可得到,
定理 ７,１１ 当 →t ∞ 时,排队过程 tX 近似于 Poisson 分布 mPoisson?l,】
对于一般排队过程来说,通过定理 ４,２ 8 用混合的 Erlang 分布,来近似排队系统中的服务分布或顾客到达的间隔分布的方法,是一个简化排队系统的重要方法,通常称为 位相方法,例如,由定理 4.28,排队系统中的服务时间的 近似 分布为 )(xFh,它对应于 顾客要以概率 np 连续地完成 n 个独立的串联的分布为
h
Exp1 的服务后 ( 称为 n 个位相 ),才离开系统,
这种思路可以用来有限地简化排队系统的一些统计指标的近似计算,如不变分布,队伍长度的分布等等,
[注 ] 处理一般非 Markov 排队过程 tX 的 常用的方法中,还有一种加入辅 助变量使之成为 高一 维的 Markov 过程 的 辅助 过程 方法,例如,对 于 1/G/M 系统的排队过程 tX,记
tt =j 时刻在接受服务的顾客已接受服务的时间,那么 ),( ttX j 是取值于 ++ × RZ 的
Markov 过程,其中 ++ RZ,分别为非负整数集,非负实数集,类似地,对 于 1/M/G 系统的
194
排队过程 tX,只要 记 =ty,自 t 时刻 至 下一个顾客到达 的 等待时间,,则 ),( ttX y 也是取值于 ++ × RZ 的 Markov 过程,这里的 tt yj,都是辅助随机过程,辅助随机过程引入后,就可以使用 Kolmogorov 方程和 Master 方程,以及不变 分布等工具,近年来 我国有些学者,注意到 了 多数排队系统的排队过程在某些特定的随机时刻上具有 Markov 性,并称这种在一些特殊时刻上具有 Markov 性的随机过程为 Markov 骨架过程,他们利用首达 时刻 分析 方法,
得到了 Markov 骨架过程的转移特征满足的积分方程,由此可以得到描述排队过程的许多特征量,在理论上 为研究 1/G/GI 等 系统,提供了不同于 在辅助过程方法 的一个途径,
* 4,半 Markov 过程
4,1 半 Markov 过程
１,半 Markov 过程是时间连续的 Markov 链的自然推广,它并不假定呆在一个状态的时间服从指数分布,因此,它更多地出现在许多常见的排队过程中,它的确切定义为
定义 ７,１２ 设 tx 是一个最多只取可数个状态的连续时间的随机过程,其跳跃由某个连续时间的
Markov 链的嵌入链的转移矩阵决定,但是它呆在状态 i 的时间未必服从指数分布,假定在状态 i 呆的时间是与离开 i 时进入的状态 j 也有关的某个分布 )(),( jitFij ≠,再假定各次跳跃是独立的,呆在不同状态的时间是独立的,且它们之间也相互独立,这样的随机过程 tx 称为 半 Markov 过程,
２,半 Markov 过程有与连续时间的 Markov 链类似的优点,就是容易对它作随机模拟,我们以 N 个状态的半 Markov 过程为例,给出 它的轨道模拟步骤如下,
(1),模拟初 始 分布 0m ))(,),1(( 00 Nmm L=,对于 Ni ≤≤1,以概率 )(0 im 取 i ;
(2),作分布 ijF 的随机数 ijT,让轨道在状态 i 停留时间 ijT 后,以概率 )1( =∑
≠
ij
ij
ij pp 跳到
)( ij ≠ ;
(3),以 j 代替 i 后重复步骤 (2).,
这个 P )0(),( == iiij pp 对应的 Markov 链,称为半 Markov 过程的 嵌入链,也称 P为 半 Markov 过程的嵌入转移矩阵,
３,半 Markov 过程在转移前平均停留时间可以表达如下,
设从 i 出发,到转移前在 i 停留的时间为 it,由假定,在转移到 j 的条件下,it 的条件分布为 ijF,
而从 i 转移为 j 的概率为 ijp,于是 it 的分布函数为
∑
≠
=≤
ij
ijiji tFptP )()(t,
4,2 半 Markov 过程的渐近性质
令 iit 为半 Markov 过程两次连续进入 i 间的一个循环的时间间隔,那么半 Markov 过程从开始停留在
195
i,一直到离开 i 后又首次回到 i,就形成一个循环,所有的循环连起来就成为一个交错更新过程,对这个交错更新过程用极限定理,便得到半 Markov 过程的状态转移的渐近性质,
定理 7,１３ 如果半 Markov 链的 嵌入转移矩阵 P不可约,且 iit 的分布为非格点分布,又
∞<iiEt,那么
jj
j
j
t
t E
EijP
t
tpxx?∞→ =?→?== )|(
0,
j
jj
jt
E
E
t
jt p
t
t =?→? ∞→的时间中过程停留在],0[
,
它们都与半 Markov 链的初值无关,】
若嵌入链 P正常返,互通,即 P ~p→n,又若 iit 为非格点分布,且 ∞<iiEt,回忆 Markov 链的情形,那时有 jj
j
j
j ECqC tp
pp ~
~
==,可以猜想这个关系 对于半 Markov 过程仍然正确,即我们有下述定理
定理 7,１４ 若半 Markov 过程的嵌入链 P正常返,互通,即 P ~p→n,又若 iit 为非格点分布,且
∞<iiEt,则
=(jp
∑
=
k
kk
jj
jj
j
E
E
E
E
tp
tp
t
t
~
~
),
它 等价于
~
~
j
k
kk
jj
E
E
p
tp
t
∑
=,
证明 令 )(kjt 为第 k 次在 j 停留的时间长度,)(njN 为前 n 次转移中取 j 的次数,)(njp 为前 n 次转移中取 j 的时间的比例,用 )(lim njnj p∞→=p 及强大数定律于
∑ ∑
∑
=
==
i
N
k
k
i
N
k
k
j
n
j n
i
n
j
p )(
)(
1
)(
1
)(
)(
t
t
∑ ∑
∑
=
=
=
i
N
k
k
in
i
n
i
N
k
k
jn
j
n
j
n
i
n
j
Nn
N
Nn
N
)(
)(
1
)(
)(
)(
1
)(
)(
)(
1
1
t
t
196
∑
→? ∞→
i
ii
jjn
E
E
tp
tp
~
~
,
便得定理,】
利用交替更新定理,我们还可以证明
命题 ７ 。 １６
)|,,( 0 iksttjP t =+= xx 转移到后后首次转移在
jj
s
jkjk
E
duuFp
t
∫
∞
=
))(1(
,
)|,( 0 isttjP t =+= xx 后后首次转移在
jj
s
j
E
duuP
t
t∫
∞
>
=
)(
,
证明 记服从分布 ijF 的随机变量为 ijt,在两次连续进入 i 间的一个循环的时间间隔中,满足条件
},,{ ksttjt 转移到后后首次转移在 +=x
的时间,与不满足该条件的时间,分别组成交替更新间隔,而在一个 i -循环中满足此条件的时间的期望为
])[( +? sEp jkjk t ∫
∞
+ >?=
0
))(( duusPp jkjk t
∫
∞
+>=
0
)( dusuPp jkjk t ∫
∞
>=
s
jkjk duuPp )(t,
用交替更新定理便得第一个等式,而第二个等式乃是第一个等式的推论,
* 5,有限位相型分布 ( PH - 分布 )
5,1 背景
在排队系统的理论中,常出现所谓有限位相型分布 ( 简称为 PH-分布 ),这类分布是 指数分布在矩阵意义下的推广,这一类分布包括了混合 Erlang 分布,因此,可以用来近似 任意有密度的正随机变量的分布,所以,PH 分布类有广泛的代表性,即 在 ),0[ ∞ 上取值的随机变量的分布都可以用 PH 分布近似,
直观地,假定给定了一个具有一个吸收状态的有限状态的连续时间的 Markov 链,如果在此吸收态设置一个观测点,测量此 Markov 链在被吸收的时间,即首次到达此吸收点的时刻 t,这个随机时间 (它是停时 ) 的分布,就称为 有限 位相型分布 ( PH - 分布 ),t 就称为 PH 随机变量,
不同的 连续时间的 Markov 链,可能生成相同的有限位相型分布,
一个相反的问题是,知道了这个 有限位相分布 ( PH-分布 ),能在多大程度上知道此连续时间的 Markov
链的转移矩阵,或它的转移速率矩阵呢? 如果回答为肯定,那么这就提供了一种测量转移参数的手段,
下段中我们把上面的定义,叙述得更为数学化一些,
5,2 PH 分布 (有限位相型分布 )
197
定义 ７,１ ７ 设状态空间为 },1,0{ NL,的连续时间的 Markov 链 tx,其 转移速率矩阵为
Q =

~00
Qq T,( Q 的行和为 1),再假定
~
Q是一个对角线上为恒负的可逆矩阵,此时 0 为唯一的吸收态,我们 将 tx 被 0 吸收的时刻 t 的分布称为 PH 分布,
下面我们将 PH 分布写为参数形式,设 tx 的初始分布为
)1,0(,)(
0
0 ∑
=
=≤≤==
N
j
jj NjjP aax,
仿照离散时间 Markov 情形,我们记禁忌到过 0 的转移概率为 )(}0{ tpij,那么类似地有
etpij =))(( }0{
~
Q? t,
于是 PH 分布可以写为
)(1)()( tPtPtF >?=≤= ttD
)()|)0(0,(1 00
1,
iPitsjP st
N
ji
==<<≠=?= ∑
=
xxxx
)()(1 0
1,
}0{ iPtP
N
ji
ij =?= ∑
=
x
eN ),,(1 1 aa L?=
~
Q t T1,
由此得到
定理 ７,１ ８ PH 分布的分布函数总可以表示为 eN ),,(1 1 aa L?
~
Q t T1,其中
~
Q ijq~＝,它们满足
∑
=
≠≥<<≥
N
i
ijiiii jiqq
1
~~
)(,0,0,1,0 aa,
所以 PH 分布只依赖参数
=a ),,(
1 Naa L 与
~
Q,
定义 ７,１９ 定理 ７,１８ 中的参数组 ),,( ~Qa 称为 PH 分布的一个 参数表示,不同的参数组可能对应与相同的 PH 分布,因此,同一个 PH 分布可以有多个参数表示,N 最小的那组参数表 示,就称为此
PH 分布的最小表示,
例 ７,２０ 参数为 l 的指数分布 lexp 是 PH 分布,且 它的最小表示为,
=a,1
~
Q l?=,
198
证明 记以 }1,0{ 为状态空间,并以 Q

= ll
00
为转移速率矩阵的连续时间的 Markov 链为 tx,
则由上面的结论可知,tx 首达 0 的时刻 t 的分布为 tetP lt?=> )(,这正说明了 lt exp~,
命题 ７,２ １ Erlang 分布 （ ),( lkΓ,分布 ） 是 PH 分布,
证明 在 1=k 时,),( lkΓ 分布就是指数分布,为了得到一些直观的认识,我们先看 2=k 情形,
我们证明 ),2( lΓ 分布是以,=a )0,1(,
~
Q

=
l
ll
0 为最小表示的 PH 分布,为此,我们记以
}2,1,0{ 为状态空间,初值 10 =x,并以 Q
=
ll
ll0
0
为转移速率矩阵的连续时间的 Markov
链为 tx,利用


=



n
nnn n
)1(
)1()1(
1
11 1
,
我们得到
e
~
Q t te l

= 1
11



=
∞
=
∑
t
n
n
int
e
n
tne
l
l l
0 !
)()1(


=

t
tt
e
tee
l
ll l
于是由定理 ７,１８ 知道 tx 首达 0 的时刻 t 的分布为
etP )0,1()( =>t
~
Q t

1
1 tet ll?+= )1(
,
由此得到 t 的分布密度为 )(),0[2 tIte t ∞?ll,即为 ),2( lΓ 分布,从而 ),2( lΓ 分布为 PH 分布,
对于一般的 k,我们记以 },,1,0{ kL 为状态空间,初值 10 =x,并以
Q
=
ll
ll
ll
OO
0
为转移速率矩阵的连续 时间的 Markov 链为 tx,利用
199
n


1
11
11
OO


+
=


n
n
nnn
knnnn
nn
nnn
knnnnnn
)1(
)1()1(
)1()1()1()1(
)1()1()1()1()1()1()1(
1
21
21
O
OOO
L
LL
,
我们得到
e
~
Q t
t
e
l




= 1
11
11
OO
=

1
1
)(1
)()(1
2
12
t
tt
ttt
e
k
t
l
ll
lll
l OOO
L
L
,
由定理 ７,１８ 知道 tx 首达 0 的时刻 t 的分布为
etP )0,0,1()( L=>t
~
Q t
1
1
M t
k
ekttt llll?
++++= ))!1(
)(
!2
)(1( 12 L,
即 t 的分布密度为 )()!1( )( ),0[
1
tIekt t
k
∞
lll,就是 ),( lkΓ 分布,从而 ),( lkΓ 分布为 PH 分布,
命题 ７,２２ PH 随机变量的混合仍为 PH 随机变量,即,若 )(),( xGxF 均为 PH 分布,则
)10(),()1()( <<?+ lll xGxF,也是 PH 分布,
( 证 明提 示 设它们分别有表示 ),(
)1(~
)1( Qa 与 ),(
)2(~
)2( Qa,那么 由 直观可以看出,
l((,)1(a )1( l? )),)2(~
)1(~
)2(


Q
Qa 就是 )()1()( xGxF ll?+ 的一个表示 ),
例 ７,２３ （ 超指数分布 － mH 分布 ）
)1()(
1
t
i
m
i
ietF la?
=
= ∑,
其表示为 =aa ),,( ~Q ),,( 1 maa L,
~
Q是对角元素为 mll,,1 L 的对角矩阵,
与超指数分布有关的还有 2?Coxian 型分布,假定随机变量 21,XX 相互独立,分布服从分布
200
21
,ll ExpExp,而随机变量 x 是混合型的,它以概率 p 取 21 XX +,而以概率 p?1 取 1X,则随机变量 x 的分布称为 2?Coxian 型分布,
定理 ７,２３ PH 分布是常数与连续型随机变量的混合分布
证明 显见 0)0( at ==P,而且在 00 =a 时,t 具有分布密度 ( 利用 Q 的行和为 1,即
q1Q =~ )
=+ )(tf eN ),,( 1 aa L
~
Q? t q T,
然而,当 00 >a 时,1)(
10
<= ∑∫
=
+
∞ N
k
kdttf a,此时 )(1
1
0
tf +?a 才是 分布密度,于是 PH 随机变量 t
的分布是如下的一个混合分布,
以 0a 的概率取常值 0,而以 01 a? 的概率具有分布密度 )(1 1
0
tf +?a,
在实际情形中,常出现 00 =a 情形,此时 PH 分布是有密度的,注意此,有密度部分,看起来像,矩阵型指数分布,,这是指数分布的一种推广,
命题 ７,２４ （ PH 分布的矩母函数 ）
若随机变量 t 服从 PH 分布,则它的矩母函数为
∫
∞
+
+== 0 00
0
0 )(1
1)1()( dttfeeEesM sts
aaa
t
),,( 10 Naaa L+=?sI( 1~ )?Q q T,
而 其 k 阶矩为
k
k
k
ds
sMdE )(=t,
5,3 离散 位相型 分布
与 PH 分布的不同处是,这里用离散时间的 Markov 链 nx 来代替前面的连续时间 Markov 链 tx,
定义 ７,２５ 设 nx 的状态空间为 {0,1,…,N},初分布为
)1,0(,)(
0
0 ∑
=
=≤≤==
N
j
jj NjjP aax,
转移矩阵为
P

= ~01
Pp T,其中?I
~P
为可逆,
201
nx 被状态 0 吸收的时刻 t,是一个取非负整值的随机变量,称为 离散 的 PH 随机变量,它的分布称为 离散
PH 分布,此分布依赖于参数组 =aa ),,( ~P ),,( 0 Naa L,
同样地,不同的参数组可能对应与同一个离散 PH 分布,因此离散 PH 分布也可能有不同的参数表示,
N 最小的那组参数,就称为此 PH 分布的最小表示,
命题 ７,２６ （ 离散 PH 分布的参数表示 ）
仿 PH 分布情形,对于离散 PH 分布,易得

==
),,()( 1
0
N
kP aa at L ~P 1?k p ),2,1( )0( L= =k kT,
这是一个,矩阵型几何分布,,由此可以直接得到它的母函数
)(,,()( 10 NzzP aaa L+=?I z 1~ )?P p T
和各阶矩,
5,4 PH 分布族的封闭性
经过仔细的分析运算后可证明,PH 分布类在多种运算下具有封闭性,即有,
（ １ ） 独立 PH 随机变量的和仍为 PH 随机变量,
( 证 明提 示 设它们分别有表示 ),(
)1(~
)1( Qa 与 ),(
)2(~
)2( Qa,那么可以证明 (=a )1(
0a )
)2(a,


= )2(~
)2()1(
)1(~
~ 0
Qq
QQ
Ta
就是此两个随机变量的和的 一个 PH 型的表示 ),
（ ２ ） 若 hx,都是 PH 随机变量,则它们的最大值 hx ∨,最小值 hx ∧,都是 PH 随机变量,
（ ３ ）,两个 PH 分布的混合分布,仍是 PH 分布,
（ ４ ） 若 }{ kt 为独立同 PH 分布,h 为与它们独立的几何随机变量,那么 ∑
h
t
1
i 也服从 PH 分 布,
［ 注 １ ］ 还可以考虑如下的广义 PH 型分布 etF N ),,(1)( 1 aa L?=
~
Q )(th T1,其中 )(th 为
),( ∞?∞ 上定义的偶函数,满足 )(,0)0( thh = 在 ),0[ ∞ 上非降,有人用广义 PH 型分布的波形设计滤波器 。
［ 注 ２ ］ 关于 排 队系统 1// kEG,1// GEk,1// PHG 与 1//GPH 的讨论可参见 ；
徐光辉,随机服务系统,第 ２ 版,科学出版社,１９８８,
徐光辉,袁学明,排队论,现 代数学手册,随机数学卷,第 １５ 篇,华中科技大学出版社,２０００,
习题 7
1,设 ){},{ nn hx 是相互独立的独立同分布随机变量列,

aax 1
21~
1,

bbh 1
21~
1,
202
假定只有排队系统一条服务线,顾客都在整数分钟的时间到达服务线,且同一时间只会有一个顾客到达,
而第 n 个顾客到达的时刻为 nn xxt ++=? L1,再假定也只在整数分钟的时间才接受服务,先到先服务,
第 n 个顾客需要服务的时间为 nh,记时刻 n 的队伍长度为 nX （ 包括等待的顾客和在接受服务且未完的顾客,称为离散时间的排队过程 ）,证明 nX 是 Markov 链,并求其平稳分布,
2,发廊有 N 个美发师,且只能容纳 )( NM > 个顾客 ),假定第 1+M 个顾客会自动离去,设顾客以强
度为 λ 的指数流到达,而做头发所需时间服从参数为 μ 的指数分布,而且与到达的情形相互独立,求在
时刻 t 在发廊中顾客数 tX 的平稳分布,
3,在 2//MM 系统中,设顾客按参数为 λ 的指数流到达,而服务时间是与之独立的参数为 μ 的独立指
数分布,且 ml 2<,如果改用一个比原来的两个服务员快一倍的一个服务员 ( 即改用 1//MM 系统,
但是服务时间的分布为 m2exp ),请比较这 两种服务系统在稳定情形下的平均排队的队伍长度,并判断其优劣,
4,在 1//MM 中若每当队伍长度大于 N 时就增加一条服务线,而当队伍长度 N≤ 时就撤掉新增加的那条服务线,求排队队伍长度 tX 的平稳分布 ( 队伍长度是指在系统中顾客的数目 )
5 对于 1//MM 排队系统,记在一个服务间隔中到达的顾客数为 n 的概率为 nh,用向前方程导出 na
满足的差分方程,从而证明在一个服务间隔中到达的顾客数的分布为参数为 ml l+ 的几何分布,
6,( 带随机消失的 1//MM )
在下列情形下分别求在时刻 t 系统中顾客数 tX 的平稳分布,
(1),新 来的顾客看到原来的 kX t > ( k ＞ 1) 则以概率 p 留下,而以概率 p?1 离去,
(2),新来的顾客看到原系统中的人数 n 超过 k 则离去,而在 kn ≤ 时则以概率 )1( +?= nk nkp 留下,
而以概率 p?1 离去,
(3),把 (2) 中的 p 改为 n+1 1,
7,出租车站以指数流 λ 来车,而顾客则以指数流 μ 独立的到站,假定一辆车只载一个客人,且顾客到站时如看到已有两人在等候时就自动离开,设 ml <,问在稳定情形下,平均有客人在等候汽车和平均有多少出租车在等候客人?
8,分别在 NMGI // 和 ∞//MGI 系统中,把输入流的计数过程由 Poisson 过程改为复合 Poisson 过
程,说明此时在时刻 t 在系统中的顾客数 tX 仍为 Markov 链,并写出它的转移速率阵 Q,再讨论什么时
203
候有平稳分布,这平稳分布是什么,
9,设顾客按参数为 l 的指数流到达某个服务机构,每人必须相继地接受独立的,服务时间分别服从参数
为 1m 和 2m 的指数分布的两次服务,假定只在两个服务台都有空时顾客才接受服务,否则就离开,求顾
客能接受服务的概率,
10,某实验室有 n 台相同的仪器,它们独立地处在工作状态或调试状态,工作的仪器每台耗电 a 千瓦,
调试的仪器每台耗电 b 千瓦,在时刻 t 工作着的仪器于 ),( htt + 内转为调试的概率为 )(hoh +?l,
而在时刻 t 调试的仪器于 ),( htt + 内重新工作的概率为 )(hoh +?m,求此实验室的平均耗电,
11,系统由 n 个独立地工作的相同元件并联而成,元件的寿命服从参数为 l 的指数分布,另有 m 个同类
的备用元件,又一个失效就立刻换上,备用件用完后就不再更换,证明此系统能工作的时间的分布函数
为 dsesnme smn
n
mst
t

+
∫ ll l
!
)()1( 11)(
0
,
12,假定顾客按强度为 l 的指数流到达服务台,如果他看见有 n 人在排队,则他以概率 n21 排队,而以
概率 n211? 离去,假定服务 台的服务时间服从与之独立的 mexp,将时刻 t 在服务台前排队的人数 ( 包
括正在接受服务的人 ) 记为 tX,再记其分布为 )()( nXPtp tn ==,证明它满足方程
)(2)()2()()(' 111 tptptptp nnnnnn+ ++?= lmlm ( 1≥n ),
)()()(' 010 tptptp lm?=,
进而证明它有平稳分布
n
nnn

=
m
lpp
2
)1(0
2
1 ( 0≥n ),