1
0 0
λ 0w0 μ 1w1 λn1wn1 (λn
μ
n)wn
μn1 wn1
2 稳态的“概率流”平衡：
μn1wn1 λnwn
解得
wn
λ n1L λ 1λ 0 μ nL μ 2μ 1
排队系统中普适性的定律，统计量服从的公式 对到达过程、服务时间分布、服务规则无特殊要求 描述长时间平稳后的系统
W 形式为：L = λ·W
L ： 系统中的平均顾客数 λ： 平均(有效)到达率 W： 顾客在系统中所消耗的平均时间
M/M/1 或 M/M/1/∞排队模型
λ
λ
λ
λ
λ
0
1
2
3
4
μ
μ
μ
μ
μ
到达系统的顾客数服从泊松分布，参数 λ
负载因子ρ= λ/μ<1 的条件下，具有稳态分布：
wn
λ n1L λ 的概率
λ μ
n
wn
w0 (1
ρn
ρ)ρn
w0
1
λ μ
λ μ
n
系统平均用户数：
L n wn
n0
1ρ
ρd
ρn
dρ n0 ρ λ
μ
用户数的方差：
一定间隔内到达的顾客数服从泊松分布，到达率 λ 到达的时间间隔服从负指数分布，平均到达时间 1 / λ
排队系统的服务时间
缓冲区
服务者
服务时间
服务时间：服务器处理每个顾客业务所需的时间
是与服务器对具体业务的处理能力有关的随机量 一般用处理业务所需的时间的分布来表征 典型的服务时间：负指数分布
服务时间服从负指数分布，平均服务时间 1 / μ 顾客离开率： μ
生灭过程
任何时刻，状态最多只能转移到临近状态
若处于0状态，则只能转移到状态1。
若在 t 时刻处于n状态，在(t,t+Δt)间隔内
转移到状态（n+1）的概率为 λn(t)Δt+o(Δt)
转移到状态（n-1）的概率为 μn(t)Δt+o(Δt)
转移到其他状态的概率为 o(Δt)
λn(t)Δt+o(Δt)
主要内容
生灭过程
特点 稳态分析
排队论基础
排队过程的基本参数和问题 排队问题的分析方法 排队问题的Little定律
排队问题举例
例1 M/M/1/∞、例2 M/M/1/N 例3 顾客成批到达的排队问题 例4 电话交换问题（M/M/N/N） 例5 M/M/s/∞排队系统、例6 M/M/s/k 例7 机器维修问题
每个元件的正常工作时间服从负指数分布 若t时刻有n个元件失效，则在(t,t+Δt)时间间隔内产生一个
新的失效元件的概率是λnΔt+o(Δt)，修复一个元件的概率是 μnΔt+o(Δt) 在(t,t+Δt)间隔内多个元件失效或修复的概率是o(Δt) 系统正常工作至少要有k个元件正常工作——当（M-k+1） 元件失效时系统就停止工作，等待修复
1
M/M/S/∞
μ 2μ
λλλ
S
S+1
sμ sμ sμ
稳定状态时，各状态的概率
0 λ0 1 λ1 2 λ2 3 λ3 μ1 μ2 μ3 μ4
Q
λ0 μ1
λ0 (μ 1 λ1 )
0 λ1
0 L
0
L
解 写出Q，列稳态分布方程 法 w’= wQ=0
0
μ2
(μ 2 λ2 )
λ2
L
L
L
L
L L
λλλλ
0
1
2
3
M/M/1/N
μμμμ
λ
N
μ
Mλ (M-1)λ (M-2)λ (M-3)λ
M元件1维修工人 0 μ 1 μ 2 μ 3 μ
λ
N
μ
批量发生
MX/M/1/∞ 0
λ μ
1
λ μ
2
λ μ
3
λ μ
4
λ μ
每次三个
电话接入
λλ
0
1
M/M/N/N
μ 2μ
λλ
N-1
N
(N-1)μ Nμ
S个侍者
λλ
0
平稳的条件：0≤λn≤μn
平衡方程
μn
wn+λn
λ0w0=μ1w1 wn=μn1 wn1+λn1
wn1
局部平衡方程
μn1μw1 wn11
λ0w0 λnwn
与Σwn=1联立，得
wn
λ n1L λ 1λ 0 μ nL μ 2μ 1
w0
生灭过程：实例
例 排队问题(排队论分析)
例 可靠性问题(可靠性分析)： M个元件组成的系统中失效元件数
λ2
L
L
L
L
L L
0 0
λ 0w0 μ 1w1 λn1wn1 (λn
μ
n)wn
μn1 wn1
与Σwn=1联立，可解
wn
λ n1L λ 1λ 0 μ nL μ 2μ 1
w0
平稳的条件：0≤λn≤μn
生灭过程：稳态分析
0
1
λn(t)Δt+o(Δt)
x
n-1
n
n+1
μn(t)Δt+o(Δt)
ρ
μλ
1 ρ2 μ λ2
ρ
λ
1ρ μλ
平均延迟：根据little公式 D = L / λ
1
μλ
轻负载情况下：λ « μ，延迟近似为平均服务时间 业务极度繁忙情况下：λ≈μ，几乎无限延迟
典型排队问题：
最普通情形
λλλλλλ
M/M/1/∞ 0 μ 1 μ 2 μ 3 μ 4 μ 5 μ
队列有限
服务时间服从负指数分布，平均服务时间是1/μ
只有一个服务器
若服务器正忙，则加入排队行列（不限长）
服务器空闲时间到达的顾客立刻得到服务
服务时间与到达过程独立
顾客数组成一个生灭过程
顾客到达和离开对应于生灭过程的生和灭
任意时刻和状态，到达率和离开率均为相同常数
λn=λ，μn=μ
M/M/1 排队模型：应用生灭过程的结论
排队系统的基本模型
缓冲区
服务者
到达
排队
服务中 离开
A/R/S/N/D：常见为 A/R/S，或A/R/S/N
A：到达类型
R：服务时间分布 S：服务者个数 N：系统容量（含服务中用户数），默认无限大 D：排队规则，FIFO
排队系统的到达过程
缓冲区
服务者
到达
到达过程：到达的业务/顾客流构成的随机过程
可以用一定间隔内到达的顾客数的分布来表征 也可以用顾客到达的时间间隔的分布来表征 典型的到达过程：泊松过程
排队系统的基本问题
缓冲区
服务者
概率分布特征:
系统中顾客数的概率分布（及 平均值L） 在排队等候的平均顾客数 LQ
用户在系统中花费时间的概率分布（及 平均值W或D） 顾客排队等候的平均用时 WQ 或 DQ
服务器忙或空闲的概率 服务器处于工作状态的持续时间的分布 用户因为队列满而离开的概率
排队问题的Little定律
0
1
x
n-1
n
n+1
μn(t)Δt+o(Δt)
Q
λ0 μ1
λ0 (μ 1 λ1 )
0 λ1
0 L
0
L
0
μ2
(μ 2 λ2 )
λ2
L
L
L
L
L L
生灭过程：稳态分析
稳态方程 wk(t) qkn 0 k
Q
λ0 μ1
λ0 (μ 1 λ1 )
0 λ1
0 L
0
L
0
μ2
(μ 2 λ2 )