数据、模型与决策（原书第16版）课件 第11章、排队模型

AnIntroductiontoManagementScience,16e第十一章、排队模型章节内容11-1 排队系统的结构11-2 到达服从泊松分布、服务时间服从指数分布的单服务台排队模型11-3 到达服从泊松分布、服务时间服从指数分布的多服务台排队模型11-4 排队模型中的一般关系11-5 排队的经济性分析11-6 肯德尔排队模型分类法11-7 到达服从泊松分布、服务时间为任意的单服务台排队模型11-8 到达服从泊松分布、服务时间任意且不排队的多服务台模型11-9 有限客源的排队模型

本章小结章节目标(1/2)完成本章后，你将能够:LO11.1 使用泊松分布描述到达时间，使用指数分布描述服务时间LO11.2 计算泊松到达和指数服务时间的单服务台排队的稳态运行参数LO11.3 计算泊松到达和指数服务时间的多服务台排队的稳态运行参数LO11.4 用里特导出方程来描述任何排队系统的运行参数之间的关系章节目标(2/2)LO11.5 使用排队的经济性分析做出排队系统决策LO11.6 计算泊松到达和一般服务时间的单服务台排队的稳态运行参数.LO11.7 计算泊松到达、一般服务时间和无等待的多服务台排队的稳态运行参数

LO11.8 计算有限客源的泊松到达和指数服务时间的单服务台排队的稳态运行参数介绍回想一下上一次你不得不排队的情形，比如在超市的收银台排队、在银行排队、在快餐店排队等。在类似上述需要排队的情况下，把时间用于等待是令人非常不愉快的。然而增加更多的收银员、银行出纳员或服务生并不总是改变服务水平的最经济的策略。因此，各行各业需要采取相应的措施，把排队时间控制在顾客所能容忍的限度内。人们已经设计建立了一些模型来帮助管理者理解等候线的运作，并帮助管理者做出更好的决策。用管理科学的术语来讲，等候线也称排队，与等候线相关的知识体系被称为排队论。排队模型包括一些数学公式以及可用于确定排队运行参数(系统指标)的关系式。相关运行参数如下：(1)系统中没有顾客的概率(2)排队的顾客平均数(3)系统中的顾客平均数(排队的顾客数加上接受服务的顾客数)(4)每位顾客排队花费的平均时间(5)每位顾客在系统中花费的平均时间(排队时间加上服务时间)(6)顾客到达以后不得不排队以接受服务的概率11-1排队系统的结构伯格·度姆快餐店我们以伯格·度姆快餐店的等候线为例。伯格·度姆快餐店出售火腿汉堡、奶酪汉堡、法式油炸食品、软饮料和奶昔，同时还有一些特色食品和甜点可供选择。虽然伯格·度姆快餐店希望能为每位顾客提供即时的服务，但是很多时候，到达的顾客远远多于快餐店的服务人员所能接待的人数。因此，顾客不得不排队等候点餐和取餐。伯格·度姆快餐店担心它目前所用的顾客服务方式导致了过长的排队时间。管理层希望通过对等候线进行研究，开发一个能够减少排队时间、提高服务质量的最佳方式。单服务台等候线在伯格·度姆快餐店目前所实行的运作方式中，一名服务生为一位顾客点餐，计算总费用，向顾客收取餐费，然后上菜。为第一位顾客上菜之后，这名服务生就可以为下一位排队的顾客服务。这种运作方式就是一个单服务台排队模型的例子。11-1到达间隔分布

11-1服务时间分布

11-1排队原则和稳态运行就伯格·度姆快餐店的排队（推广到一般来讲，可以是所有面向顾客的排队）来说，我们是以先到先服务的原则来安排等候服务的顾客的，这种方式被称作“FCFS排队原则”。然而，有些情况要求有不同的排队原则：在乘坐飞机时，最后登机的顾客往往会最先下飞机，因为有许多航空公司都是让座位在飞机后排的乘客先登机。医院急诊室不会采用前面所述的任何一种排队原则，而是赋予等候个体优先次序，然后为具有最高优先权的顾客最先提供服务。在本章中，我们只讨论采用先到先服务排队原则的排队。当伯格·度姆快餐店早上开始营业时，店里没有顾客，每位顾客从到达到最终被服务的时间存在明显差别，因而没有一定的排队原则。渐渐地，营业开始正常或呈稳定状态。我们将开始或起始阶段称为过渡（瞬时）阶段。当系统正常或稳态运行时，过渡（瞬时）阶段结束。排队模型描述了排队的稳态运行特征。11-2到达服从泊松分布、服务时间服从指数分布的单服务台排队模型

11-2伯格·度姆快餐店问题的运行参数

伯格·度姆快餐店的单列服务台排队的计算结果给出了一些关于排队运作的重要信息：11-2伯格·度姆快餐店问题的结果和改进管理者对排队模型的应用伯格·度姆快餐店的单列服务台排队的计算结果表明顾客在点餐前的平均等待时间为3分钟，这对以快速服务为宗旨的行业来说，多少有些长了点。此外，我们还注意到：等待中的顾客平均人数为2.25位。顾客不得不等待的概率为75%。有7个或更多顾客等待的概率为0.1335。这一数字表明，伯格·度姆快餐店的管理者应当考虑采取其他设计或计划来改善单服务台排队运作方式。改善排队运作伯格·度姆快餐店的管理者决定让顾客在排队的同时将自己的点餐单直接交给厨房，这样等到顾客缴费的时候就可以同时获得自己的餐点。按照这一设计，伯格·度姆快餐店的管理者预测：改变后的系统的平均服务率提高到1.25（位顾客/分钟）。顾客排队等候所花费的平均时间从3分钟下降到了1.2分钟。11-3到达服从泊松分布、服务时间服从指数分布的多服务台排队模型一个多服务台排队包括两个或两个以上服务台，假设这些服务台就服务能力而言是相同的。在多服务台服务系统中存在两种典型的情况：①顾客先是排在同一等候线里（也叫一个“集中”或“共享”队列），等到自己接受服务的时候，就转移到一个可以直接被服务的口那里去；②每个服务窗口有自己的队列，新来的顾客选择其中一个队列排队等候服务。在本章中，我们重点关注针对所有服务窗口的单个共享队列的系统设计。本节中，我们将介绍确定多服务台排队稳态运行参数的公式。这些公式的应用前提为下列条件成立：（1）到达服从泊松分布。（2）各个服务台的服务时间服从指数分布。（3）各个服务台的平均服务率μ相同。（4）到达者在单服务台中排队，然后移动到最先空闲下来的服务台接受服务。11-3运行参数

11-3伯格·度姆快餐店问题的运行参数

我们可以计算出系统中有n位顾客的概率：

11-3稳态运行参数现在，我们可以将双服务台系统的稳态运行参数与11.2节中所讨论过的原始的单服务台系统的运行参数进行对比：（1）一位顾客在系统中所花费的平均时间（等候时间加上接受服务时间）从W=4分钟减少到W=1.1636分钟。（2）排队顾客的平均数从Lq=2.25位减少到Lq=0.1227位。（3）一位顾客排队所花费的平均时间从Wq=3分钟减少到Wq=0.1636分钟。（4）某位刚到达的顾客必须等待的概率从Pw=0.75下降到Pw=0.2045。双服务台系统可以极大地改善排队运行参数。排队研究展示了三种排队结构的运行特征：原始的单服务台系统、直接向厨房提交订单的单服务台系统和由两个服务生处理订单构成的双服务台系统。考察了上述结果之后，伯格·度姆快餐店采用了下面的策略：在预计到达顾客为平均每小时45位的时间段内，伯格·度姆快餐店将安排2个点餐台，每个点餐台有1个服务生。11-4排队模型中的一般关系约翰·里特证明了下列4个参数之间存在几种关系，并且这些关系适用于各种不同的排队系统，无论到达是否服从泊松分布和服务时间是否服从指数概率分布。相关的运行参数如下：Lq=排队顾客的平均数L

=系统中顾客的平均数Wq=一位顾客排队所花费的平均时间W

=一位顾客在系统中所花费的平均时间

11-5排队的经济性分析经理可能会做出决定：将系统中的平均等待时间控制在1分钟或1分钟以内，并把等待服务的顾客的平均数控制在2位或2位以内。利用前几节中所讨论的排队模型，可以为实现该经理的目标确定服务台的数量。此外，经理可能还会希望计算出运行排队系统的成本，然后在每小时或每天的运行成本最小化的条件下，决定如何设计系统。在进行排队的经济性分析之前，必须首先建立一个总成本模型，包括等候成本和服务成本。

11-5伯格·度姆快餐店问题的经济性分析

我们可以看出，服务成本随着服务台数的增加而提高；然而，更多的服务台会带来更好的服务，即等候时间及等候成本是随着服务台数量的增加而减少的。因此，我们可以通过对几个设计方案进行评估求得最佳的服务台数量，使得其对应的总成本接近于最低。11-6肯德尔排队模型分类法D.G.肯德尔提出了一套符号，这套符号有助于对已有的许多不同的排队模型进行分类。肯德尔符号系统包含3个字母，具体形式如下：A/B/k其中：A=到达的概率分布B=服务时间的概率分布k=服务台数根据在A或B的位置上出现的不同字母，可以描述出许多排队系统。通常使用的标记字母如下：M=到达服从泊松分布或服务时间服从指数分布D=到达或服务时间是确定的或持续不变的G=到达或服务时间服从某种已知均值和标准差的一般概率分布例如，利用肯德尔符号法，我们可以将：到达服从泊松分布、服务时间服从指数分布的单服务台排队模型可以划为M/M/1模型。到达服从泊松分布、服务时间服从指数分布的双服务台排队模型可以划为M/M/2模型。11-7到达服从泊松分布、服务时间为任意的单服务台排队模型

11-7哈氏海货供应公司：M/G/1模型的示例

11-7定长服务时间

11-8到达服从泊松分布、服务时间任意且不排队的多服务台模型本节要讲的排队系统中，当系统满载时，到达的个体受阻，并会离开系统。本节中所讲到的这个特定模型是建立在下列假设基础上的：（1）系统中有k个服务台。（2）到达服从平均到达率为λ的泊松分布。（3）每个服务台的服务时间可能服从某种概率分布。（4）每个服务台的平均服务率μ是相同的。（5）当至少有一个服务台空闲时，到达者才会进入系统。如果某个顾客在所有服务台都繁忙时到达，则他会受到阻碍。在上述条件下的模型被称为“即时制”M/G/K模型，其中，G表示服务时间服从一般或者某种不确定的分布。这种模型主要应用在电话系统和其他通信系统的设计中。其中，到达者是打进的电话，服务台是可用的电话数或通信线路的数目。在这样一个系统中，所有电话拨打的是同一个号码。当所有的服务台都忙碌时，再打进来的电话将接收到一个繁忙信号，并且不能进入系统。在这种情况下，要解决的问题是:“应该使用多少服务台?”更重要的设计考虑因素包括确定服务台数量如何影响受阻顾客的百分比。11-8即时制M/G/k模型的运行参数

11-8微型资料软件公司：无等待的M/G/k模型微型资料软件公司利用一套电话订货系统来为其计算机软件产品进行相关服务。来电者可以通过拨打公司的800免费电话向公司订货。假设拨打该号码的来电以λ=12个电话/小时的平均频率到达。处理一个电话订货所需要的时间因订货要求不同而有很大不同。然而，预计微型资料软件公司的每个销售代表平均每小时处理6个电话，即μ=6个电话/小时。目前，该公司的800免费电话有3条内线，每条内线由一个销售代表来操作。打进的800免费电话会自动切换到一条空闲的内线。当3条内线都繁忙时，来电者就会听到一个表示系统繁忙的信号。过去，微型资料软件公司的管理者曾假设，听到忙音的来电者过些时候会再打过来。然而，最近对电话订货的一项研究表明，许多没有打通电话的来电者并不一定会在稍后的时间再打一次。这些未打进的电话说明公司会遭受到利润上的损失。因此公司的管理者提出要求，要对电话订货体系进行分析。公司管理者最想知道的是听到忙音并且受到阻碍无法进入系统的来电者的比率。如果管理者的目的是让此系统的能力达到能够处理90%的来电者，那么，公司应该有多少条电话线、多少名销售代表？11-8微型资料软件公司的解决方案

11-9有限客源的排队模型当对要求服务的顾客数量不加限制时，我们称该模型为无限客源模型。在这种假设下，不管有多少顾客排队，平均到达率λ均保持不变。大多数排队模型都假设有无限客源。然而在有些时候，需要假设服务的个体或顾客的最高人数是限定的。此时，系统的平均到达率是变化的，并且取决于排队顾客的数量，我们称这种模型为有限客源模型。为了说明有限客源造成的影响，我们需要对前面讲到的排队模型的运行参数的计算公式进行修改。本节中所讨论的有限客源模型基于以下假设：1.每位顾客的到达服从平均到达率为λ的泊松分布。2.服务时间服从平均服务率为μ的指数分布。3.有服务要求的顾客的人数是有限的。在前面所讲的排队模型中，λ是系统的平均到达率。在有限客源的情况下，系统的平均到达率因系统中顾客的数量不同而有所差别。对于每位顾客，我们假设服务完成后需要再服务的时间间隔平均为1/λ。11-9有限客源的M/M/1模型的运行参数

11-9可可美制造公司：机器维修问题在机器维修问题中，我们将一组机器看作有限客源的“顾客”，它们要求维修服务。当一台机器出现故障时，就会要求一次新的维修，在这里就是指出现了新的到达者。如果第一台机器的维修尚未完成，又有一台机器出现故障，那么从第二台机器开始形成一条排队接受维修服务的“等候线”。如果更多机器出现故障，排队的长度会加长。先到先服务的假设说明，这组机器按照它们出现故障的先后顺序接受维修。M/M/1表明只有一人或一个服务台可以提供维修服务。也就是说，为了使机器恢复正常运转，必须以单服务台的运作方式来维修出现故障的每台机器。可可美制造公司有一组6台相同的机器。每台机器在维修后到再次遇到故障之前，平均运转20个小时。因此，每台机器的平均到达率（或称每台机器的维修服务要求次数）是λ=1/20=0.05/小时。在机器随时会发生故障的情况下，我们可以