阿壮博客
排队论 (queuing theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。
排队论已广泛应用于交通系统、港口泊位设计、机器维修、库存控制和其他服务系统。表 2 中列出排队论的应用。
中文名：排队论
外文名：queuing theory
又 称：随机服务系统理论
隶 属：运筹学
简介排队论日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。排队论的基本思想是 1909 年丹麦数学家、科学家，工程师 A. K. 埃尔朗在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。
自 20 世纪初以来，电话系统的设计一直在应用这个公式。30 年代苏联数学家 А. Я. 欣钦把处于统计平衡的电话呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他们用数学方法深入地分析了电话呼叫的本征特性，促进了排队论的研究。50 年代初，美国数学家关于生灭过程的研究、英国数学家 D. G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，L. 塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。70 年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。
定义排队论 (queuing theory)，或称随机服务系统理论， 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科，也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络、生产、运输、库存等各项资源共享的随机服务系统。 排队论研究的内容有 3 个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。
排队论起源于 20 世纪初的电话通话。1909—1920 年丹麦数学家、电气工程师埃尔朗（A. K. Erlang）用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则。20 世纪 30 年代中期，当费勒（W. Feller）引进了生灭过程时，排队论才被数学界承认为一门重要的学科。在第二次世界大战期间和第二次世界大战以后，排队论在运筹学这个新领域中变成了一个重要的内容。20 世纪 50 年代初，堪道尔（D. G. Kendall）对排队论作了系统的研究，他用嵌入马尔可夫链方法研究排队论，使排队论得到了进一步的发展。是他首先（1951 年）用 3 个字母组成的符号 X/Y/Z 表示一个排队系统。其中 X 表示顾客到达时间分布，Y 表示服务时间的分布，Z 表示服务机构中的服务台的个数。
1.排队模型的表示
X/Y/Z/A/B/C
X — 顾客相继到达的间隔时间的分布；
Y — 服务时间的分布（M — 指数分布、D — 确定时间、Ek — k 阶埃尔朗分布、G — 一般分布等）；
Z — 服务台个数；
A — 系统容量限制（默认为 ∞）；
B — 顾客源数目（默认为 ∞）；
C — 服务规则 （默认为先到先服务 FCFS）。
2.排队系统的衡量指标
服务队长 Ls — 正在接受服务的顾客数；
排队长 Lq — 在队列中等待的顾客数；
总队长 L = Ls + Lq — 系统中的顾客总数；
服务时间 Ws — 顾客在服务中消耗的时间；
等待时间 Wq — 顾客在队列中等待的时间；
总时间 W = Ws + Wq — 顾客在系统中的总逗留时间；
忙期 — 服务机构两次空闲的时间间隔；
服务强度 ρ；
稳态 — 系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。
3.排队系统的构成及应用前景
排队系统由输入过程与到达规则、排队规则、服务机构的结构、服务时间与服务规划组成。
一般还假设到达间隔时间序列与服务时间均为独立同分布随机变量序列，且这两个序列也相互独立。
评价一个排队系统的好坏要以顾客与服务机构两方面的利益为标准。就顾客来说总希望等待时间或逗留时间越短越好，从而希望服务台个数尽可能多些。但是就服务机构来说，增加服务台数，就意味着增加投资，增加多了会造成浪费，增加少了要引起顾客的抱怨甚至失去顾客，增加多少比较好呢？顾客与服务机构为了照顾自己的利益对排队系统中的 3 个指标：队长、等待时间、服务台的忙期（简称忙期）都很关心。因此这 3 个指标也就成了排队论的主要研究内容。
排队论的应用非常广泛。它适用于一切服务系统。尤其在通信系统、交通系统、计算机、存贮系统、生产管理系统等方面应用得最多。排队论的产生与发展来自实际的需要，实际的需要也必将影响它今后的发展方向。
组成部分排队系统又称服务系统。服务系统由服务机构和服务对象（顾客）构成。服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。图 1 为一最简单的排队系统模型。排队系统包括三个组成部分：输入过程、排队规则和服务机构。
输入过程输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间 t 内顾客到达数 n(t) 服从一定的随机分布。如服从泊松分布，则在时间 t 内到达 n 个顾客的概率为
或相继到达的顾客的间隔时间 T 服从负指数分布，即 P(T ≤ t) = 1 – e-λt，式中 λ 为单位时间顾客到达数的期望，称为平均到达率；1/λ 为平均间隔时间。在排队论中，讨论的输入过程主要是随机型的。
排队规则排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务（如医院接待急救病人）。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。
服务机构可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。而随机型服务时间 v 则服从一定的随机分布。如果服从负指数分布，则其分布函数是 P(v ≤ t) = 1 – e-μt，式中 μ 为平均服务率，1/μ 为平均服务时间。
问题求解研究排队系统问题的主要目的是研究其运行效率,考核服务质量,以便据此提出改进措施。通常评价排队系统优劣有 6 项数量指标：
①系统负荷水平 ρ ：它是衡量服务台在承担服务和满足需要方面能力的尺度；
②系统空闲概率 P0：系统处于没有顾客来到要求服务的概率；
③总队长：系统中排队等待服务和正在服务的顾客总数，其平均值记为 Ls；
④队长：系统中排队等待服务的顾客数，其平均值记为 Lg；
⑤逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其平均值记为 Ws；
⑥等待时间：一个顾客在系统中排队等待时间，其平均值记为 Wg。M/M/1 排队系统是一种最简单的排队系统。系统的各项指标可由下图中马尔可夫链的状态转移速度图推算出来（表 1）。其他类型的排队系统的各种指标计算公式则复杂得多，可专门列出计算公式图表备查。现已开始应用计算机仿真来求解排队系统问题。
应用排队论已广泛应用于交通系统、港口泊位设计、机器维修、库存控制和其他服务系统。表 2 中列出排队论的应用。
参考资料1.·
