Lec6 一般到达或服务模型 排队论及其应用 教学课件

(z) z
0
(1
z)K(z)
K(z) 1
0K
(z)
|z 1
/
0
1
1
பைடு நூலகம்
0 1 其 中 E[servicetime]
综上，(z)(1)(1z)K(z)
K(z)z
13
获得Π(z)，即可获得{πn}；或者从稳态方程递 归获得
i1
i 0ki jkij1, (i0,1,2,...) j1
当i=0，求出π1； 当i=1，求出π2； 当i=2，求出π3； …
k0 k1 k2
P p ij 0 k 0 k1
0 0 k0
0 0 0
1
K
1
kn
n0
K 1
1 kn
n0
K 2
1 kn
n0
K 3
1 kn
n0
1 k 0
由 π πP，得到M/G/1/K的稳态方程
0ki
i1
kj ij1
(i 0,1,2,
,K1)
i 1Kj01jj1
有i个客户的概率=客户离开后瞬间系统中有i个 客户的概率,即pn=πn 下面我们证明这一点
18
证明πn=pn
πn：一个客户离开后瞬间系统中有n个客户的概率 pn：任意时刻系统中有n个客户的概率 证明：
考虑在一段时间T内系统的演变。令An(T)表示时间T内系统 发生nn+1状态迁移的次数，Dn(T)表示时间T内发生 nn-1状态迁移的次数。两种迁移的次数之差最多为1。
P r{ 到 达 P 客 r{ 户 客 发 户 现 能 系 够 统 进 内 入 已 系 有 统 n } 个 客 户 } 1 q n q K
因此qn 1qK n，求qn’，需要获得qK’
对(1 于 Mq K /G)/ 1/ K(1 ， 下p 0 式) 成立q K 1 p 0(= )
因此 qK 1 p0,qn (1p 0)n，需获得p0
(Xn1)
当Xn≥1，第n个客户离开立即开 始服务第n+1个客户；
(Xn0)
但是当Xn=0，必须先等第n+1个 客户到达，才开始服务
这里An+1是服务器服务第n+1个客户这段时间S(n+1) 内到达排队系统的客户数量。 An+1和S(n+1)均为独 立随机变量，稳态下与n无关。用A和S来表示。有
P r{ A a } 0P r(A a|S t)d B (t)
序列{πi}，{kji}的生成函数
(z) jzj, Ki(z) kjizj
j0
j0
将展开方程两边乘以相应的zj再相加，整理得
( z ) 0 K 0 ( z ) 1 K 1 ( z ) 2 z K 2 ( z ) j 1 z j K j 1 ( z )
28
考虑一个特例，服务器的服务时间服从指数分 布，且有两档服务速率（“慢”和“快”）， 分别是系统空和非空时的服务速率。
A和S相互独立，所以
Pr{Aa|St}et(t)a
a!
泊松到达，时间t内 到达a个客户的概率
3
X n 1X n U (X n)A两边平方
X n 2 1 X n 2 U 2 ( X n ) A 2 2 X n U ( X n ) 2 A U ( X n ) 2 A X n
再取期望，得
20
有限等待位的M/G/1/K模型
M/G/1/K与M/G/1的关系类似于M/M/1/K与 M/M/1的关系
一个服务器，任意服务时间分布，平均服务速率μ， K-1个等待位
PK等式不成立 排队系统只有K+1个状态，相应地，单步转移
概率矩阵 (K+1)×(K+1)
21
单步转移矩阵
k
0
k1
k2
当T→∞，X(0)和X(T)是有限的，综合以上条件
limDn(T) limAn(T) T D(T) T A(T)
由于客户到达事件独立于系统状态，所以
nT li m D D n((T T))T li m A A n((T T))pn
客户到达的泊松过程独立于排队系统中的客 户人数，因此最后一个等号成立
定义：
qn’ ：一个客户到达时系统中已有n个客户的概率， 不管这个到达客户是否能够进入排队系统
qn：一个客户到达并且能够进入排队系统时系统中 已有n个客户的概率
阻塞概率： qK’
参考对M/G/1排队模型中“πn=pn”的证明过程， 对M/G/1/K，有πn=qn。
24
n q n P r{ 到 达 客 户 发 现 系 统 内 已 有 n 个 客 户 |客 户 能 够 进 入 系 统 }
对状态相关服务时间分布的M/G/1排队模型，
稳态存在的条件是
lim sup{j E [Sj]1 }
Crabill, 1968
简单来说，就是对所有Bi(t)，ρi<1。
27
将方程 π πP展开，可以写为 p j j 0 k j , 0 1 k j , 1 2 k j 1 , 2 3 k j 2 , 3 j 1 k 0 , j 1
前 一 个 客 户 离 开 后 瞬 间 系 统 中 有 i个 客 户 }
Pr{Xn1j|Xni} 注意：我们已经证明了Xi的Markov性质
pij
et( t)ji1
dB(t),
0 (ji1)!
(ji1,i1)
Pr{在 服 务 器 服 务 一 个 客 户 的 时 间 t内 到 达 了 ji1个 客 户 }
Var[A]2S2 所以
E [A 2]2S 22
综上 L(D) 2 2S2 2(1)
对于M/G/1，客户离开时的系统参数均值=任 意时刻的系统参数均值（将证明这一点）
7
M/G/1排队系统中平均客户数量
L 2 2S2 2(1)
这个公式被称为Pollaczek-Khintchine等式（PK等式， 波拉切克-辛钦等式）
n 4
n 0
16
服务时间分布B(t)是一个两点分布，
kn
et (t)n
dB(t) 0 n!
1 n!
e5(3/
20)
[5(
3 )]n 20
2 3
e5(1/5)[5(1)]n 5
1 3
2 3n!
e3/4
3 4
n
1 3n!
e1
K(z)2e34 3z/4i 1e1 zi
3 i0 i!
排队论及其应用
Lecture 6 一般到达或服务模型
中国科学技术大学 计算机科学与技术学院
田野
1
M/G/1排队模型
考虑一个排队系统
一个服务器，无穷等待位 客户到达服从泊松过程，速率λ 任意服务时间分布函数，平均服务速率μ（即单位时间
服务μ个客户），服务时间CDF分布：B(t) 用M/G/1表示
|An(T)D n(T)|1
令A(T)和D(T)分别表示时间T内的所有到达和离开事件的个 数，X(T)为T时刻系统内客户个数
D (T ) A (T ) X (0 ) X (T )
19
客户离开后瞬间状态概率
n
lim
T
Dn (T ) D(T )
由于
Dn(T)An(T)Dn(T)An(T) D(T) A(T)X(0)X(T)
kji1
10
由此可以得到{Xi}的一步转移概率
k0 k1 k2 k3
k
0
k1
k2
k3
0
P
{ pij}
0
k0 k1 k2 0 k0 k1
0
0
0
k0
并且
πP = π
或者展开，有
i1
i 0ki jkij1, (i0,1,2,...) j1
11
序列{πi}和{ki}的生成函数
(z) i zi i0
1e0t (n0) Bn(t) 1et (n0)
转移概率
kn0
3 i0 i!
2e34e3z 4 1e1ez 2e3(z1) 4 1ez1
3
3
3
3
17
根据Π(z)和K(z)的关系
(z)(1)(1z)K(z)
K(z)z
由K(z)计算Π(z)，再由Π(z)获得{πn}
P r { 多 于 3 台 机 器 故 障 } 1 0 1 2 3
具体计算过程略 迄今为止我们使用一个假设：任意时间系统中
用系（统即t1,t）客2,t的户3,…时离表刻开示，排客队X户(t系i)1表统，示后2，在瞬3t间i，时系.系..完统统成内内服客的务户客（的户离数数开量 量）。可以用嵌入马尔科夫链模型描述这个排队 系统，用Xi表示X(ti)。
2
离散时间随机过程{Xi}具有Markov性质
证明：
Xn1X Ann11An1
0 E [ U 2 ( X n ) ] E [ A 2 ] 2 E [ X n U ( X n ) ] 2 E [ A U ( X n ) ] 2 E [ A X n ]
由于 U 2 (X n ) U (X n ),X n U (X n ) X n，可得
0E[U(Xn)]E[A2]2E[Xn]2E[AU(Xn)]2E[AXn]
F. Pollaczek：法国数学家 A. Y. Khinchin：苏联数学家（现代概率理论奠基人之
一）
由Little’s Law： 平均逗留时间： W L
平均排队时间： Wq W1
平均排队客户数：Lq Wq
8
例子：
一个单服务器排队系统，客户到达可视为泊松过程， 平均每小时到达10个。服务器平均服务时间5分钟， 服从指数分布。现在如果有一种措施，可以把服务 时间标准差从5分钟减为4分钟，但是平均服务时间 会延长到5.5分钟？问这种措施是否必要？