关于排队论介绍

[拼音]：paiduilun

[外文]：queueing theory

研究服务系统中排队现象的随机规律的一门学科。各种服务系统中，有各式各样的排队现象，如售票厅中买票人的排队，是一种有形的排队；向电话局问询台问询的用户的排队，是一种无形的排队。凡是服务系统为之服务的对象，皆称为顾客。排队论中的顾客可以是人、是物、是事、是信息。由各种行业可组成各种服务系统，其性质和形式可以大不相同，但是，任何一种服务系统都包含以下三个基本组成部分：

（1）输入过程，即顾客到来的规律。

（2）排队规则，即为顾客服务的次序。

（3）服务机构，即为顾客服务的各种设施（服务员、服务台、窗口等等）及服务的时间。

由于服务系统中顾客的到达以及服务时间和次序，都含有随机因素，因此，排队论又称为随机服务系统理论。排队论所要研究的课题，是如何合理地设计与控制服务系统，使之以最经济的服务机构满足顾客的需要。

刻画服务系统的性能优劣的主要数量指标有三个：

（1）等待时间，即从顾客到达时起，到开始接受服务时止的这段时间。这是顾客所关心的。

（2）忙期，即服务机构连续繁忙的时期。这是服务机构所关心的。

（3）队长，即服务系统中的顾客数目。这是顾客与服务机构都关心的，而且因其涉及等待空间的大小，所以对于设计人员至为重要。

此外，有时也用到其他一些数量指标。

模型

关于输入过程、排队规则和服务机构的模型，将最常见的叙述如下。

（1）定长输入，即顾客等间隔到达，如产品经传送带输入包装箱。

（2）最简单流输入或称泊松输入，即顾客相继到达的间隔时间相互独立，且具有相同的负指数分布，其分布函数（见概率分布）为

此处 λ为一正的常数。如电话呼唤流的到来。对于最简单流，可以证明，在t时间内到达k个顾客的概率vk(t)遵从泊松分布。 ③埃尔朗输入Ek，即顾客相继到达的间隔时间相互独立，并具有相同的埃尔朗分布密度，其中k为正整数，λ>0为一常数。

（4）一般独立输入，即顾客相继到达的间隔时间相互独立，并具有相同的一般分布。前三种输入是此种输入的特例。

（5）成批到达的输入，即有一系列的到达点（时间），它们的间隔分布可以是上述的各种分布，但是，在每一到达点上来到的顾客不是单独一个，而是一批，每批顾客的数目n为一随机变量，其分布为P{n=k}=αk(k=0，1，2，…)。

主要有三种。

（1）损失制，即顾客到达时，若所有服务台均被占，该顾客就自动消失。如通常使用的损失制电话系统。

（2）等待制，即顾客到达时，若所有服务台均被占，顾客就排队等待服务，且可以采用下列各种规则：a.先到先服务，即按顾客到达的先后次序给以服务。这是最通常使用的方法。b.后到先服务，即当服务机构得空时，总是挑选最后到达的顾客给予服务。如在通讯系统中，最后到达的信息一般说来是最有价值的，因而往往采取这种服务方式。c.随机服务，即当服务机构得空时，在等待的顾客中随机选取一名顾客给予服务，每一个顾客被选到的概率是相同的。d.优先权服务，如码头上对载有重要物资的船只先进行装卸；在电话局对长途电话比市内电话优先服务。e.多个服务台的情形，可在顾客到达时排成一个公共的队，按上述各种规则给予服务，或者在每个服务台前排成一队，第m 个顾客到达时以概率pmi排入第 i个队接受服务，此处m =1，2，…，n表示服务台个数。

（3）混合制，在队长有限制的情形，若限制队长为N，则在顾客到达时的队长小于N 时，顾客就排入队伍；当其等于N 时，顾客就离去。在等待时间有限制的情形，若规定等待时间为T，则顾客在队伍中等待的时间不大于T，顾客可得到服务；当其大于T 时，顾客就离去。在顾客的逗留时间(即顾客的等待时间与服务时间之和)有限制的情形，若规定逗留时间为T，则顾客逗留时间超过T 时即离去。

在服务设施方面，服务台的个数可以是一个或几个；在其组织形式上，可以是并联的或串联的或循环的；在服务方式上，可以是单个服务的或成批服务的；在服务时间上，可以是定长分布、负指数分布、埃尔朗分布、一般分布等各种类型的分布。对于多个服务台的情形，各个服务台的服务分布可以是参数不同或类型不同。

D.G.肯德尔在1951年引入了一个常用的关于随机服务系统分类的记号X/Y/n，其中X代表输入，Y 代表服务，n代表服务台的数目。在排队论中，通常用M代表泊松输入或负指数服务分布，用D代表定长分布，用Ek代表埃尔朗分布，用GI代表一般独立输入，用G代表一般服务分布。最常见的服务系统模型有M/M/1、M/M/n、M/G/1、M/G/n、GI/M/1、GI/M/n、GI/G/1和GI/G/n等，其中如M/G/1表示具有泊松输入、一般服务分布、单个服务台的系统，而M/M/n表示泊松输入。负指数服务分布、n个服务台的系统。如果不附加说明，这种记号一般都指先来先服务、单个服务、服务台并联的等待制系统。

平稳性态的研究

如果在有限时刻去考察一个系统，该系统的数量指标的变化规律一般会依赖于初始条件及已经运行的时间，那么系统在此时的状况称为瞬时性态。如果系统已运行了相当长的时间，每项数量指标在任何时刻的变化规律是相同的，而且不再受初始条件的影响，那么就称该系统在此时已处于统计平衡，其状况就称为平稳性态。

1909年，A.K.埃尔朗关于电话系统排队问题的研究开始后的四五十年间，绝大多数的文献都属于平稳性态的研究。平稳性态的研究是排队论研究的发端。早期研究中最著名的结果是损失制的M/M/n系统的埃尔朗公式，即顾客到达系统后，由于n个服务台被占用而遭到损失的概率（称为损失率）是

式中λ为最简单流的参数，即单位时间内到达的顾客的平均数；μ 为负指数服务时间分布的参数，即单位时间内每个服务台服务完的顾客的平均数。

这个公式对于系统的性能分析及设计都有重要作用。例如在电话系统中，由统计检验已经证实，呼唤流的到来正好是最简单流，而会话时间也服从负指数分布，因此只要统计出单位时间内到来的呼唤平均数 λ及会话的平均长度1/μ，根据电话局线路的数目n，就能由此公式确定呼损率的大小。反之，如果先规定呼损率的指标，比如要求小于5‰，即平均1000次通话中最多有5次打不通，那么由公式即可求出需要的最少线路数目。

埃尔朗公式还被推广到M/G/n系统，自1957年起，陆续给出了严格的证明。

另一著名的公式是辛钦-波拉采克公式， 它主要包括两个公式：其一为M/G/1系统中顾客的平均数Q＝ρ＋，式中λ是单位时间内到达的顾客的平均数，ρ=λ/μ 称为服务强度，1/μ 是每个顾客的平均服务时间，而σ2为服务时间的方差。可以看出，在平均服务时间不能缩减的情况下，缩减服务时间的方差也能使系统中顾客的平均数下降。其二为M/G/1系统中等待时间分布的拉普拉斯变换，式中λ、ρ如同上述，B*(s)是服务时间分布的拉普拉斯变换，它完全确定等待时间的分布。

为了研究系统在什么样条件下才能最终达到统计平衡的问题，肯德尔在1951年首先对M/G/1系统引进了嵌入马尔可夫链的概念，并证明了系统中队长达到统计平衡的充分必要条件是，服务强度ρ <1。它的直观意义是明显的，即只有在单位时间内到达的顾客的平均数小于被服务完的顾客的平均数时，队长才能避免无限增长而达到平衡。在1953年，他又对GI/M/n系统得到了类似的结论。关于等待时间，则在1952年就有文献对GI/G/1系统证明了：服务强度ρ<1也是等待时间达到统计平衡的充分必要条件。关于统计平衡的其他研究工作，也不断出现。

瞬时性态的研究

从20世纪50年代中期开始，引起了人们的注意，并逐渐成为排队论研究的焦点。最早的瞬时性态研究是求解描述最简单的M/M/1系统的生灭过程的微分方程组，利用了母函数法、随机游动法或谱论。

当输入间隔与服务分布并非都是负指数分布时，则情况更为复杂。为了将非马尔可夫过程化为马尔可夫过程，以便于处理，于是引入了嵌入马尔可夫链和提出了补充变量法。又由于考虑了所谓的再生点，而使更新过程（见点过程）的技巧在排队论中也得到广泛的应用。此外，利用有关变量概率关系的分析并结合拉普拉斯变换的方法，已成为排队论的有力工具。

对于更一般的系统GI/G/1的瞬时性态研究，由于组合分析法的运用而有了很大的进展。

对于经典的系统M/M/1、 M/M/n、 M/G/1、GI/M/1、GI/G/1和GI/M/n的瞬时性态研究，在一些主要问题上，已经得到解决，中国数学工作者作出了贡献。但是在M/G/n和GI/G/n系统的瞬时性态研究方面，只获得了某些定性的结果，尚未求得明显解。

逼近理论

由于一些系统瞬时性态问题的解，包含着极为复杂的拉普拉斯变换的反演与母函数的展开，实际计算起来相当困难，而另一些系统如 M/G/n与GI/G/n的平稳性态与瞬时性态问题的明显解均未求得，因此有必要去研究各种便于实际计算的近似解法。

由考虑能否找出某些量的上界、下界来给出系统的初步信息，导致许多有关平均队长或平均等待时间的上界、下界的研究。由考虑能否用简单的系统来逼近复杂系统，导致研究诸如用埃尔朗输入或服务的系统来逼近一般系统、用分析上易于处理的扩散过程来逼近各种排队过程。由考虑逼近的有效性，导致关于所谓连续性即逼近序列的变化而引起极限系统的变化大小的讨论。

此外，有很多文献讨论饱和服务（服务强度小于1而已充分接近于1的情形）的逼近问题。 因为它涉及系统的合理设计问题，所以在应用上值得注意。

对于尚未解决的M/G/n系统，除了利用扩散逼近求解外，还有采用补充变量法与拉普拉斯法，列出方程组后，直接进行近似求解，或在作出马尔可夫性的近似假定后，再来计算求解。

研究复杂系统的性态时，计算机模拟的方法有很大的实用价值。

最优化

随机服务系统的最优化问题虽然起源很早，但是到20世纪60年代才受到普遍重视。它包括设计最优化与控制最优化两个方面。

设计最优化与性态研究的关系较为密切，一般来说，只要对性态研究得到了明显表达式，设计最优化也就随之解决。

控制最优化问题，在研究中有时需要采用新的概念与技巧。首先，作为最优化的标准，应考虑一个目标函数，例如总费用最小或总效益最大；其次，必须对系统运行的概率规律有确切的了解，才能实际控制。另外，作为决策人进行控制的手段，要有一组可供选择的策略，于是，有可能形成一个马尔可夫决策过程的模型。马尔可夫决策过程在控制最优化问题的研究中，有重要作用。

输入过程、排队规则以及服务设施都有最优化控制问题。输入过程的最优控制可以通过拒绝顾客的到达来进行，可以用调整平均到达速度来进行，也可以让顾客本身发挥作用如利用价格政策的影响来进行。排队规则的最优控制可以通过优先权的指定或顾客在各服务台之间的分配来进行。服务设备的最优控制可以通过增减服务速度或服务台的数目来进行。

还有一些与排队论有密切关系的随机分支。

存储论也称水库论，起源于水库蓄水问题。上游的水不断流入水库，水库又按一定规则放水，以使水库存储的水量保持在安全理想的状态，并能满足防洪、发电、航运、灌溉等等多种需要。在各种输入、输出情况下研究库容变化规律，是存储论的主要研究内容。存储论中的库容问题与排队论中的等待时间问题，在某种离散的特殊情形下，是两个完全等价的问题，但是，由于水库进水是连续的，而放水可以是离散的，也可以是连续的，因而一般不能用排队论的方法直接处理水库问题。水库问题与排队问题既相似又不同，它有自身的理论体系，其发展与排队论又互为影响。

计算机设计的数学理论，是20世纪60年代中期排队论开始应用于计算机的性能分析而产生的。计算机系统本身就是一个大型的、复杂的、网络式的随机服务系统，因之可用排队论的方法来研究计算机的设计和性能分析。在实时处理、分时系统、多道程序、计算机网络和存储器分配中，都有排队论的应用。排队论是计算机设计的数学理论基础之一。

其他有关的分支是计算机模拟、可靠性数学理论及库存论。

参考书目

1. 徐光煇著:《随机服务系统》，科学出版社，北京，1980.
2. J.W.Cohen，The Single Server Queue，Rev.ed.，North Holland，Amsterdam，1982.
3. D.R.Cox & W.L.Smith，Queues，Methuen，London，1961.