系统工程-第九章 排队论

第九章排队论9.1排队论概述9.2排队系统的组成及数量指标9.3到达间隔的分布和效劳时间的分布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中放已经模拟过的班数。于是可以画出模拟框图，如图9-20所示。9.6排队论应用案例

图9-20模拟流程图