第9章排队模型：从 M/M/1 到 M/M/m

系统分析：线性规划、非线性规划与排队模型 · 第 9 / 11 篇（展开目录）

从线性规划建模、单纯形法、对偶与灵敏度、运输与指派，到非线性规划、随机过程、马尔可夫链、排队模型和决策分析，每章都配手算例题和自测，最后一章用综合例题把方法串起来。

约 35 分钟 · 需要第8章的生灭过程

读完你能： 读懂 A/S/m/K/L 记号；用 Little 公式在 L、Q、W、D 之间换算；计算 M/M/1、M/M/1/N、M/M/m、Mb/M/1 的性能指标；判断稳定条件；用等待时间分布求“等太久”的概率；用成本比较两种服务方案；比较三种常见排队设计并说明哪个指标对顾客最重要。

1. 排队系统与记号

一个排队系统由三部分组成：到达（规则还是随机，单个还是成批）、服务机构（几个服务台、服务时间分布）、排队规则（通常先到先服务）。

肯德尔记号 A/S/m/K/L：

位置	含义	常见取值
A	到达过程	M = 泊松到达（间隔为指数分布）
S	服务时间分布	M = 指数分布
m	服务台个数	1, 2, …
K	系统最大容量（含正在服务的）	省略表示无限
L	顾客总体规模	省略表示无限

四个基本指标（稳态下）：

记号	含义
$L$	系统中的平均顾客数（排队的 + 正在服务的）
$Q$	队列中的平均顾客数
$W$	顾客在系统中的平均停留时间
$D$	顾客在队列中的平均等待时间

2. Little 公式

L=\lambda W,\qquad Q=\lambda D,\qquad W=D+\frac1\mu .

$\lambda$ 是实际进入系统的到达率。Little 公式几乎不依赖具体分布和排队规则，只要系统达到稳态就成立，所以通常只需算出 $L,Q,W,D$ 中的一个，其余三个都能换算出来。

3. M/M/1

泊松到达（速率 $\lambda$ ）、指数服务（速率 $\mu$ ）、一个服务台。系统内人数 $N(t)$ 是 $\lambda_k=\lambda$ 、 $\mu_k=\mu$ 的生灭过程。记利用率（交通强度）

\rho=\frac\lambda\mu .

由第8章的生灭公式：

\pi_k=\rho^k(1-\rho),\qquad \pi_0=1-\rho\ (\text{系统空闲的概率}),

L=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda},\quad Q=\frac{\rho^2}{1-\rho}=\frac{\lambda^2}{\mu(\mu-\lambda)},\quad W=\frac{1}{\mu-\lambda},\quad D=\frac{\lambda}{\mu(\mu-\lambda)} .

稳定条件： $\rho<1$ ，即 $\lambda<\mu$ 。 $\rho\ge1$ 时 $\sum\rho^k$ 发散，队伍无限增长， $L,W$ 都是无穷大。 $\rho$ 也是服务台忙碌的时间比例。

例1： 零件按每小时 12 个到达检验台，检验速率每小时 15 个。

$\rho=0.8$ ， $L=0.8/0.2=4$ 个， $Q=0.64/0.2=3.2$ 个， $W=1/(15-12)=1/3$ 小时 = 20 分钟， $D=12/(15\times3)=4/15$ 小时 = 16 分钟。检查： $L=\lambda W=12\times\frac13=4$ ✓， $W=D+1/\mu=16+4=20$ 分钟 ✓。

停留时间的分布

在先到先服务下，一个到达者看到 $k$ 个人时，他的停留时间是 $k+1$ 个指数服务时间之和。对 $k$ 加权求和后得到一个简洁的结果：

P(w\le t)=1-e^{-(\mu-\lambda)t},\qquad \text{即}\ w\sim\mathrm{EXP}(\mu-\lambda).

排队等待时间 $d$ ： $P(d=0)=1-\rho$ （到达时系统空）， $P(d\le t)=1-\rho e^{-(\mu-\lambda)t}$ 。

例1 续： 零件在检验台停留超过半小时的概率 $P(w>0.5)=e^{-3\times0.5}=e^{-1.5}=0.223$ 。

用成本选服务速率

例2： 例1中有两台检验设备可选：X 每小时检验 15 个、运行成本每小时 60 元；Y 每小时检验 20 个、成本每小时 90 元。零件在系统中每停留一小时造成 50 元的在制品损失。

每小时总成本 = 运行成本 + 50 × $L$ （系统中平均有 $L$ 个零件在“等着花钱”）：

X： $L=12/3=4$ ，总成本 $60+200=260$ 元/小时；
Y： $L=12/8=1.5$ ，总成本 $90+75=165$ 元/小时。

Y 虽然贵，但总成本低。

4. M/M/1/N：容量有限

系统最多容纳 $N$ 人（排队位置 $N-1$ 个），满员时到达的人被拒绝。这是 $\lambda_k=\lambda\ (k<N)$ 、 $\lambda_N=0$ 的有限生灭过程，状态 $0,1,\dots,N$ ：

\pi_k=\frac{\rho^k(1-\rho)}{1-\rho^{N+1}},\qquad 0\le k\le N\qquad(\rho\ne1).

有限容量下不需要 $\rho<1$ 也存在稳态。 $\rho=1$ 时 $\pi_k=1/(N+1)$ 。

L=\frac{\rho\,[1-\rho^N-N\rho^N(1-\rho)]}{(1-\rho)(1-\rho^{N+1})},\qquad Q=L-(1-\pi_0).

关键是实际进入率：只有系统不满时到达的人才进得来，

\lambda_{\text{eff}}=\lambda(1-\pi_N),\qquad \text{被拒绝的比例}=\pi_N,\qquad \text{吞吐量}=\lambda_{\text{eff}}=\mu(1-\pi_0).

例3： 例1的检验台前只放得下 2 个待检零件（ $N=3$ ），满了的零件转去别处。 $\rho=0.8$ ：

\pi_0=\frac{0.2}{1-0.8^4}=0.339,\quad \pi_1=0.271,\quad \pi_2=0.217,\quad \pi_3=0.173 .

被拒绝的比例 17.3%，实际进入率 $\lambda_{\text{eff}}=12\times0.827=9.92$ 个/小时；
$L=0\times0.339+1\times0.271+2\times0.217+3\times0.173=1.225$ ；
进入系统的零件平均停留 $W=L/\lambda_{\text{eff}}=0.1235$ 小时 ≈ 7.4 分钟。

W 用哪个到达率

按 Little 公式，进入系统的顾客平均停留 $L/\lambda_{\text{eff}}$ 。有些公式表里的

W=\frac{1-\rho^N-N\rho^N(1-\rho)}{\mu(1-\rho)(1-\rho^{N+1})}

实际上等于 $L/\lambda$ （例3中为 0.102 小时），相当于把被拒绝的顾客也算进来、停留时间记为 0。两者含义不同；用公式表时照它的定义算，自己推导时写清楚用的是哪一个。

例3 续（服务速率的经济选择）： 若每完成一个零件得利润 $q$ ，以速率 $\mu$ 运行的成本为 $C\mu$ ，则单位时间利润 $P=q\cdot\mu(1-\pi_0)-C\mu$ ，对 $\mu$ 求极值即可找到最划算的服务速率。

5. M/M/m：多个服务台共用一条队

$m$ 个相同的服务台，每个速率 $\mu$ ；有空闲服务台就立刻服务，否则排队。生灭速率 $\lambda_k=\lambda$ ， $\mu_k=k\mu\ (k<m)$ ， $\mu_k=m\mu\ (k\ge m)$ 。记

\rho=\frac{\lambda}{m\mu}\quad(\text{每个服务台的利用率，稳定条件}\ \rho<1),\qquad a=m\rho=\frac\lambda\mu .

\pi_0=\Big[\sum_{k=0}^{m-1}\frac{a^k}{k!}+\frac{a^m}{m!(1-\rho)}\Big]^{-1},\qquad \pi_k=\begin{cases}\pi_0\,a^k/k!,&k<m\\[2pt]\pi_0\,m^m\rho^k/m!,&k\ge m\end{cases}

Q=\frac{\rho\,a^m\pi_0}{m!(1-\rho)^2},\qquad L=Q+\frac\lambda\mu,\qquad W=\frac L\lambda,\qquad D=\frac Q\lambda=W-\frac1\mu .

平均忙碌的服务台数 $B=\lambda/\mu$ ；到达者需要排队的概率 $P(\text{等待})=\dfrac{a^m\pi_0}{m!(1-\rho)}$ 。

例4： 汽修店有 3 名技师，每人每天修 6 辆，顾客每天来 15 辆。 $\rho=15/18=5/6$ ， $a=2.5$ 。

\pi_0=\Big[1+2.5+\frac{2.5^2}{2}+\frac{2.5^3}{6\times(1/6)}\Big]^{-1}=\big[1+2.5+3.125+15.625\big]^{-1}=\frac{1}{22.25}=0.0449 .

Q=\frac{(5/6)(2.5^3)(0.0449)}{6\times(1/6)^2}=3.51,\quad L=3.51+2.5=6.01,\quad W=\frac{6.01}{15}=0.401\ \text{天},\quad D=\frac{3.51}{15}=0.234\ \text{天}.

70% 的顾客到达时需要排队。

6. 三种设计，哪个更好？

总到达率 $\lambda$ ，总服务能力 $3\mu$ ，三种组织方式：

系统	模型	$W$	例4的数据（ $\lambda=15,\ \mu=6$ ）
1：三个窗口各卖一种，顾客按需求分流	3 个独立的 M/M/1，各为 $(\lambda/3,\ \mu)$	$\dfrac{3}{3\mu-\lambda}$	$W_1=1$ 天
2：一个窗口，三人合力服务一位顾客	M/M/1， $(\lambda,\ 3\mu)$	$\dfrac{1}{3\mu-\lambda}$	$W_2=0.333$ 天
3：三个窗口都能卖所有品种，共用一条队	M/M/3， $(\lambda,\ \mu)$	见第5节	$W_3=0.401$ 天

三个系统的稳定条件相同： $\lambda<3\mu$ 。结论（对任意稳定的 $\lambda,\mu$ 都成立）：

W_2<W_3<W_1 .

系统 1 最差：某个窗口排长队时，旁边的窗口可能闲着——服务能力被“隔开”浪费了。
系统 3 比系统 1 好：共用一条队，只要有人空着就能接下一位，没有闲置浪费。
系统 2 的总停留时间最短：人少时系统 3 只有一个人在工作（速率 $\mu$ ），而系统 2 总是三人合力（速率 $3\mu$ ），服务本身更快。

但如果看排队等待时间 $D$ ，结论反过来：例4中 $D_3=0.234$ 天 $<D_2=Q/\lambda=0.278$ 天。系统 3 中顾客更少需要排队，只是被服务得慢一些。

选哪个指标

对顾客来说，通常最在意的是从到达到离开的总时间 $W$ （修车要等多久才能取车）；如果顾客更在意“有没有人在处理我的事”，或者服务过程中他们本来就要在场，那么 $D$ 更重要。比较题要先说清选的是哪个指标、为什么，再下结论。另外还要考虑现实因素：三人合力未必真能把速度提高到 3 倍。

7. Mb/M/1：成批到达

顾客按批到达，批的到达是速率 $\lambda$ 的泊松过程，每批 $b$ 个；单个服务台逐个服务，速率 $\mu$ 。利用率 $\rho=b\lambda/\mu<1$ 。

用母函数解速率平衡方程，得到

L=\frac{\rho(1+b)}{2(1-\rho)},\qquad Q=L-\rho,\qquad W=\frac{L}{\lambda b}=\frac{1+b}{2\mu(1-\rho)},\qquad D=W-\frac1\mu .

注意这里 Little 公式用的是个体到达率 $\lambda b$ 。

例5： 零件每批 3 个，每小时 4 批，检验速率每小时 15 个。 $\rho=12/15=0.8$ （与例1相同）：

L=\frac{0.8\times4}{2\times0.2}=8,\quad Q=7.2,\quad W=\frac{8}{12}=0.667\ \text{小时},\quad D=0.6\ \text{小时}.

同样的利用率下，成批到达让 $L$ 从 4 变成 8、 $W$ 从 20 分钟变成 40 分钟——同一批的零件一到就开始互相等待。

8. 小结

模型	稳定条件	关键公式
M/M/1	$\lambda<\mu$	$\pi_k=\rho^k(1-\rho)$ ， $L=\frac{\rho}{1-\rho}$ ， $W=\frac{1}{\mu-\lambda}$ ， $w\sim\mathrm{EXP}(\mu-\lambda)$
M/M/1/N	总有稳态	$\pi_k=\frac{\rho^k(1-\rho)}{1-\rho^{N+1}}$ ， $\lambda_{\text{eff}}=\lambda(1-\pi_N)$
M/M/m	$\lambda<m\mu$	$\pi_0$ 见第5节， $Q=\frac{\rho a^m\pi_0}{m!(1-\rho)^2}$ ， $L=Q+\lambda/\mu$
Mb/M/1	$b\lambda<\mu$	$L=\frac{\rho(1+b)}{2(1-\rho)}$ ， $W=\frac{L}{\lambda b}$

Little 公式 $L=\lambda W$ 、 $Q=\lambda D$ 贯穿所有模型。

自测

1. 餐饮公司有 3 名厨师，订单每天 15 单（泊松），每名厨师独立完成一单的速率为每天 9 单。求 L、Q、W、D。

M/M/3， $\rho=15/27=5/9$ ， $a=15/9=5/3$ 。 $\pi_0=\big[1+\frac53+\frac{(5/3)^2}{2}+\frac{(5/3)^3}{6(1-5/9)}\big]^{-1}=\big[1+1.667+1.389+1.736\big]^{-1}=0.1727$ 。 $Q=\frac{(5/9)(5/3)^3(0.1727)}{6(4/9)^2}=0.3747$ ， $L=Q+5/3=2.041$ ， $W=L/15=0.136$ 天， $D=Q/15=0.025$ 天。

2. 例1中如果到达率涨到每小时 14 个，W 变成多少？这说明什么？

$W=1/(15-14)=1$ 小时，是原来 20 分钟的 3 倍。利用率从 0.8 升到 0.933，等待时间急剧上升——接近满负荷时，到达率的小幅增加会让排队时间大幅增加，这是规划产能时要留余量的原因。

3. 图书馆某本新书只允许一位读者预约。借阅者按速率 λ 到达，借期服从均值 1/μ 的指数分布。写出状态与稳态概率。

状态 0：书在馆；1：借出、无预约；2：借出、有一人预约（再来的人被拒绝）。这是 $N=2$ 的 M/M/1/N： $\lambda\pi_0=\mu\pi_1$ ， $\lambda\pi_1=\mu\pi_2$ 。令 $\rho=\lambda/\mu$ ， $\pi_0=\dfrac{1}{1+\rho+\rho^2}$ ， $\pi_1=\rho\pi_0$ ， $\pi_2=\rho^2\pi_0$ 。（还书后若有预约，书直接借给预约者，状态 2 → 1。）