系统工程第九章排队论

系统工程第九章排队论9.1排队论概述9.1.1排队论发展简述9.1.2排队论的一些应用问题9.1.3排对论的一般模型作业9.1排队论概述9.1.1排队论发展简述最早有关排队论著作一般人共认的是1909年丹麦数学家爱尔朗（A.K.Erlang）所发表的论文，爱尔朗服务于丹麦哥本哈根电话公司，该论文研究的主题是电话交换机的使用状况，爱尔朗主要的著作成于1909至1920年间，有关他的生平与作品可参阅布鲁可迈尔（E.Brockmeyer）等人的文章。

爱尔朗之后从事排队论研究的先驱人物有法国数学家勃拉彻（F.Pollaczek）和前苏联数学家金勤（），他们在这方面的研究课题都在30年代完成并载于他们后来撰写的著作里。第二次世界大战之后，应用概率论，运筹学得到了广泛而深入的发展，排队论的论述已十分普及了。50年代初期英国人堪道（）又系统地阐述了排队问题，并且利用嵌入马尔柯夫链的方法推动了排队论的进一步发展。9.1排队论概述60年代，排队论研究的课题日趋复杂，因而开始了近似法的探讨与队列上下限问题的研究，在应用方面排队论进入了生产线、交通线。排队论在计算机、计算机网络、通信方面的应用主要开始于70年代。由于排队问题多呈网络出现，计算上的繁琐使得研究范围扩及到计算方法上面，同时有关模拟法的研究继50年代（计算机问世的年代）之后再度成为科研工作者注意的对象。排队论的发展、推广起自于实际应用的需要，同时由于近代计算工具的精密、快速以及排队问题本身趋于复杂的倾向决定了排队论研究的方向。9.1排队论概述9.1.2排队论的一些应用问题排队论应用的例子不胜枚举，下面我们列举七个方面略作说明。1.通信问题电话交换机通常仅有有限条电话线以沟通音讯，如果在某一时刻所有的电话线均被占用，那么新的使用要求就必须等到有一条线空下来时方能满足，这时电话线的使用要求是排队问题，电话线为服务台，而占用电话线的时间为服务时间，而一般使用电话线的排队规则为“先到先占”。在人造卫星通信方面排队论也常被用来解答实际问题。在这个系统内，通讯卫星为服务台，地面通信站使用卫星的要求可视为顾客的到达，服务时间视通信站发射信息的长短以及卫星转播信息的时间而定，排队规则可以先到先占或者是依次轮流使用。9.1排队论概述

2.公共服务问题许多公共服务事业对群众提供服务的水平，或者公共服务设施的使用情况也可纳入排队问题。例如银行的服务人员，邮局的服务员，医院的病床，饭店的座位等可当作服务台，服务时间以及到达顾客则与实际的情形完全一致，一般来说排队规则则均为先到先占。但是在某些情况下也可以有优先权的出现，例如病危的患者可以有优先占用病床的权利。

3.救护、公安系统警察、消防人员、消防车、医院救护车均可当作服务台，紧急事故的发生相当于顾客的到达，通常这类问题都要求极低的服务台使用率，因而当一件紧急事故发生后有足够的应付能力（至少有一个服务台可以立即使用）。9.1排队论概述

4．存量问题贮存系统中存量的变化的随机行为和排队论中的队列长度变化的随机行为有相似的地方。例如，零售商店货柜上的商品，图书馆的藏书，水库的存水量都可视作队长，卖出的商品、借出的书籍、防水灌溉或发电可视作顾客的离去，而进货、还书，又下雨或河水引入增加贮水量则为顾客到达。

5．交通问题港口的码头是服务台，船只为顾客。码头的使用决定了港口的吞吐量，船只过久等待进港造成罚款都是应当注意的问题。飞机跑道或者停机坪可以作为服务台，飞机起降为顾客的服务要求，如何安排飞机班次便利顾客并使飞机起降有条不紊，是机场调度的重要问题。9.1排队论概述

6．生产线问题在工厂生产线上，机器、工人甚至物料运输设备如何安排以保证生产率的水平，降低生产过程中原料和半成品的存量往往也可通过排队问题的研究获得解决。在这类问题里，产品为顾客，机器、工人或者有关生产、运输设备为服务台。

7．计算机问题在计算机内部中央处理器、输入输出设备可当作服务台，计算程序为顾客。在计算机网络问题里计算机本身可以当作服务台，计算机程序或指令通过网络可由一个计算机传送至另一计算机，这类问题通常都以网络队列形式出现。9.1排队论概述9.1.3排对论的一般模型作业排队论主要研究的问题是什么？9.1排队论概述9.2排队系统的组成及数量指标

9.2.1排队系统的组成和特征9.2.2排队问题的分类9.2.3排队问题的数量指标小结作业9.2排队系统的组成及数量指标

9.2.1排队系统的组成和特征一般的排队系统都有输入过程、排队规则、服务机构三个基本组成部分。

1．输入过程（InputProcess）输入过程是指顾客到达排队系统的方式和分布。为了完整地描述一个输入过程，必须考虑到顾客源（顾客的总体）、到达的方式和顾客相继到达的时间间隔诸因素。

顾客源可以是有限的和无限的。

顾客到达排队系统的方式可能是单个的。

顾客相继到达的时间间隔可以是确定的，也可以是随机的。9.2排队系统的组成及数量指标

2．排队规则（QueueDiscipline）顾客到达时，若所有服务机构正被占用，则顾客可以随即离去，也可以排队等候。随即离去的称损失值（或即时值）；排队等候的时间称等待值。

排队规则是指有关服务次序的安排的规定。对于等待制，一般有（1）先到先服务（First-come,first-servedFCFS）（2）后到先服务（Last-come,first-servedLCFS）（3）随机服务（RandomSelectionforServiceRS）（4）优先服务（PriorityDiscipline）9.2排队系统的组成及数量指标

3.服务机构（ServiceMechanism）（1）单队——单服务台系统顾名思义，这个系统仅有一个服务台。如图9-2，方块代表服务台而圆圈代表顾客，箭头表示顾客流动的方向。图中显示队列长度为4，有一个顾客占用服务台。9.2排队系统的组成及数量指标

9.2排队系统的组成及数量指标

9.2排队系统的组成及数量指标

9.2排队系统的组成及数量指标

9.2.2排队问题的分类9.2排队系统的组成及数量指标

9.2排队系统的组成及数量指标

9.2.3排队问题的数量指标表明排队系统特征和性态的基本数量指标是：9.2排队系统的组成及数量指标

小结排队问题的组成：一般的排队系统都有输入过程、排队规则、服务机构三个基本组成部分。

排队问题的主要特征：（1）相继顾客到达间隔时间的分布；（2）服务时间的分布；（3）服务台个数。

排队问题的数量指标：

1．队长；2．队列长；3．逗留时间；4．等待时间；5．服务机构的利用率（或空闲率）。作业对于等待制，排队规则一般有哪几种？按服务台的数目、队列的组合及服务时间的分布，排队问题可分为哪几种类型？9.2排队系统的组成及数量指标

9.3到达间隔的分布和服务时间的分布

9.3.1泊松流到达间隔的分布9.3.2服务时间v的分布9.3.3生灭过程小结作业9.3到达间隔的分布和服务时间的分布

9.3.1泊松流到达间隔的分布1．泊松流

9.3到达间隔的分布和服务时间的分布

1）在不相重叠的时间区间内顾客到达数是相互独立的，我们称之为无后效性。9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

2．负指数分布

9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3.2服务时间v的分布9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3.3生灭过程生灭过程描述系统消长生灭的随机过程，是排队论研究的重要数学工具。对于输入为泊松到达、服务为负指数分布的系统，其系统状态随时间变化的过程就称为一个生灭过程。9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

现在来讨论生灭过程的状态概率。9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

9.3到达间隔的分布和服务时间的分布

利用上述讨论所得结果式（9-14）、式（9-15），可以求解多种随机服务系统。9.3到达间隔的分布和服务时间的分布

小结泊松流生灭过程负指数分布9.3到达间隔的分布和服务时间的分布

生灭过程描述系统消长生灭的随机过程，是排队论研究的重要数学工具。生灭过程的微分方程组：9.3到达间隔的分布和服务时间的分布

生灭过程的差分方程组：9.3到达间隔的分布和服务时间的分布

作业什么是负指数分布？什么是爱尔朗分布？简述生灭过程的微分方程组和差分方程组。9.4排队系统的数学模型9.4.1单队——单服务台系统模型分析9.4.2多服务台系统模型分析9.4.3非负指数分布排队系统模型简介小结作业9.4排队系统的数学模型9.4.1单队——单服务台系统模型分析1.标准的单队——单服务台系统模型

M/M/1标准的M/M/1模型是指适合下列条件的排队系统此外，还假定到达间隔时间和服务时间是相互独立的。9.4排队系统的数学模型标准M/M/1的模型的分析步骤是9.4排队系统的数学模型9.4排队系统的数学模型从而得到状态概率9.4排队系统的数学模型下面，在已知系统状态概率的基础上，求其运行的基本数量指标：1)平均队长（系统中的平均顾客数）即9.4排队系统的数学模型2）平均队列长（队列中等待的平均顾客数）9.4排队系统的数学模型4）平均逗留时间5）服务机构的空闲率服务机构的利用率9.4排队系统的数学模型可将标准的M/M/1模型的主要运行指标归纳如下它们的相互关系为9.4排队系统的数学模型解

按式（9-17）、式（9-18）有（1）系统中平均队长（2）平均队列长9.4排队系统的数学模型（3）平均逗留时间（4）平均等候时间（5）服务机构利用率（6）顾客到达后立即接受服务的概率9.4排队系统的数学模型2.系统容量有限时的单队——单服务台系统模型M/M/1（N）9.4排队系统的数学模型从公式（9-14）得

（9-19）从式（9-15）得（9-20）9.4排队系统的数学模型该排队系统的数量指标为9.4排队系统的数学模型由于，故9.4排队系统的数学模型9.4排队系统的数学模型（2）平均队列长9.4排队系统的数学模型（3）平均等候时间（4）平均逗留时间9.4排队系统的数学模型9.4排队系统的数学模型解：

（1）某顾客一到达就能理发（相当于理发馆中没有顾客）的概率9.4排队系统的数学模型（2）需要等候的顾客的期望值（3）有效到达率9.4排队系统的数学模型（4）一顾客在理发馆内的平均逗留时间（期望值）（5）理发馆的损失率（即可能到来的顾客中不等待就离开的百分数）9.4排队系统的数学模型3.顾客源有限时的单队——单服务台系统模型M/M/1（M）

9.4排队系统的数学模型此时，可建立该问题的稳定状态方程如下9.4排队系统的数学模型由概率的性质故9.4排队系统的数学模型最后，给出顾客源有限的单队—单服务台系统的各项数量指标的计算公式9.4排队系统的数学模型9.4.2多服务台系统模型分析1.标准的M/M/c模型

模型运作的示意图如图9-3所示。

9.4排队系统的数学模型9.4排队系统的数学模型该系统的运行指标可计算如下（1）从式（9-14）可得9.4排队系统的数学模型（2）顾客到达后必须等待（即系统中至少有c个顾客）的概率为（9-24）9.4排队系统的数学模型从而（9-25）9.4排队系统的数学模型（9-26）9.4排队系统的数学模型（9-27）解：

按题中给定的条件9.4排队系统的数学模型（1）各卸货点都处于空闲概率为（2）汽车到达后必须等待的概率为9.4排队系统的数学模型图9-8三个单队——单服务台系统构成的排队系统9.4排队系统的数学模型这时系统的状态概率和运行指标分别为（9-28）9.4排队系统的数学模型（9-29）（9-30）9.4排队系统的数学模型这时的运行指标如下：（9-31）9.4排队系统的数学模型9.4排队系统的数学模型解：

（a）（b）顾客一到达就能立刻理发的概率为（c）（d）9.4排队系统的数学模型9.4排队系统的数学模型9.4排队系统的数学模型(1)其中（9-32）9.4排队系统的数学模型(2)平均顾客数（即平均故障台数）

在机器故障问题中，它是每单位时间M台机器平均出现故障的次数。9.4排队系统的数学模型(3)可以证明（9-33）9.4排队系统的数学模型9.4.3非负指数分布排队系统模型简介1.M/G/l排队模型

下面给出排队论中著名的Pollaczek-Khintchine（P-K）公式：9.4排队系统的数学模型（9-34）（9-35）9.4排队系统的数学模型具体有（9-36）9.4排队系统的数学模型

例9-7设某电话间的顾客按泊松流到达，平均每小时到达6人。通话时间T的平均值为8分钟，标准差为4分钟。管理人员想知道平均队长和顾客平均等待时间是多少？解：

因此从而9.4排队系统的数学模型2.M/Ek/1排队模型

代入公式（9-35）有（9-35）9.4排队系统的数学模型（9-37）9.4排队系统的数学模型解：

由题意知服务时间服从5阶爱尔朗分布。9.4排队系统的数学模型小结单队——单服务台系统模型（1）标准的单队——单服务台系统模型M/M/1；（2）系统容量有限时的单队——单服务台系统模型M/M/1（N）；（3）顾客源有限时的单队——单服务台系统模型

M/M/1（M）多服务台系统模型（1）标准的M/M/c模型；（2）系统容量有限的单队——多服务台系统模型M/M/c（N）；（3）顾客源有限时的单队——多服务台系统模型M/M/c（M）。非负指数分布排队系统模型

（1）M/G/l排队模型；（2）M/Ek/1排队模型。作业标准的M/M/1模型应符合哪些条件？它与M/M/1(N)模型、M/M/1（M）有何区别？标准的M/M/c模型的基本特征是什么？与M/M/c（N）和M/M/c（M）的区别？9-49-59.4排队系统的数学模型9.5经济分析——系统的最优化

9.5.1排队系统的最优化问题9.5.2多服务台模型中的最优服务台数9.5.3M/M/1模型中最优服务率μ

9.5.4M/M/c模型中最优的服务台数c

小结作业9.5经济分析——系统的最优化

9.5.1排队系统的最优化问题

排队系统的最优化问题分为两类：系统设计的最优化和系统控制最优化。前者称为静态问题，从排队论一诞生起就成为人们研究的内容，目的在于使设备达到最大效益，或者说，在一定的质量指标下要求机构最为经济。后者称为动态问题，是指一个给定的系统，如何运营可使某个目标函数得到最优，这是近十多年来排队论的研究重点之一。由于学习这后一问题还需更多的数学知识，所以本节只讨论静态最优的问题。9.5经济分析——系统的最优化

在一般情形下，提高服务水平（数量、质量）自然会降低顾客的等待费用（损失），但却常常增加了服务机构的成本，最优化的目标之一是使二者费用之和为最小，决定达到这个目标的最优的服务水平。另一个常用的目标函数是使纯收入或使利润（服务收入与服务成本之差）为最大（见图9-15）。各种费用在稳态情形下，都是按单位时间来考虑的。一般情形，服务费用（成本）是可以确切计算和估计的。至于顾客的等待费用就有许多不同情况，像机械故障问题中等待费用（由于机器待修而使生产遭受的损失）是可以确切估计的，但像病人就诊的等待费用（由于拖延治疗使病情恶化所受的损失），或由于队列过长而失掉潜在顾客所造成的营业损失，就只能根据统计的经验资料来估计。9.5经济分析——系统的最优化

常用的求解方法：对于离散变量常用边际分析法，对于连续变量常用经典的微分法，对于复杂问题读者们当然可以用非线性规划或动态规划的方法。9.5经济分析——系统的最优化

9.5.2多服务台模型中的最优服务台数

（9-38）9.5经济分析——系统的最优化

（9-39）9.5经济分析——系统的最优化

Note：9.5经济分析——系统的最优化

解：

这是求M/M/c排队模型最优服务台数的问题，其中9.5经济分析——系统的最优化

计算过程与结果如表9-6所示。9.5经济分析——系统的最优化

9.5.3M/M/1模型中最优服务率μ

9.5.3.1标准的M/M/1模型

由（9-18）式，有（9-41）9.5经济分析——系统的最优化

解得（9-42）9.5经济分析——系统的最优化

解：

（9-42）9.5经济分析——系统的最优化

（9-42）（9-38）9.5经济分析——系统的最优化

在这种情形下，系统中如已有N个顾客，则后来的顾客即被拒绝，于是被拒绝的概率（借用电话系统的术语，称为呼损率）；能接受服务的概率；单位时间实际进入服务机构顾客的平均数。9.5经济分析——系统的最优化

（9-43）9.5经济分析——系统的最优化

9.5.3.3顾客源为有限的情形

仍按机械故障问题来考虑。9.5经济分析——系统的最优化

而9.5经济分析——系统的最优化

9.5经济分析——系统的最优化

小结

多服务台模型中的最优服务台数的计算

M/M/1模型中最优服务率的计算作业9-109.5经济分析——系统的最优化

9.6排队论应用案例

案例1排队论在教务员岗位数量确定中的应用案例2排队论在露天矿开采中的应用案例3排队论在医院科室编制方面的应用9.6排队论应用案例

教务员的岗位职责主要是安排教学、日常教学管理、维持教学秩序和核对登记成绩等，其工作具有明显的周期性，每年的学期初和学期末都格外繁忙，尤其是期末，大量的理论教学和实践教学成绩在半个月或稍长的一段时间内陆续评定结束，教务员进入异常的繁忙期。某大学工程技术学院每一学期都有超过100人上课，期末时有近500份成绩上报。核对登记成绩是一项单调和乏味的工作。从人员设置的角度来考虑，教务员数量多，平时人员冗余过多，经济性不好；教务员数量少，忙期工作强度过大，易于出错，工作效率低，难以满足教学管理的要求，且此时教师也忙于整理教案和登记平时测验的成绩等，有余暇能担当教务员职责的人难以找到。根据教务员平时的工作状态以及教学运行中的实际情况，特以学期末的工作状态为考察对象，度量决定教务员的合理数量。案例1排队论在教务员岗位数量确定中的应用9.6排队论应用案例

根据统计观察，教师上交成绩单的时间会比教务部要求的时间滞后1-2周不等，个别教师可能延迟上交时间，但是，在相对比较紧凑的半个月内，教师相继到达的时间间隔服从负指数分布。教学科已有二名教务员，现考虑是否需要再增加教务员，增加几个合适?9.6排队论应用案例

将该问题可看作一个M/M/s/∞排队问题，其中首先，成绩单到达的间隔比服务时间短，不增加工作人员，即使教务员一刻也不停息地工作，成绩单也将会以2份/小时的速度增加，因此，必须增加教务员的数量。9.6排队论应用案例

现在考虑增加的人数，根据前面得到的多服务台排队系统模型的结果，将有关计算结果列入表9-7中。9.6排队论应用案例

因此，从提高工作效率、减少成绩单积压时间、为学生提供及时的服务，并适当降低教务员的工作强度来看，2个教务员是不够的，设置3名教务员较为合理。9.6排队论应用案例

案例2排队论在露天矿开采中的应用

9.6排队论应用案例

图9-19露天矿排队系统

9.6排队论应用案例

可以看出，电铲台数、卡车辆数与卸位个数之间需要有一个适当的匹配关系，否则就会在采掘场或卸场造成忙闲不均的现象，影响电铲、卡车或卸位的效率的充分发挥。现将装运过程看作一个排队系统，此系统共分四级：9.6排队论应用案例

还假定四级系统都是等待制的，先到先服务，各级服务时间都相互独立，对于2，4两级系统，由于服务台数目足够全体顾客同时服务，因而自然就不存在排队等待现象。9.6排队论应用案例

现在引进刻画系统特征的几个数量指标：9.6排队论应用案例

9.6排队论应用案例

以班为单位进行模拟，对每个顾客（卡车），考察它在各级排队系统中服务完毕的时刻，并用两个存储单元作记录。9.6排队论应用案例

单元D中放第1系统的服务台得空，可以开始下一服务的时刻。单元G中放第2系统的服务台得空，可以开始下一服务的时刻。单元H