排队论最早由丹麦工程师Agner Krarup Erlang于1910年提出，旨在解决自动电话系统的问题，成为话务理论的奠基石。Erlang通过研究电话呼叫的随机到达和服务时间，推导出著名的埃尔朗电话损失率公式，用于计算电话系统的呼叫阻塞率，揭示了排队现象的本质。Erlang之后，排队论得到进一步发展。瑞典数学家Felix Balm引入了有限后效流概念，帮助分析复杂的输入过程；美国数学家William Feller提出了生灭过程理论，用以描述顾客到达和离开的动态变化。David George Kendall则通过嵌入马尔科夫链理论对排队系统进行分类，并提出了著名的Kendall符号表示法：A/B/C/d/e/f，简化了排队系统的描述。匈牙利数学家Lajos Takács引入组合方法，提升了求解复杂排队系统的效率。Takács的工作使得排队论在工程、计算机科学等领域得到广泛应用，成为研究排队现象的重要工具。
| 排队场景1 | 排队场景2 |
|---|---|
 |
 |
一、Kendall排队系统分类模型
排队论，又称随机服务系统，是研究顾客随机到达、排队并接受服务的数学理论。
1.1 排队系统的构成要素
排队现象的复杂性在于其具有随机性和动态性。顾客的到来时刻与数量通常是未知的，因此排队系统是一种典型的随机聚散现象。为了更好地理解和分析排队系统，研究者通常将其划分为三个主要要素：输入过程、排队规则和服务机构。
输入过程：输入过程指的是顾客的到达方式。根据顾客到达的特点，输入过程可以进一步分为不同类型。例如，顾客源可以是有限的或无限的。当顾客源有限时，系统的顾客数量是有上限的，而无限顾客源意味着顾客可以源源不断地到达。顾客的到来方式也可以是单独到来或成批到来。单独到来意味着每次只有一个顾客到达系统，而成批到来则表示多个顾客在同一时间到达系统。此外，顾客的到达时间间隔可以是随机的或确定的，随机的到达间隔通常遵循某种概率分布，例如泊松分布（Poisson distribution）。输入过程还可以分为平稳和非平稳两种情况。在平稳输入过程中，顾客到达的平均速率在整个时间段内保持不变；而在非平稳输入过程中，顾客到达的速率会随时间变化，例如高峰期和非高峰期的顾客到达速率可能会有所不同。
排队规则：排队规则决定了顾客在系统中等待和接受服务的方式。常见的排队规则包括即时制（也称为损失制）和等待制。在即时制排队系统中，如果所有服务台都被占用，顾客会立即离开系统，不会排队等待。而在等待制排队系统中，顾客可以在服务台满员时排队等待，直到有服务台空出。服务顺序也是排队规则的一个重要组成部分。最常见的服务顺序是先到先服务（First-Come, First-Served, FCFS），即顾客按到达的顺序接受服务。另一种较少见的服务顺序是后到先服务（Last-Come, First-Served, LCFS），即最新到达的顾客优先接受服务。此外，还可以采用随机服务顺序，即顾客按随机顺序接受服务，或者采用优先权服务规则，即某些顾客比其他顾客享有更高的服务优先级。
服务机构：服务机构是指为顾客提供服务的设施。服务机构可以包含一个或多个服务台（servers）。当系统中有多个服务台时，它们可以以串行或并行的方式运作。串行服务意味着顾客需要依次通过每个服务台，而并行服务则表示顾客可以选择任意一个空闲的服务台。
服务时间的分布也可以分为确定型、纯随机型和中间型三类。确定型服务时间意味着每个顾客的服务时间是固定的；纯随机型服务时间则意味着每个顾客的服务时间是完全随机的，通常遵循某种概率分布，例如指数分布（Exponential distribution）；而中间型服务时间则介于两者之间，即服务时间具有某种随机性，但存在一定的规律性。
1.2 Kendall符号表示法
为了方便描述排队系统的特性，Kendall提出了一种符号表示法，其一般形式为：A/B/C/d/e/f。具体而言：
A代表顾客到达过程的分布类型，常见的分布包括泊松分布（M，Markovian）、一般分布（G，General）、确定型分布（D，Deterministic）等；
B代表服务时间的分布类型，常见的分布类型与A类似；
C表示系统中的服务台数量；
d表示系统的容量，即排队系统中最多可以容纳多少顾客；
e表示顾客的总数目，通常可以是无限的；
f表示排队规则，如先到先服务、后到先服务等。
通过这种符号表示法，我们可以简洁地描述各种不同的排队系统，亦即不同的排队模型。例如：
M/M/S/∞表示一个输入过程为泊松流，服务时间服从指数分布，系统有S个并行服务台，且系统容量为无限的排队系统。
M/G/1/∞表示输入过程为泊松流，服务时间服从一般概率分布，系统中只有一个服务台，容量为无限的排队系统。
GI/M/1/∞表示顾客到达的时间间隔服从一般概率分布，服务时间服从指数分布，系统中有一个服务台，且容量为无限的排队系统。
EK/G/1/K表示顾客的到达时间间隔服从K阶Erlang分布，服务时间服从一般概率分布，系统中有一个服务台，且容量为K的排队系统。
D/M/S/K表示顾客的到达时间间隔是确定的，服务时间服从指数分布，系统中有S个并行服务台，容量为K的排队系统。
1.3 常见的排队分布
| 分布类型 | 描述 | 概率密度函数 (PDF) | 期望 (E) | 方差 (Var) |
|---|---|---|---|---|
| 泊松分布 (Poisson) | 单位时间内事件到达的数量 | \(f(k;λ) =\frac{ λ^k*e^{-λ}}{k!}\) | E(X) = λ | Var(X) = λ |
| 指数分布 (Exponential) | 两个事件到达之间的时间间隔 | \(f(x;λ) = λe^{-λx}, x ≥ 0\) | E(X) = 1/λ | Var(X) = 1/λ² |
| 正态分布 (Normal) | 服务时间或其他连续变量 | \(f(x; \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\) | E(X) = μ | Var(X) = σ² |
| 伽玛分布 (Gamma) | 累积服务时间 | \(f(x; k, \theta) = \frac{x^{k-1} e^{-x/\theta}}{\theta^k \Gamma(k)}, \quad x > 0\) | E(X) = kθ | Var(X) = kθ² |
| Erlang分布 (Erlang) | 多阶段服务系统 | \(f(x; k, \lambda) = \frac{\lambda^k x^{k-1}e^{-\lambda x}}{(k-1)!} \quad \text{for } x > 0\) | E(X) = k/λ | Var(X) = k/λ² |
| 一般分布 (General, G) | 非特定分布类型 | - | E(X) = μ | Var(X) = σ² |
| 泊松分布 (Poisson) | 指数分布 (Exponential) | 伽玛分布 (Gamma) |
|---|---|---|
 |
 |
 |
1.4 排队分布的参数估计
根据统计学参数估计知识，可以跟踪在服务系统的到达时刻和接受服务的时间长度，估计出排队论常用的两个参数\(\lambda,\mu\)。
- 顾客到达间隔时间（根据\(\lambda = 0.5\)模拟，样本量为20）：
- 顾客服务时间（根据\(\mu = 0.7\)模拟，样本量为20）：
- 到达率\(\lambda\)的估计。根据顾客到达间隔时间的均值\(\bar{X}\)，\(\lambda\)的估计值为：
- 服务率\(\mu\)的估计。根据顾客服务时间的均值\(\bar{Y}\)，\(\mu\)的估计值为：
- 结果。估计到达率\(\lambda\)为：0.548；估计服务率\(\mu\)为：0.808，这些估计值基于我们模拟的指数分布数据，接近真实的\(\lambda = 0.5\)和 \(\mu = 0.7\)。
二、排队系统绩效指标
系统空闲概率 \(P_0\)
- 定义：系统中没有顾客的概率，即所有服务台都空闲。
- 计算：对于 M/M/1 和 M/M/c 系统，\(P_0\) 是基础指标，表明系统在无负载状态下的可能性。
系统中有 \(n\) 个顾客的概率 \(P_n\)
- 定义：系统中恰好有 \(n\) 个顾客的概率，反映系统在不同状态下的可能性。它是分析系统排队长度分布的重要指标。
平均队列长度 \(L_q\)
- 定义：排队系统中平均排队的顾客数，不包括正在接受服务的顾客。
- 计算：对于 M/M/1 和 M/M/c 系统，队列长度取决于顾客到达率、服务率及服务台数量。
顾客在系统逗留时间 \(L_s\)
- 定义：系统中包括排队和正在接受服务的顾客的平均数量。
- 公式：
- 对于 M/M/1 系统，\(L_s = \frac{\lambda}{\mu - \lambda}\)。
- 对于 M/M/c 系统，公式更加复杂，但反映顾客到达和服务之间的平衡。
顾客的平均等待时间 \(W_q\)
- 定义：顾客在系统中排队的平均等待时间，不包括服务时间。
- 计算：对于 M/M/1 系统，\(W_q = \frac{L_q}{\lambda}\)；对于 M/M/c 系统，考虑了多个服务台及系统负载情况。
顾客的平均系统时间 \(W_s\)
- 定义：顾客在系统中的总时间，包括等待时间和服务时间。
- 计算：对于 M/M/1 系统，\(W_s = \frac{1}{\mu - \lambda}\)；对于 M/M/c 系统，\(W = W_q + \frac{1}{\mu}\)。该指标反映顾客从到达系统到离开的总时间。
通过这些指标，可以有效评估排队系统的服务效率、顾客的等待情况以及系统的稳定性。
| 排队系统指标 | M/M/1 | M/M/c |
|---|---|---|
| 到达过程 | 顾客到达服从泊松分布，平均到达率为 \(\lambda\) | 顾客到达服从泊松分布，平均到达率为 \(\lambda\) |
| 服务过程 | 服务时间服从指数分布，服务率为 \(\mu\) | 服务时间服从指数分布，服务率为 \(\mu\) |
| 服务台数量 | 1个服务台 | \(c\) 个服务台 |
| 系统空闲概率 | \(P_0 = 1 - \rho\)，其中 \(\rho = \frac{\lambda}{\mu}\) | \(P_0 = \left[ \sum_{n=0}^{c-1} \frac{(\lambda/\mu)^n}{n!} + \frac{(\lambda/\mu)^c}{c! (1 - \rho)} \right]^{-1}\)，其中 \(\rho = \frac{\lambda}{c\mu}\) |
| 系统中有 \(n\) 个顾客的概率 | \(P_n = (1 - \rho) \rho^n\) | 对于 \(n < c\)，有 \(P_n = \frac{(\lambda/\mu)^n}{n!} P_0\)；对于 \(n \geq c\)，有 \(P_n = \frac{(\lambda/\mu)^n}{c^c (c!) (1-\rho)} P_0\) |
| 平均队列长度 | \(L_q = \frac{\rho^2}{1 - \rho}\) | \(L_q = P_0 \frac{(\lambda/\mu)^c \rho}{c! (1 - \rho)^2}\) |
| 系统中的平均顾客数 | \(L_s = \frac{\rho}{1 - \rho}\) | \(L = L_q + \frac{\lambda}{\mu}\) |
| 顾客的平均等待时间 | \(W_q = \frac{\rho}{\mu (1 - \rho)}\) | \(W_q = \frac{L_q}{\lambda}\) |
| 顾客在系统逗留时间 | \(W_s = \frac{1}{\mu - \lambda}\) | \(W = W_q + \frac{1}{\mu}\) |
三、排队系统性能指标的Python计算
import numpy as np
# 参数设置
lambda_rate = 5 # 平均到达率
mu_rate = 7 # 服务率
c = 3 # 服务台数量
# M/M/1 系统计算
rho = lambda_rate / mu_rate
P0_mm1 = 1 - rho
Pn_mm1 = [(1 - rho) * (rho ** i) for i in range(10)] # 计算前10个概率
Lq_mm1 = (rho ** 2) / (1 - rho)
Ls_mm1 = rho / (1 - rho)
Wq_mm1 = (rho / (mu_rate * (1 - rho)))
Ws_mm1 = 1 / (mu_rate - lambda_rate)
# M/M/c 系统计算
factorial = np.math.factorial
P0_mmc = 1 / (1 + sum((lambda_rate / mu_rate) ** i / factorial(i) for i in range(c)) + (lambda_rate / mu_rate) ** c / (factorial(c) * (1 - rho)))
Pn_mmc = [P0_mmc * (lambda_rate / mu_rate) ** i / factorial(i) if i < c else P0_mmc * (lambda_rate / mu_rate) ** i / (c ** c * factorial(c) * (1 - rho)) for i in range(10)]
Lq_mmc = P0_mmc * ((lambda_rate / mu_rate) ** c * rho) / (factorial(c) * (1 - rho) ** 2)
L_mmc = Lq_mmc + lambda_rate / mu_rate
Wq_mmc = Lq_mmc / lambda_rate
W_mmc = Wq_mmc + 1 / mu_rate
# 输出表格
print("排队系统指标 | M/M/1 | M/M/c")
print("| --- | --- | --- |")
print("到达过程 | 顾客到达服从泊松分布，平均到达率为 {:.2f} | 顾客到达服从泊松分布，平均到达率为 {:.2f} |".format(lambda_rate, lambda_rate))
print("服务过程 | 服务时间服从指数分布，服务率为 {:.2f} | 服务时间服从指数分布，服务率为 {:.2f} |".format(mu_rate, mu_rate))
print("服务台数量 | 1个服务台 | {} 个服务台 |".format(c))
print("系统空闲概率 | {:.2f} = 1 - {:.2f} | {:.2f} |".format(P0_mm1, rho, P0_mmc))
print("系统中有 n 个顾客的概率 | {} | {} 到 {} |".format(Pn_mm1[:3], Pn_mmc[:3], Pn_mmc[-3:])) # 展示部分概率
print("平均队列长度 | {:.2f} | {:.2f} |".format(Lq_mm1, Lq_mmc))
print("系统中的平均顾客数 | {:.2f} | {:.2f} |".format(Ls_mm1, L_mmc))
print("顾客的平均等待时间 | {:.2f} | {:.2f} |".format(Wq_mm1, Wq_mmc))
print("顾客在系统逗留时间 | {:.2f} | {:.2f} |".format(Ws_mm1, W_mmc))
| 排队系统指标 | M/M/1 | M/M/c |
|---|---|---|
| 到达过程 | 顾客到达服从泊松分布，平均到达率为 5.00 | 顾客到达服从泊松分布，平均到达率为 5.00 |
| 服务过程 | 服务时间服从指数分布，服务率为 7.00 | 服务时间服从指数分布，服务率为 7.00 |
| 服务台数量 | 1个服务台 | 3 个服务台 |
| 系统空闲概率 | 0.29 = 1 - 0.71 | 0.31 |
| 系统中有 n 个顾客的概率 | [0.29, 0.20, 0.15] | [0.31, 0.22, 0.08] 到 [0.00064, 0.00046, 0.00033] |
| 平均队列长度 | 1.79 | 0.17 |
| 系统中的平均顾客数 | 2.50 | 0.88 |
| 顾客的平均等待时间 | 0.36 | 0.03 |
| 顾客在系统逗留时间 | 0.50 | 0.18 |
总结
排队系统数学模型是用于分析和预测服务设施中顾客等待时间和系统负载的工具。这些模型通常基于几个关键假设，如顾客到达服从泊松分布，服务时间服从指数分布。M/M/1模型，包含单个服务台和一个等待队列，是最基本的排队模型，适用于单个服务点的场景。M/M/c模型则扩展到多个服务台，适用于服务台数量较多的情况，如银行柜台或呼叫中心。
这些模型的关键性能指标包括系统空闲概率、顾客在系统中的概率、平均队列长度、系统中的平均顾客数、顾客的平均等待时间和逗留时间。通过这些指标，管理者可以评估服务效率、优化资源配置，并改善顾客体验。排队理论的应用有助于减少等待时间、提高服务质量和运营效率，是现代服务管理和工业工程不可或缺的一部分。
