排队论及应用举例课件

第六章排队论关键词排队（Queue）指数分布（ExponentialDistribution）单通道、单阶段（SingleChannel,singlePhase）排队系统（QueuingSystem）泊松分布（PoissonDistribution）多通道、多阶段（Multichannel,Multiphase）到达率（ArrivalRate）服务率（ServiceRate）有限队列（FiniteQueue）第六章排队论关键词1一、排队问题的经济含义在日常经济生活中，经常遇到排队现象，如：在超市等待结帐、工厂中等待加工的工件或待修理的机器、开车上班等，排队论是运作管理中重要的方法，它是计划、工作设计、存货控制以及其他问题的基础。每一个排队事例的核心问题就是对不同因素作权衡决策，管理者必须衡量为提供更快捷服务而增加的成本和等待费用之间的关系。一种情况是：直接对成本进行权衡决策，例如考虑到顾客排队等待可以增加设备，就要权衡增加设备的成本与多服务顾客所带来的价值的大小，决策比较直观和容易；另一种情况是：排队问题是对医院床位的需求，可以估算增加床位带来的房屋建筑、附加设备以及增加的维护费用等成本，但衡量标准时什么？因为用金钱成本来度量病人对病床的需求显然是徒劳的，尽管可以估计出医院因病床不足会损失多少收入，但无法估计病人因得不到适当的医护所遭受的损失。解决排队问题的基本目标是平衡等待成本与增加资源引起的成本之间的关系。对于一个服务系统来说，这意味着若要给顾客创造很短的等待时间，服务台的利用率将回降低。排队问题中一个关键问题是用什么样的程序或优先规则来选择下一个产品或顾客作为服务对象。一、排队问题的经济含义在日常经济生活中，经常遇到排队现象，如2成本效益平衡服务成本总成本最小值等待成本最佳能力成本＄服务设施能力图6-1服务成本与等待成本的关系

如图6-1所示，是一个典型（稳定）的客运问题中的权衡。等待成本随着服务能力的增大而减小，可以用负指数曲线描述；服务成本可以简单地用线性变化表示；总成本或复合成本则是U型曲线。所以，理想的最优化（最小）成本位于服务成本曲线和等待成本曲线的交点上。排队问题的实际应用顾客到达服务需求量到达的数目时间服务时间普通能力时间图6-2到达与服务的关系

如图6-2表示的是到达某一服务机构（银行）的人数和对这一机构服务的需求（信贷人员）。在服务系统营业过程中，每一小时到达系统的顾客人数是一个很重要的变量。从提供服务的观点来看，顾客对于服务的需求是不断变化的，而且经常超过正常的服务能力。可以通过不同的方法对到达人数加以控制。如特殊顾客通道、临时加班、设定等待座位数等。一般服务时间受到服务速度、机器运转速度的影响，另外，服务时间也会因使用的工具、材料或计划的不同而变化。成本效益平衡服务成本总成本最小值等待成本最佳能力成本＄服务设3二、排队系统服务系统服务机构等待队列离开顾客源图6-3排队系统的组成如图5-3所示，一个排队系统有三个主要部分组成：一是：顾客源和顾客到达系统的方式二是：服务系统三是：顾客离开系统的方式(是否回到顾客源？)顾客到达到达服务系统的顾客可以分为两类：有限总体和无限总体。1.有限总体。要求服务的顾客数是有限的，通常是排成一队的。顾客总体中的某一位离开其位置（如一台设备停机待修理），顾客就少一个，同时减少了下一次要求服务的概率。相反，当被服务的顾客回到顾客总体中，总体人数对服务需求的概率也就增加了。2.无限总体。对于服务系统来说顾客数量足够大，由于人数增减而引起的总体规模的变化不会对系统的概率分布产生显著的影响。3.顾客到达的分布。这是一个到达率或单位时间到达数的问题。固定到达的分布呈周期性的，即相继到达的两个顾客之间的时间间隔几乎相同。在生产系统中，通常运用一些技术控制顾客在固定的时间间隔内到达。多数情况下，顾客的到达呈随机分布。

首先，分析相邻两个顾客到达的时间间隔是否服从某些统计分布？通常假定相邻两次到达的时间间隔服从指数分布其次，在设定时间长度为T，然后确定在时间T段内有多少顾客到达并进入系统？通常假定单位时间到达的人数服从泊松分布。二、排队系统服务系统服务机构等待队列离开顾客源图6-344.第一种情况：指数分布。当顾客已完全随机方式到达服务机构时，相邻到达时间间隔服从指数分布。如图5-4所示。其概率密度函数为：（6-1）式中代表单位时间段到达的顾客数量。图5-4中曲线下方的阴影区域即为函数5-1在正数范围内的积分，即。通过这种方法，就可以计算出某一特定时间顾客到达的概率。例如：在顾客是单个到达服务系统（）时，可通过两种方法得到表5-1。一种是根据式，另一种可以应用负指数分布。表的第二栏是下一个到达的顾客时间间隔超过分钟的概率；第三栏为下一个顾客到达时间小于分钟的概率。图6-4指数分布（1）（2）（3）下一个顾客将在下一个顾客将在小于t分钟大于t分钟内分钟内到达的概率到达的概率(3)=(1)-(2)01.0000.50.610.391.00.370.631.50.220.782.00.140.86期望值方差4.第一种情况：指数分布。当顾客已完全随机方式到达服务5

5.第二种情况:泊松分布。主要针对某一时段T内有n人到达的概率，到达过程是随机的，则服从泊宋分布。如图5-5所示。计算公式为：（6-2）式5-2表示在T时间内有n个顾客到达的概率。例如，如果一个系统的平均到达率是每分钟有3个顾客到达（），要求1分钟内有5个人到达的概率为：.149.168.224.102.050.224.20.10.05期望值方差平滑曲线12345681012时间T内有n人到达的概率到达人数n图6-5泊松分布（）0这就是说，在任何一分钟的间隔期内有5人到达的概率是10.1%。泊松分布是一类离散型的分布，但通常用一条平滑曲线来表示（n越大，曲线越平滑）。在这个实例中，n指的是到达系统的人熟，因而该分布是离散的，且必须为整数。5.第二种情况:泊松分布。主要针对某一时段T内有n人到6排队系统队列考虑的因素：队长、队列数、排队规则队长无限队列：即指相对于服务系统来说是相当长的队列。如：堵塞在立交桥上的车辆、绕这街道排列成队购买商品的顾客等。有限队列：是指由于法律或实际空间特点制约，排队等待服务的队长受到限制。如：停车厂、加油站等，但是有可能出现到达后离开，过一会有可能再来或到其他地方寻求服务。这是有限总体条件下的两种不同表现。队列数单列队是指只有一个队列。多列队指排在两个或两个以上服务台前的多个单列队，或者指在中间某点汇集的多个单列队。多列队的缺点是如果前面的几个服务时间短或者那些在其他队的顾客需要短服务时间时，到达的顾客将会挪动队列。排队规划是指决定队列中顾客接受服务次序的一个或一系列优先法则。直接影响着队列中顾客人数、平均等待时间、等待时间变化范围以及服务设施的效率等。在使用任何优先法则时，两大现实问题：一是确保顾客了解并遵守法则；二是保证有一个能使雇员对队列进行管理的系统。排队规则先来先服务最短过程时间预订优先紧急优先最优顾客优先其他最大需求优先最大盈利优先服务时间分布在排队问题中，服务率通常是指单位时间内服务台完成服务的顾客数，而不是指每位顾客的服务时间。固定服务时间是指每次服务的时间完全相同，这仅限于机器受控运作。当服务时间比较随机时，则近似指数分布，一般用作为每时间段内被服务的平均顾客数。排队系统在使用任何优先法则时，两大现实问题：排队规则先来先服7队列结构——见图5-6所示单通道、单阶段：最简单的队列结构形式。用简单的公式可以解决到达人数和服务时间的标准分布问题。如单人理发店。单通道、多阶段：由一系列以非常标准的顺序进行的服务构成。如：洗车服务的吸尘、打湿、冲洗、晾干、洗车窗和停车。重要的因素是该服务由多少个步骤组成，在各个不同步骤中又分别形成了队列。多通道、单阶段：如：银行的出纳窗口、大型商场的收银台等。每个顾客不均匀的服务时间会引起队列流动不均匀，导致某些顾客先于早到的顾客接受服务，一定程度上影响顾客挪动队列。为了保证顾客按到达时间顺序接受服务，则要排成一个单队，当一个服务台空出来时，队列最前面的顾客就可以去接受服务，如银行自动抽号排队。最大的问题在于需要对队列进行刻板的控制以维持秩序和引导顾客到空闲的服务台。多通道、多阶段：服务由多个步骤组成，完成每个服务步骤有两个或多个服务台，一般可有多个顾客同时被服务。如：医院里接待病人的系统：挂号（有多个窗口，病历上填写病人信息）、就诊（同一科室有多位大夫）、化验、检查（同一化验、检查有多个窗口和设施）、回复就诊（同一科室有多位大夫）、处方划价（多个窗口）、缴费（多个窗口）、取药（多个窗口）。混合型：两种情况：1）多通道—单通道结构；2）交错通道结构。考虑到阶段问题，如：单阶段服务的多通道变成了单通道（如过桥时多队变成一队）；多阶段服务的多通道变成了单通道（如多条子装配线汇成一条主装配线）上述形式的选择，一方面依赖于被服务顾客数；另一方面，依赖于服务顺序的特殊要求。队列结构——见图5-6所示上述形式的选择，一方面依赖于被服8队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交错通道图5-6队列结构队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交错通道图6-6队列结构队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶9顾客离开“经常发生事件（recurring-common-coldcase）”：顾客回到顾客源，马上成为一名新的顾客要求服务。如：机器例行修理后重新使用，可能再次出现故障而需要修理。“只发生一次事件（appendectomy-onlyoncecase）”：顾客重新要求服务的可能性极小，即不可能重新要求服务。如：机器进行彻底检查和修理后，在一段时间内不会重新维修。顾客接受服务后，离开的情况可能有两种顾客源有限时，对回头客服务的任何改变都会改变顾客到达率，引起排队问题的特征的改变。三、排队模型问题一：顾客等待。

银行希望知道有多少顾客在等待其服务到车（drive-in）出纳员的服务？出纳员的效率是多少？如果要求在95%的时间内，任一时刻系统中不超过三辆车，则其服务率应达到什么水平？问题二：设备选择。

公司有三中不同的设备可以提供同一种服务，设备功率越大，成本也越高，但服务速度越快。因此作决策时，成本与收入是紧密相联的。问题三：服务人数决策。

经销公司的一个销售部门必须决定一个柜台雇佣多少职员。职员越多，成本也越高，但服务等待时间的减少能带来部分成本的节约。问题四：有限总体。

前述都是无限总体，而对于有限顾客总体，如：车间有若干台设备，一名维修工负责4台设备的运转，在充分考虑设备闲置成本和维修工的服务成本的基础上，决定应该雇佣多少名维修工？四种典型的问题顾客离开“经常发生事件（recurring-common-c10模型分布服务阶段顾客源到达人数分布排队规则服务时间分布允许的队列长度典型例子1单通道单一无限泊松先来先服务指数无限银行出纳员服务系统；单道收费桥系统2单通道单一无限泊松先来先服务常数无限自动洗车服务；游乐园的滑行铁道系统3多通道单一无限泊松先来先服务指数无限汽车经销公司零件柜台服务系统4单通道单一有限泊松先来先服务指数无限工厂里故障机器的维修服务表6-1特殊队列模型特征在研究上述问题时，给出四种排队模型及其求解公式。但一个基本假设是：所研究的过程是持续稳定的。如果在一个问题中，其服务率或者到达率随时间而改变的话，运用公式得出的结果将不很精确。模型分布服务顾客源到达人排队规则服务时允许的典型例子1单通道11

四种队列问题的求解公式：模型1：（6-3）模型2：（6-4）模型3：给出P与M值，查表可得（6-5）是有限排队问题，可以通过有限表来解决。模型4：（6-6）HLn+=四种队列问题的求解公式：模型1：（6-3）模型2：（6-412公式6-3、4、5、6中符号注释无限排队模型（1-3）有限排队模型4公式6-3、4、5、6中符号注释无限排队模型（1-3）13四、应用举例

例1：顾客等待西部开发银行正在考虑开设一个服务到车的窗口。管理者估计顾客将以每小时15人的速度到达，出纳员的服务速率是每3分钟服务一位顾客。第一部分假设到达人数服从泊松分布，服务时间服从指数分布，求：1）出纳员的利用率；2）平均等待顾客数；3）系统中平均顾客数；4）平均等待时间；5）顾客在系统中的平均逗留时间，包括服务时间。解：四、应用举例例1：顾客等待西部开发银行14

第二部分由于空间的限制及对服务水平的要求，假如银行经理希望能保证以95%的置信度，在任一时刻系统中的车辆数不超过3辆。那么，在3辆车限制下，服务水平应为多高？出纳员的利用率应达到什么水平？为保证95%的服务水平，出纳员的服务率应为多少？解：3辆车或更少时的服务水平是指系统中车辆数分别为0、1、2或3时的概率。根据模型1和式（6-3），可得：0.685或68.5%系统中车辆数大于3的概率为：1.0-0.685=0.315要求系统中不多于3辆车的服务水平为95%，即应该使我们可以用试算法来解这个方程0.685或68.5%系统中车辆数大于3的概率为：1.0-0.685=0.315要求系统中不多于3辆车的服务水平为95%，即应该使第二部分由于空间的限制及对服务水平的15这就是说，出纳员必须以95%的置信度每小时为32人服务，这样才能使系统中的车辆数不超过3辆。也许通过调整服务方式，增加另一个出纳员或者限制营业种类，服务速率可以大大提高。另外，在95%的置信度下保证系统中不多于3辆车时，出纳员将有53%的闲暇时间。

例2：设备选择在美国有一个机器人公司被特许将加油业务和汽车冲洗业务合并在一起。机器人公司对加满油的车辆提供免费冲洗，对于不加油只冲洗的车收取0.5美元。以往的经验表明：加油并洗车的顾客数与单独洗车的顾客数大致相等。平均家一次油可以盈利0.7美元，洗一次车的成本是0.1美元，机器人每天运转14小时。机器人有三档功率和驱动系统，该特许专营店必须先对着三档功率作出选择。A档可以每5分钟洗一辆车，每天成本为12美元；B档可以每4分钟洗一辆车，每天成本为16美元；C档可以每3分钟洗一辆车，每天成本为22美元。该专营店估计，每个顾客洗一辆车不愿等待时间超过5分钟，若等待时间过长，公司将会失去顾客。若估计每小时有10名顾客来洗车，那么该选择哪档功率？这就是说，出纳员必须以95%的置信度每小时为16解：选择功率A时，根据模型2的公式可以计算出顾客的平均等待时间。

如果等待时间是唯一标准，则应该选择功率B，但是在做最终决策结论之前，还必须比较两者的利润。对于功率A，由于等待时间为12.5分钟，部分顾客会放弃接受服务。可以估计出选择功率A时营业额的减少量。可通过增加t1=5分钟或1/12小时（平均顾客等待时间），从中解得到达率，这将是最有效的顾客到达率。

因此，既然λ的最初估计值是10人/小时，则每小时将失去2名顾客，损失为：2×14小时×1/2（0.7加油效益+0.4洗车效益）=15.40＄/天。因为选择功率B，成本只增加4＄/天，显然，选择功率A所损失的15.40＄的效益能保证功率B的启动。功率B能满足最初设定的5分钟等待最大限度，因此功率C可以不予考虑，除非到达率有较大的增长。解：选择功率A时，根据模型2的公式可以计算出顾客的平均等待时17例3：关于服务台的决策海尔公司住西安售后服务部门，维修工要为空调修理或服务而准备零件。他的这种需求以表的形式递交到零件服务柜台，由柜台职员填表，而此时维修工处于等待状态。维修工的到达呈泊松分布，到达率为40人/小时，职员填表的速率为20份/小时，且处理时间服从指数分布。如果柜台职员的工资为￥6元/小时，维修工的工资为￥12元/小时。请决定柜台职员的最佳数。由于到达率很大，所以假设顾客源是无限的。解：首先假定服务柜台安排3名职员，因为只有一个或两个职员将产生无限长的队列，原因是：在这里将用到模型3的公式（6-5）。根据表计算队列中平均顾客数。由此可看出，每天队列中平均等待数为0.8888，按一天8小时，每小时￥12元计算，维修工等待所付出的代价=0.8888×12×8=￥85.32元。假定增加一个柜台职员，重新计算维修工的等待时间，比较增加一个柜台职员的成本与维修工因此而节约时间所带来的效益两者之间的大小。维修工等待成本：0.1730×12×8=￥16.61（元/天）减少维修工等待时间可节约：85.32-16.61=￥68.71（元/天）增加一名柜台职员的成本：8×6=￥48（元/天）柜台职员由3名增加到4名，可节约成本68.71-48=￥20.71（元/天）所以柜台职员的最佳数是4名。该问题可以引伸为由运送员向维修工运送零件的情况，此时解决该问题需要决定运送员的最佳人数。但是，必须考虑由于传递错误引起时间耽误带来的费用。因为维修工直接到柜台领取零件可以立即纠正零件提取错误。例3：关于服务台的决策海尔公司住西安售后服18例4：有限顾客源某纺织公司对一个车间的一排纺织机（共4台）进行研究表明，平均每台机器每小时都需要调整。就目前的这些调整服务人员来说，平均一次调整的时间为7.5分钟。假定顾客到达数服从泊松分布，服务时间服从指数分布，每台机器闲置时每小时损失￥40元。如果有另外一名调整服务人员（其平均一次调整时间也是7.5分钟）。请决定是否以每小时￥7元的成本雇佣他？解：这是一个有限排队问题。需要比较机器停工成本（包括等待的和被维修的时间）加上一个调整服务人员的成本与机器的停工期成本加上两位调整服务的成本之间的大小。所以必须找出在系统中等待的平均机器数。设：N：总体的机器数；M：调整服务人员数；T：每台机器的维修；U：在被维修之前，每台机器的平均运行时间；L：队列中等待维修的平均机器数；X：服务因子或每台机器维修时间比率（X=T/(T+U)）；H：被维修的平均机器数。需要从有限排队表中获得的值有：D：一台需要维修的机器需等待的概率；F：效率因子，衡量需维修的机器必须等待的结果。有限排队表是根据三个变量来安排的：N为总体大小；X为服务路线数（在此问题中是指维修人员数）。先找到相应的N值的表，查找对应的X值以及D与F值。然后用有限排队系统的模型和公式（6-6）计算其他参数。表6-24台机器停工成本与维修成本比较表维修人员数故障机器数（H+L）故障机器每小时成本（H+L）×40维修人员成本7元/小时·人每小时总成本10.59723.887.0030.8820.45118.0414.0032.04例4：有限顾客源某纺织公司对一个车间的一排19

为解决此问题，考虑一个维修人员和两个维修人员两种情况。情况1：一个维修人员。根据上述资料可知：N=4，T=7.5分钟，U=60分钟，则X=T/（T+U）=7.5/（7.5+60）=0.111通过有限排队表，即N=4的有限表，当X=0.111，且M=1时，可查得F=0.957。队列中等待维修的机器数为：L=N（1-F）=4×（1-0.957）=0.172台机器被维修的机器数为：H=FNX=0.957×4×0.111=0.425台机器表6-2表示的是由于故障机器停工期和维修人员引起的成本。情况2：两个维修人员。根据上述资料可知：N=4，T=7.5分钟，U=60分钟，则X=T/（T+U）=7.5/（7.5+60）=0.111通过有限排队表，即N=4的有限表，当X=0.111，且M=2时，可查得F=0.998。队列中等待维修的机器数为：L=N（1-F）=4×（1-0.998）=0.008台机器被维修的机器数为：H=FNX=0.998×4×0.111=0.433台机器机器闲置成本与两个维修人员的成本显示在表6-2中。最后一列表明，安排一名调整维修人员是最佳选择。四、排队问题的计算机仿真

一些排队问题看视简单，但真正做起来非常困难甚至不可能。前面讨论了独立条件的排队问题，也就是说，无论是由单阶段构成的整个系统还是系列服务中的一个，它们都是独立的，也就是当一个服务的输出发生在下一个服务之前，从实质上说，该输出成为下一个服务的输入。当一系列服务依次进行，且前一个服务的输出率是后一个服务的输入率时，就不能简单地运用前面介绍的公式；另外，当问题不满足前面公式规定的条件时，也不能运用前面的公式。这时解决问题的最好手段是——计算机仿真。为解决此问题，考虑一个维修人员和两个维修人员20例：两阶段装配线

一条装配线上所组装的产品的体积是装配线分析和设计所要考虑的重要因素。因为每个工作站所能存放的产品数量将会影响工人的工作。如果产品体积很大，那么相邻的工作站存在着相互依赖的关系。如图6-6，A和B在一个两阶段装配线上工作，中间没有可以存放半成品的地方，A如果干的慢，B就会被迫等待；相反如果A干得快或者说B完成工作比A用时要长，那么A就得等B。工作站1工作站2员工A员工B图6-6一条装配线上的两个工作站

假设A是组装线上的第一个工人，他能够在任何时候拿到需要组装的半成品进行工作。

该问题分析研究的重点就是A和B彼此间的相互影响。

研究的目标：1）每个工人的平均完工时间是多少？2）这条组装线的生产率是多少？3）A等待B的时间是多少？4）B等待A的时间是多少？5）如果两个工作站间的空间加大，可以存储半成品，从而增加工人的独立性，那么这对于生产率、等待时间等问题会有什么影响？

数据的采集：一种方法是将装配时间分割开，对每个工人单独观测，然后进行汇总。

仿真作为一项分析工具，她的动态性决定了它在定量分析方面具有很大的优势。而解析方法则不同，它表示的是系统长期运转的平均结果。例：两阶段装配线工作站1工作站2员工A员工B图6-6一21秒工人A工人B次数次数5~14.994415~24.996525~34.9910635~44.9920745~54.99401055~64.9911865~74.995675~84.994410050表6-3工人观测数据收集表表6-3是观测工人A、B两人装配时间的数据收集表。为了简化操作，装配时间以10秒为区间进行划分。对工人A观测100次，对B观测了50次。一般地观测次数越多、时间间隔划分越小，则研究的准确性越高。但是投入的时间和人力就会越多，编程和仿真模型运行的时间就会越长。

随机数区间分配表6-4是根据实际观测数据的相同比率进行分配的随机数区间。例如，工人A在100次操作中有4次在10秒种内完成。因此，我们用100个数进行分配。应该分配4个数与10秒钟相对应。这4个数可以是任意的4个数，例如，42、18、12和93，但是，这样会使查找变得非常困难。所以在此，我们分配连续的数给他，比如00、01、02和03。我们得到工人B的50个观测值。有两种办法分配随机数。第一种：只用50个数（如00~49）来进行分配，并在仿真是忽略所有超过49的数，这样将丢弃随机数列中50%的数，是一种浪费。第二种：将频率次数加倍。例如，不是将00~03分配给50次观测中装配时间为10秒的4次观测，而是将00~07分配给100次观测中的8次观测，这样，观测次数加倍了但比例不变。秒工人A工人B次数次数5~14.994415~24.99622秒A的次数随机数区间B的次数随机数区间10400~03400~0720604~09508~17301010~19618~29402020~39730~43504040~791044~63601180~90864~7970591~95680~9180496~99492~9910050表6-4工人A和B的随机数区间

简单仿真表6-5是工人A和B装配10件产品的手工仿真结果。随机数来自随机数表，从二位数的第一列开始向下取数。假定从00时间开始，接下来以秒计算。第一个随机数56对应于工人A装配第一个工作用时55秒。这个工件送给工人B，他的开始时间是50秒。接下来的随机数是83，根据表6-4，工人B用70秒完成了工作。同时，工人A开始装配下一件产品，从第50秒开始用时50秒（因为接下来的随机数是55），在第100秒完成。然而，工人A无法开始第三件产品的工作，因为工人B在第120秒才干完一件活。因此，工人A等待了20秒。（如果他们之间有存储空间，工人A干完的活可以移出工作站，他在第100秒就可以干下一件活。）表6-5中其他数据可以用同样的方法来