数学建模之排队论

排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。

排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分： （i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。 （ii）优化问题，又分静态优和动态优，前者指优设计。后者指现有排队系统的优运营。 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。

下图是排队论的一般模型: 图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员 组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的 众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。 因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而 会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。

一般的排队过程都由输入过程、排队规则、服务过程三部分组成

输入过程是指顾客到来时间的规律性，可能有下列不同情况： （i）顾客的组成可能是有限的，也可能是无限的。 （ii）顾客到达的方式可能是一个—个的，也可能是成批的。 （iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响； 否则是相关的。 （iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等 数字特征都与时间无关，否则是非平稳的。

排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和 混合制三种. （i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。 （ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接 受完服务才离去。例如出故障的机器排队等待维修就是这种情况。 排队方式还分为单列、多列和循环队列。

（i）服务机构。主要有以下几种类型：单服务台；多服务台并联（每个服务台同 时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。 （ii）服务规则。按为顾客服务的次序采用以下几种规则： ①先到先服务，这是通常的情形。 ②后到先服务，如情报系统中，后到的情报信息往往有价值，因而常被优先处理。 ③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。 ④优先服务，如医疗系统对病情严重的病人给予优先治疗。

排队模型用六个符号表示，在符号之间用斜线隔开，即 X/Y/Z/A/B/C 。第一 个符号 X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号Y 表示服务时间的 分布；第三个符号Z 表示服务台数目；第四个符号 A是系统容量限制；第五个符号B 是 顾客源数目；第六个符号C 是服务规则，如先到先服务 FCFS，后到先服务 LCFS 等。并 约定，如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。我们只讨论先到先服务 FCFS 的情形，所以略去第六项。 表示顾客到达间隔时间和服务时间的分布的约定符号为： M —指数分布（M 是 Markov 的字头，因为指数分布具有无记忆性，即 Markov 性）； D—确定型（Deterministic）； Ek —k 阶爱尔朗(Erlang)分布； G —一般（general）服务时间的分布； GI —一般相互独立（General Independent）的时间间隔的分布。 例如，M/M/1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统。 D/M/c/表示确定的到达时间、服务时间为指数分布、c个平行服务台（但顾客是一队）的模型。

为了研究排队系统运行的效率，估计其服务质量，确定系统的优参数，评价系统 的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是： (i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望，记作Ls 。 (ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作 Lq 。 (iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望，记作Ws 。 (iv）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作Wq 。 (v）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机构再次空闲止的时间）长度的数学期望，记为 Tb

排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服 务时间不可能是负值，因此，它的分布是非负随机变量的分布。常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。

单服务台等待制模型M/M/1/∞是指：顾客的相继到达时间服从参数为λ的负指数分布，服务台个数为1，服务时间V服从参数为μ的负指数分布，系统空间无限，允许无限排队，这是一类简单的排队系统。

公式（7）和（8）给出了在平衡条件下系统中顾客数为n的概率。由式（7）不难看出，ρ 是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称 ρ 为服务强度，它反映了系统繁忙的程度。此外，（8）式只有在ρ=λ/μ