1 基本概念
排队理论研究的是随机到达的个体在服务系统中的等待、接受服务与离开过程。这里的“个体”并不一定是人，也可以是电话呼叫、数据包、车辆、订单或零件。它关注的核心问题包括：系统为何会拥挤、等待时间为何波动、资源配置如何影响效率，以及如何在成本与服务质量之间取得平衡。
1.1 顾客、服务台与队列
在排队理论中，“顾客”指需要服务的对象，“服务台”指提供处理能力的设施或人员，“队列”则是等待服务的顾客集合。一个排队系统通常由到达流、等待区、服务机构和离开机制构成。
不同场景下，这些基本元素的含义会有所变化。例如在银行中，顾客是办理业务的人，服务台是柜台；在网络系统中，顾客可能是请求报文，服务台是路由器或服务器；在工厂中，顾客则可能是待加工的工件。
1.2 到达过程
到达过程描述顾客进入系统的方式与时间规律。它可以是完全随机的，也可以带有一定周期性或相关性。排队论中常用到达率来刻画单位时间内平均到达的顾客数。
常见研究重点包括到达是否独立、到达间隔是否服从某种分布，以及高峰时段是否会导致明显拥塞。对真实系统而言，到达过程往往是建模中最重要的不确定来源之一。
1.3 服务过程
服务过程描述服务台处理顾客所需的时间及其统计特征。服务时间可以是固定的，也可以是随机的；可以由单个服务台完成，也可以由多个服务台并行处理。
服务能力通常用服务率表示，它反映单位时间内平均可完成的服务量。服务时间的长短、波动程度以及不同服务台之间的协调方式，都会显著影响系统性能。
1.4 排队纪律
排队纪律是决定顾客按何种顺序接受服务的规则。它不仅影响等待体验，也会影响系统公平性和整体效率。不同系统会采用不同策略，以适应业务优先级、响应速度或资源利用率的要求。
1.4.1 先到先服务
先到先服务是最常见的规则，先到达队列的顾客先获得服务。它具有直观、公平的特点，因此广泛应用于人工服务和一般性业务流程。
该规则的优点是易于理解和实施，但在某些情况下可能使急需处理的任务无法优先完成，从而降低系统响应速度。
1.4.2 后到先服务
后到先服务是指后进入队列的顾客优先获得服务。这种规则较少出现在普通人工排队中，但在某些计算机调度、存储管理或特殊资源分配场景中会被使用。
它在局部效率上可能较高，但公平性较弱，容易造成早到者等待时间过长。
1.4.3 优先级规则
优先级规则允许某些顾客或任务优先接受服务。优先级可以是静态的，也可以是动态变化的；可以基于任务类别、紧急程度或等待时长来设定。
这类规则常用于医疗分诊、网络流量控制和生产调度等场景。其关键在于如何在高优先级任务和普通任务之间取得合适平衡。
1.5 系统容量与阻塞
系统容量指排队系统能够容纳的最大顾客数，包括正在接受服务的顾客和等待中的顾客。若系统容量有限，当系统已满时，新到达的顾客可能被拒绝进入，这种现象称为阻塞。
阻塞会使部分需求无法被即时接纳，进而影响系统吞吐量和服务可达性。容量设计过小会导致频繁拒绝，容量过大则可能增加建设与维护成本。
1.6 稳态与瞬态分析
稳态分析关注系统经过足够长时间后所达到的长期平均行为，如平均队长、长期利用率和稳态分布。它适用于系统运行较久且统计特征相对稳定的情形。
瞬态分析则研究系统在初始阶段或参数变化后的短期演化过程，强调“随着时间变化会发生什么”。在系统刚启动、需求骤增或策略切换时，瞬态分析尤其重要。
2 排队模型分类
排队模型的分类方式很多，通常按服务台数量、队列结构、容量限制、系统开放性以及到达与服务方式来区分。不同类别对应不同的数学处理方法，也对应不同的应用场景。
2.1 单服务台模型
单服务台模型只有一个服务设施，顾客必须依次接受服务。这是最基础的排队模型，常用于描述单窗口服务、单个机器加工或单一服务器处理请求的情形。
这类模型结构简单，但已能揭示拥挤、等待和稳定性等核心现象，因此常作为更复杂模型的起点。
2.2 多服务台模型
多服务台模型包含多个并行服务台，顾客可同时被不同服务台处理。它适用于银行多窗口、呼叫中心、分布式服务器等场景。
多服务台的引入通常能降低平均等待时间，但也会增加系统分析复杂度，因为需要考虑顾客分配、服务台利用率以及并行协同问题。
2.3 单队列与多队列系统
单队列系统是多个服务台共享一条等待队列，顾客按规则依次被空闲服务台接收。多队列系统则是每个服务台各自拥有一条队列，顾客到达后自行选择或被分配到某一队列。
单队列通常更公平，也更能避免某条队列过长；多队列则在某些情况下更灵活，但容易出现队列长度不均衡的问题。
2.4 有限容量与无限容量模型
有限容量模型对系统可容纳的顾客数设有上限，超过上限的到达会被阻塞或丢弃。无限容量模型则假定等待空间足够大，理论上可容纳任意数量的顾客。
有限容量更接近现实中的带宽限制、缓存空间或物理场地约束；无限容量则便于理论分析，也是许多经典结果的基础假设。
2.5 开放型系统与封闭型系统
开放型系统允许外部顾客进入并在完成服务后离开。大多数现实服务场景都可视为开放型系统，例如呼叫接入、网页请求和门诊挂号。
封闭型系统则假设系统内顾客总数固定，顾客在不同服务站点之间循环流动，常用于制造系统和计算机资源循环利用的分析。
2.6 批量到达与批量服务模型
批量到达模型允许顾客以“成组”方式进入系统，例如一批订单同时提交或一批数据包同时到达。批量服务模型则表示服务台一次处理多个顾客。
这类模型更适合描述突发性较强或操作具有打包特征的场景，但也会使系统状态变化更为剧烈。
3 经典排队模型
经典排队模型通常以到达过程、服务时间分布、服务台数量和系统容量的符号组合来命名，其中最常见的是以 M、G、D 等字母表示不同随机性质的模型。它们构成了排队理论的基础框架。
3.1 M/M/1 模型
M/M/1 模型表示到达过程为泊松过程、服务时间服从指数分布、且只有一个服务台。它是最著名的基础模型之一，具有较强的解析性。
该模型能够清晰展示负载增加时队列长度和等待时间迅速上升的现象，因此常被用作理解排队系统的入门例子。
3.2 M/M/c 模型
M/M/c 模型是单到达泊松、指数服务、多个并行服务台的情形。这里的 c 表示服务台数量。
它常用于描述多窗口服务系统。随着服务台数量增加，等待时间通常下降，但边际改善会逐渐减弱，因此适合用于容量配置分析。
3.3 M/M/1/K 模型
M/M/1/K 模型是在单服务台基础上加入有限容量 K 的设定。系统中的总顾客数不能超过 K，满员时新到达顾客会被拒绝。
该模型常用于研究缓存、有限缓冲区和通信链路中的丢包问题，阻塞概率是其重要指标之一。
3.4 M/G/1 模型
M/G/1 模型假设到达过程为泊松过程，而服务时间服从一般分布。这里的 G 表示一般分布，不局限于指数型。
它比 M/M/1 更接近现实，因为很多系统的服务时间并不满足指数分布。该模型在理论上具有重要地位，适合分析服务时间方差对等待的影响。
3.5 G/M/1 模型
G/M/1 模型与 M/G/1 相对，表示到达过程为一般分布，而服务时间为指数分布。它适合研究到达波动对系统性能的影响。
由于到达间隔不再具有完全随机的泊松特征，该模型在分析上比 M/M/1 更复杂，但更能反映某些周期性或相关性明显的场景。
3.6 G/G/1 模型
G/G/1 模型是最一般的单服务台排队模型之一，到达时间和服务时间都服从一般分布。它在形式上最接近真实系统，但解析求解也最困难。
由于缺少强结构假设，G/G/1 往往需要借助近似方法、数值方法或仿真技术来分析。
3.7 Erlang 模型
Erlang 模型源于通信业务和电话交换系统的研究，主要用于描述呼叫到达、服务与线路占用问题。Erlang 体系中包含若干经典公式，在工程应用中极具影响力。
3.7.1 Erlang B 模型
Erlang B 模型用于无等待区的损失系统，即当所有服务台都忙时，新到达的顾客会直接被阻塞并离开。它常用于电话中继线容量设计。
该模型的核心指标是阻塞概率，可帮助估算在给定服务能力下需要配置多少线路或通道。
3.7.2 Erlang C 模型
Erlang C 模型允许顾客等待，适用于有排队区的呼叫中心或服务台系统。它通常用于估计等待概率和平均等待时间。
与 Erlang B 不同，Erlang C 更适合“可等候”的业务环境，因此在客服系统和人工接入系统中应用广泛。
4 性能指标
排队系统的性能指标用于衡量等待、拥挤与资源利用情况。通过这些指标，可以比较不同设计方案，并为容量规划提供依据。
4.1 平均队长
平均队长是指系统中平均处于等待状态或系统内的顾客数量。它反映拥挤程度，是最常见的性能指标之一。
队长过长通常意味着系统负担较重，也可能对应更高的用户等待成本。
4.2 平均等待时间
平均等待时间表示顾客在开始服务前平均需要等待多久。它直接影响用户体验和业务响应速度，因此在服务系统中尤为重要。
在很多场景里，等待时间比队长更容易被感知，也更便于转化为服务质量评价指标。
4.3 系统逗留时间
系统逗留时间是顾客从进入系统到完成服务离开的总时间，通常包括等待时间与服务时间两部分。
它是衡量整体处理效率的综合指标，适用于比较不同策略下用户在系统中的总耗时。
4.4 服务器利用率
服务器利用率是服务台忙碌时间占总时间的比例。利用率过低意味着资源闲置，过高则容易导致排队积压。
实际设计中通常希望利用率保持在合理区间，而不是一味追求满负荷运行。
4.5 阻塞概率
阻塞概率是顾客到达时因系统已满而无法进入的概率。它主要出现在有限容量系统中。
该指标对于通信链路、缓存系统和预约资源管理非常关键，因为它直接对应丢失业务的风险。
4.6 空闲概率
空闲概率表示系统或服务台在某一时刻处于空闲状态的可能性。它与利用率互为补充，常用于描述资源是否充分被使用。
在部分场景中，适度空闲是必要的，因为它可以提升响应速度并应对随机波动。
4.7 分布与尾部行为
除了平均值，排队理论也关注等待时间、队长等变量的分布形状及其尾部行为。尾部行为反映极端拥堵或超长等待出现的可能性。
在实际系统中，平均值并不足以完全描述风险，尤其当少量极端事件会造成较大影响时，分布尾部更具参考价值。
5 数学分析方法
排队理论之所以能够形成系统化结果，离不开一系列数学工具。不同模型常对应不同的分析方法，有时还需要多种方法联合使用。
5.1 马尔可夫链方法
当系统状态在未来只依赖当前状态而与过去无关时，可以用马尔可夫链来描述。很多经典排队模型都能转化为连续时间马尔可夫链。
这种方法便于构造状态转移关系，并求解稳态概率和长期性能指标。
5.2 生灭过程
生灭过程是一类特殊的马尔可夫链，状态只会向上“生”或向下“灭”变化。它非常适合描述队列长度随到达和服务变化的过程。
由于结构清晰，生灭过程常用于推导稳态分布和递推关系。
5.3 更新过程
更新过程用于描述事件在时间轴上的重复发生，例如顾客到达或服务完成。它能够处理更一般的间隔时间分布，因此比纯泊松假设更灵活。
在分析非指数型模型时，更新过程提供了重要工具。
5.4 拉普拉斯变换与母函数
拉普拉斯变换和母函数常用于把复杂的时域问题转化为更易处理的代数问题。它们可简化卷积、递推和微分方程的求解。
在等待时间分布、忙期分析和系统响应分析中，这类方法尤其常见。
5.5 递推与平衡方程
递推与平衡方程是求解排队模型的基本手段。通过分析系统在各状态间的流入与流出，可以建立一组方程来描述稳态概率。
在许多经典模型中，解出这些方程就能得到队长、等待时间和阻塞概率等结果。
5.6 近似分析方法
当系统过于复杂、无法得到精确解时，常使用近似分析方法，包括流体近似、扩散近似、重负荷近似等。
近似方法不一定给出精确数值，但往往能提供结构清晰、计算成本较低的估计，对工程实践很有价值。
6 随机过程基础
排队理论建立在随机过程理论之上，许多核心模型都可以看作特定随机过程的应用。理解这些基础过程，有助于把握排队模型的性质与适用范围。
6.1 泊松过程
泊松过程是描述随机事件独立、均匀发生的经典模型。它常用于近似顾客到达、呼叫请求或数据包抵达。
由于具有良好的数学性质，泊松过程在排队理论中占据核心位置。
6.2 指数分布与记忆无关性
指数分布具有记忆无关性，即已经等待了一段时间后，未来还需等待多久的分布形式不变。这一性质使得很多排队系统具有马尔可夫性。
虽然真实服务时间未必严格服从指数分布，但这一假设可显著简化分析。
6.3 半马尔可夫过程
半马尔可夫过程允许状态停留时间服从更一般的分布，因此比标准马尔可夫过程更灵活。它适合描述服务时间非指数、状态持续时间不规则的系统。
在一些复杂服务系统中，这类过程比纯马尔可夫模型更贴近现实。
6.4 维纳过程与扩散近似
维纳过程常作为连续时间随机波动的基本模型，在重负荷条件下，排队系统有时可用扩散近似来刻画。
这类方法强调“平均趋势加随机扰动”的结构，适合分析大规模系统的宏观行为。
6.5 稳定性条件
稳定性条件用于判断队列是否会无限增长。一般来说，系统的平均服务能力必须至少能够抵消平均到达负荷，系统才可能稳定。
若长期到达速度超过处理能力，队列长度往往会持续上升，导致系统失控。
7 排队网络
排队网络由多个排队节点相互连接而成，顾客可以在不同节点之间流动。它比单个队列系统更能反映复杂服务链和多阶段处理流程。
7.1 开放排队网络
开放排队网络允许顾客从外部进入网络，并在完成若干节点服务后离开系统。它适用于业务流经多个处理环节后最终退出的场景。
这类网络常用于建模互联网请求、生产流水线和多阶段服务流程。
7.2 闭合排队网络
闭合排队网络中顾客总数固定，个体在网络节点间循环流动。它适合描述固定数量作业在若干资源间反复切换的系统。
这种结构在制造系统和计算机性能分析中十分常见。
7.3 Jackson 网络
Jackson 网络是一类具有可解析性的开放排队网络，具有较强的数学结构。其重要特点是网络各节点之间可以在一定条件下分解处理。
由于可获得较为整齐的稳态结果，Jackson 网络在排队理论中具有里程碑意义。
7.4 Gordon-Newell 网络
Gordon-Newell 网络通常用于闭合排队网络分析，适合研究固定顾客数在多个服务节点间循环的情况。
它为闭合系统提供了经典的稳态分析框架，在性能评估中具有代表性。
7.5 计算机与通信网络中的排队网络
在计算机与通信系统中，数据包、任务和请求往往在多个节点之间转发、缓存与处理，因此很自然地形成排队网络。
这类应用强调端到端时延、吞吐量和拥塞传播，是现代排队理论的重要实践方向。
8 应用领域
排队理论的应用范围十分广泛，凡是存在随机到达、有限资源和等待现象的场景，通常都能找到它的身影。
8.1 通信系统
通信系统中的线路占用、流量拥塞、缓存溢出和呼叫接入，都可以用排队模型描述。排队理论帮助设计更合理的带宽和信道配置方案。
8.2 计算机与操作系统
在计算机系统中，CPU 调度、磁盘访问、进程同步和任务排程都涉及排队问题。排队分析可用于估计响应时间与系统吞吐能力。
8.3 生产制造与物流
制造业中的机器加工、装配等待、物料搬运和仓储分拣，都可视作排队过程。通过建模，可以优化工位配置和物流路径。
8.4 交通运输
交通流、收费站排队、道路瓶颈与机场地面服务等都具有明显的排队特征。排队理论可辅助分析拥堵形成机制与通行效率。
8.5 医疗服务系统
医院挂号、急诊分诊、检查排队和床位分配都属于典型服务系统。排队模型有助于改善患者等待时间与医疗资源使用率。
8.6 金融与服务业
银行、证券、保险、餐饮和客服中心等行业都面临需求波动与服务排队问题。排队分析可支持窗口数量、人员排班和服务流程设计。
8.7 云计算与数据中心
云计算环境中的虚拟机调度、任务迁移、请求分发和负载均衡，本质上也涉及排队与资源共享。排队模型有助于提升弹性和降低延迟。
9 进阶主题
随着应用场景变复杂，排队理论逐步扩展到优化控制、非平稳过程和重尾分布等更深入的问题。进阶主题往往需要更多计算与更强的近似技巧。
9.1 优化与控制
优化与控制关注如何动态调整资源配置、服务策略和调度规则，以改善系统性能。它使排队理论从“分析现象”走向“主动干预”。
9.2 动态调度
动态调度研究系统在运行过程中如何根据实时状态分配任务或调整优先级。它常见于服务器集群、生产线和交通信号控制。
9.3 重尾分布与长相关现象
当到达时间或服务时间呈现重尾分布时，极端值出现的概率会明显增大。长相关现象则表示系统波动在较长时间内仍保持相关性。
这类特征会显著改变队列尾部行为，使传统指数假设下的结论不再适用。
9.4 非平稳排队系统
非平稳排队系统的到达率或服务率会随时间变化，例如早晚高峰、节假日或突发事件。此类系统更接近真实业务环境，但分析难度更高。
9.5 大偏差理论
大偏差理论研究小概率但高影响事件的渐近规律，例如长时间拥塞或极端排队增长。它有助于评估罕见风险和设计安全裕度。
9.6 排队论中的数值方法
数值方法包括矩阵迭代、离散化、仿真和计算算法等，用于求解难以解析处理的模型。随着系统规模增大，数值计算的重要性不断上升。
10 历史与发展
排队理论的发展与电信、工业工程和运筹学的兴起密切相关。它从解决具体工程问题出发，逐渐形成了一套成熟的数学体系。
10.1 排队理论的起源
排队理论的起源通常与早期电话交换系统和服务容量设计问题相关。工程上需要回答“线路应该建多少、顾客会等多久”之类的实际问题，于是促成了系统化研究。
10.2 Erlang 的贡献
Erlang 对电话通信中的等待与阻塞问题进行了开创性研究，提出了若干重要公式。其工作奠定了现代排队理论和通信工程分析的基础。
10.3 20 世纪的发展
20 世纪中，排队理论与概率论、随机过程和运筹学进一步融合，形成了许多经典模型和分析方法。随着计算能力提升，研究范围也从单一队列扩展到复杂网络与优化控制。
10.4 现代排队理论研究方向
现代排队理论更关注大规模系统、复杂网络、数据驱动建模和实时决策问题。云计算、智能交通、医疗调度与高并发服务系统，都是当前研究的活跃领域。