KNOWECON WIKI

ARTICLE

排队论

排队论 (Queueing Theory) 排队论是运筹学与概率论的重要分支，研究服务系统中因需求与供给的随机性而产生的等待排队现象。其核心问题是：给定到达模式、服务速率和排队规则，推导系统的稳态性能指标，为容量规划与效率优化提供数学依据。丹麦工程师 Erlang 于 1909 年研究电话交换机时开创该领域，此后被广泛应用于电信、交通、制造、计算网络及服务经

浏览 4 更新 2025-12-20

排队论 (Queueing Theory)

排队论是运筹学与概率论的重要分支，研究服务系统中因需求与供给的随机性而产生的等待排队现象。其核心问题是：给定到达模式、服务速率和排队规则，推导系统的稳态性能指标，为容量规划与效率优化提供数学依据。丹麦工程师 Erlang 于 1909 年研究电话交换机时开创该领域，此后被广泛应用于电信、交通、制造、计算网络及服务经济学。

基本要素

排队系统由三个核心组件构成：

  1. 到达过程：顾客到达的时间间隔分布。最经典假设为泊松过程（Poisson process），即到达间隔服从指数分布，具有无记忆性。
  2. 服务机制：服务时间的概率分布（如指数分布、定长分布、Erlang 分布）及服务台数量。单服务台与多服务台（并联）是最常见的拓扑结构。
  3. 排队规则：如先到先服务（FCFS）、后到先服务（LCFS）、优先级服务、轮询（Round-Robin）、随机服务等，不同规则直接影响等待时间的分布特征。

Kendall 记号

学界采用 Kendall 记号 A/S/c/K/N/D A/S/c/K/N/D 统一描述队列：

  • A A ：到达时间分布（M M 为指数/Poisson，D D 为定长，G G 为一般分布）
  • S S ：服务时间分布（同上）
  • c c ：服务台数量
  • K K ：系统容量上限（缺省为 ∞ \infty ）
  • N N ：顾客源规模（缺省为 ∞ \infty ）
  • D D ：排队规则（缺省为 FCFS）

如 M/M/1 M/M/1 表示 Poisson 到达、指数服务、单服务台、无限容量；M/M/c M/M/c 则对应多服务台情形。

关键性能指标

| 指标 | 含义 | |------|------| | L L | 系统中平均顾客数（排队 + 在服务） | | Lq L_q | 队列中平均等待顾客数 | | W W | 顾客在系统中的平均逗留时间 | | Wq W_q | 顾客平均排队等待时间 | | ρ \rho | 服务强度 / 利用率 = λ/(cμ) \lambda / (c\mu) | | Pn P_n | 稳态下系统中有 n n 个顾客的概率 |

Little 定律

Little 定律（L=λW L = \lambda W 与 Lq=λWq L_q = \lambda W_q ）是排队论中最优雅且普适的结论：系统中的平均人数等于有效到达率乘以平均逗留时间。该定律不依赖具体的到达或服务分布，仅要求系统满足稳态与守恒条件，广泛适用于制造、物流及计算系统。其证明简单而深刻，是排队论中为数不多的通用工具之一，也是连接各模型的桥梁。

M/M/1 模型

作为最基础的模型，M/M/1 M/M/1 （Poisson 到达速率 λ \lambda ，指数服务速率 μ \mu ，ρ=λ/μ<1 \rho = \lambda/\mu < 1 ）的稳态解为：

Pn=(1−ρ)ρn,L=ρ1−ρ,W=1μ−λP_n = (1 - \rho)\rho^n, \quad L = \frac{\rho}{1 - \rho}, \quad W = \frac{1}{\mu - \lambda}

当 ρ→1 \rho \to 1 时，L L 与 W W 急剧增长——这是排队系统的非线性核心洞见：高利用率下，等待时间对需求波动极度敏感。例如，利用率从 0.5 提升至 0.9 时，平均队列长度增长九倍，而非线性倍增。

经济学视角

排队论对经济学有深层启示：

  • 拥堵定价：等待时间作为负外部性，个体加入队列时延长的不仅是自己的等待时间，更增加了所有后续到达者的延迟。最优定价（如道路拥堵费）应使个体内部化这一外部成本。
  • 容量投资：规模报酬递增在排队系统中表现为 ρ \rho 接近 1 时的剧烈恶化，最优容量需在闲置成本与等待成本间权衡。
  • 信息不对称：可观察队列长度与不可观察队列在均衡行为上存在本质差异（Naor, 1969），这一发现为行为经济学提供了重要实验基础。

延伸模型

M/M/c M/M/c （多服务台）、M/G/1 M/G/1 （一般服务分布，Pollaczek–Khinchine 公式）、优先级队列及排队网络（Jackson 网络）构成更丰富的研究体系。计算机科学领域中，M/D/1 M/D/1 常用于建模固定包长的网络传输，M/M/c/c M/M/c/c （Erlang 损失公式）用于呼叫中心的人员配置。

M/G/1M/G/1

的 Pollaczek–Khinchine 公式揭示了一个关键事实：即使平均服务时间不变，服务时间方差的增加也会显著延长等待队列。

> 核心直觉：排队系统存在根本性的均值-方差权衡——降低平均等待时间需要增加容量，而减少等待时间的方差则需要平滑需求或增加服务柔性。二者不可同时免费获得。

实际应用

  • 呼叫中心：M/M/c M/M/c 模型用于确定最优坐席数，在服务水平和人力成本间取得平衡。Erlang-C 公式是行业标准工具，被全球客服系统广泛采用。通过调整坐席数量与技能分组，企业可在保障服务质量的同时有效控制运营支出。
  • 交通工程：车流视为排队，瓶颈处服务率决定吞吐量。Vickrey 瓶颈模型将排队论与出行时间选择结合，奠定了拥堵定价的理论基础，可用于设计动态道路收费方案。
  • 供应链与制造：看板（Kanban）系统本质上是有限容量的排队网络，WIP（在制品）上限由 Little 定律直接约束，帮助企业实现精益生产的目标。
  • 计算系统：操作系统调度、数据库锁等待、云资源弹性伸缩均依赖排队论分析尾延迟（tail latency）与服务质量保障，是分布式系统设计的核心工具。
  • 医疗管理：急诊室分诊与手术室排程是典型的多优先级、多服务台排队优化问题，直接影响患者等待时间与医疗资源利用效率。合理配置医护人员和床位资源，能够显著缩短急诊患者的平均候诊时间并改善治疗效果。

关键公式速查

| 模型 | L L | W W | 条件 | |------|-----|-----|------| | M/M/1 M/M/1 | ρ1−ρ \frac{\rho}{1-\rho} | 1μ−λ \frac{1}{\mu-\lambda} | ρ<1 \rho<1 | | M/M/c M/M/c | cρ+ρPQ1−ρ c\rho + \frac{\rho P_Q}{1-\rho} | Lλ \frac{L}{\lambda} | ρ<1 \rho<1 | | M/G/1 M/G/1 | ρ+ρ2(1+Cs2)2(1−ρ) \rho + \frac{\rho^2(1+C_s^2)}{2(1-\rho)} | — | P-K 公式 | | M/D/1 M/D/1 | ρ+ρ22(1−ρ) \rho + \frac{\rho^2}{2(1-\rho)} | — | Cs=0 C_s=0 特例 |

其中 Cs C_s 为服务时间的变异系数，PQ P_Q 为 Erlang-C 延迟概率。Pollaczek–Khinchine 公式揭示了服务时间方差对平均队列长度的直接影响——即使均值不变，方差的增加也会显著恶化系统性能。这一结论对实际运营管理具有重要指导意义：减少服务时间的波动往往比单纯提高平均服务速率更为有效。