排队论及应用举例-.

第六章排队论关键词排队（Queue）指数分布（ExponentialDistribution）单通道、单阶段（SingleChannel,singlePhase）排队系统（QueuingSystem）泊松分布（PoissonDistribution）多通道、多阶段（Multichannel,Multiphase）到达率（ArrivalRate）服务率（ServiceRate）有限队列（FiniteQueue）一、排队问题的经济含义在日常经济生活中，经常遇到排队现象，如：在超市等待结帐、工厂中等待加工的工件或待修理的机器、开车上班等，排队论是运作管理中重要的方法，它是计划、工作设计、存货控制以及其他问题的基础。每一个排队事例的核心问题就是对不同因素作权衡决策，管理者必须衡量为提供更快捷服务而增加的成本和等待费用之间的关系。一种情况是：直接对成本进行权衡决策，例如考虑到顾客排队等待可以增加设备，就要权衡增加设备的成本与多服务顾客所带来的价值的大小，决策比较直观和容易；另一种情况是：排队问题是对医院床位的需求，可以估算增加床位带来的房屋建筑、附加设备以及增加的维护费用等成本，但衡量标准时什么？因为用金钱成本来度量病人对病床的需求显然是徒劳的，尽管可以估计出医院因病床不足会损失多少收入，但无法估计病人因得不到适当的医护所遭受的损失。解决排队问题的基本目标是平衡等待成本与增加资源引起的成本之间的关系。对于一个服务系统来说，这意味着若要给顾客创造很短的等待时间，服务台的利用率将回降低。排队问题中一个关键问题是用什么样的程序或优先规则来选择下一个产品或顾客作为服务对象。成本效益平衡服务成本总成本最小值等待成本最佳能力成本＄服务设施能力图6-1服务成本与等待成本的关系如图6-1所示，是一个典型（稳定）的客运问题中的权衡。等待成本随着服务能力的增大而减小，可以用负指数曲线描述；服务成本可以简单地用线性变化表示；总成本或复合成本则是U型曲线。所以，理想的最优化（最小）成本位于服务成本曲线和等待成本曲线的交点上。排队问题的实际应用顾客到达服务需求量到达的数目时间服务时间普通能力时间图6-2到达与服务的关系如图6-2表示的是到达某一服务机构（银行）的人数和对这一机构服务的需求（信贷人员）。在服务系统营业过程中，每一小时到达系统的顾客人数是一个很重要的变量。从提供服务的观点来看，顾客对于服务的需求是不断变化的，而且经常超过正常的服务能力。可以通过不同的方法对到达人数加以控制。如特殊顾客通道、临时加班、设定等待座位数等。一般服务时间受到服务速度、机器运转速度的影响，另外，服务时间也会因使用的工具、材料或计划的不同而变化。二、排队系统服务系统服务机构等待队列离开顾客源图6-3排队系统的组成如图5-3所示，一个排队系统有三个主要部分组成：一是：顾客源和顾客到达系统的方式二是：服务系统三是：顾客离开系统的方式(是否回到顾客源？)顾客到达到达服务系统的顾客可以分为两类：有限总体和无限总体。1.有限总体。要求服务的顾客数是有限的，通常是排成一队的。顾客总体中的某一位离开其位置（如一台设备停机待修理），顾客就少一个，同时减少了下一次要求服务的概率。相反，当被服务的顾客回到顾客总体中，总体人数对服务需求的概率也就增加了。2.无限总体。对于服务系统来说顾客数量足够大，由于人数增减而引起的总体规模的变化不会对系统的概率分布产生显著的影响。3.顾客到达的分布。这是一个到达率或单位时间到达数的问题。固定到达的分布呈周期性的，即相继到达的两个顾客之间的时间间隔几乎相同。在生产系统中，通常运用一些技术控制顾客在固定的时间间隔内到达。多数情况下，顾客的到达呈随机分布。首先，分析相邻两个顾客到达的时间间隔是否服从某些统计分布？通常假定相邻两次到达的时间间隔服从指数分布其次，在设定时间长度为T，然后确定在时间T段内有多少顾客到达并进入系统？通常假定单位时间到达的人数服从泊松分布。4.第一种情况：指数分布。当顾客已完全随机方式到达服务机构时，相邻到达时间间隔服从指数分布。如图5-4所示。其概率密度函数为：（6-1）式中代表单位时间段到达的顾客数量。图5-4中曲线下方的阴影区域即为函数5-1在正数范围内的积分，即。通过这种方法，就可以计算出某一特定时间顾客到达的概率。例如：在顾客是单个到达服务系统（）时，可通过两种方法得到表5-1。一种是根据式，另一种可以应用负指数分布。表的第二栏是下一个到达的顾客时间间隔超过分钟的概率；第三栏为下一个顾客到达时间小于分钟的概率。tetf)()(tft图6-4指数分布te11texett（1）（2）（3）下一个顾客将在下一个顾客将在小于t分钟大于t分钟内分钟内到达的概率到达的概率(3)=(1)-(2)01.0000.50.610.391.00.370.631.50.220.782.00.140.86t期望值方差1215.第二种情况:泊松分布。主要针对某一时段T内有n人到达的概率，到达过程是随机的，则服从泊宋分布。如图5-5所示。计算公式为：（6-2）式5-2表示在T时间内有n个顾客到达的概率。例如，如果一个系统的平均到达率是每分钟有3个顾客到达（），要求1分钟内有5个人到达的概率为：.149.168.224.102.050.224.20.10.05期望值方差平滑曲线1234568101233时间T内有n人到达的概率到达人数n图6-5泊松分布（）3T0!)()(neTnPTnT101.0!5)13()5(1351eP这就是说，在任何一分钟的间隔期内有5人到达的概率是10.1%。泊松分布是一类离散型的分布，但通常用一条平滑曲线来表示（n越大，曲线越平滑）。在这个实例中，n指的是到达系统的人熟，因而该分布是离散的，且必须为整数。排队系统1.队列考虑的因素：队长、队列数、排队规则2.队长无限队列：即指相对于服务系统来说是相当长的队列。如：堵塞在立交桥上的车辆、绕这街道排列成队购买商品的顾客等。有限队列：是指由于法律或实际空间特点制约，排队等待服务的队长受到限制。如：停车厂、加油站等，但是有可能出现到达后离开，过一会有可能再来或到其他地方寻求服务。这是有限总体条件下的两种不同表现。3.队列数单列队是指只有一个队列。多列队指排在两个或两个以上服务台前的多个单列队，或者指在中间某点汇集的多个单列队。多列队的缺点是如果前面的几个服务时间短或者那些在其他队的顾客需要短服务时间时，到达的顾客将会挪动队列。4.排队规划是指决定队列中顾客接受服务次序的一个或一系列优先法则。直接影响着队列中顾客人数、平均等待时间、等待时间变化范围以及服务设施的效率等。在使用任何优先法则时，两大现实问题：一是确保顾客了解并遵守法则；二是保证有一个能使雇员对队列进行管理的系统。排队规则先来先服务最短过程时间预订优先紧急优先最优顾客优先其他最大需求优先最大盈利优先5.服务时间分布在排队问题中，服务率通常是指单位时间内服务台完成服务的顾客数，而不是指每位顾客的服务时间。固定服务时间是指每次服务的时间完全相同，这仅限于机器受控运作。当服务时间比较随机时，则近似指数分布，一般用作为每时间段内被服务的平均顾客数。6.队列结构——见图5-6所示单通道、单阶段：最简单的队列结构形式。用简单的公式可以解决到达人数和服务时间的标准分布问题。如单人理发店。单通道、多阶段：由一系列以非常标准的顺序进行的服务构成。如：洗车服务的吸尘、打湿、冲洗、晾干、洗车窗和停车。重要的因素是该服务由多少个步骤组成，在各个不同步骤中又分别形成了队列。多通道、单阶段：如：银行的出纳窗口、大型商场的收银台等。每个顾客不均匀的服务时间会引起队列流动不均匀，导致某些顾客先于早到的顾客接受服务，一定程度上影响顾客挪动队列。为了保证顾客按到达时间顺序接受服务，则要排成一个单队，当一个服务台空出来时，队列最前面的顾客就可以去接受服务，如银行自动抽号排队。最大的问题在于需要对队列进行刻板的控制以维持秩序和引导顾客到空闲的服务台。多通道、多阶段：服务由多个步骤组成，完成每个服务步骤有两个或多个服务台，一般可有多个顾客同时被服务。如：医院里接待病人的系统：挂号（有多个窗口，病历上填写病人信息）、就诊（同一科室有多位大夫）、化验、检查（同一化验、检查有多个窗口和设施）、回复就诊（同一科室有多位大夫）、处方划价（多个窗口）、缴费（多个窗口）、取药（多个窗口）。混合型：两种情况：1）多通道—单通道结构；2）交错通道结构。考虑到阶段问题，如：单阶段服务的多通道变成了单通道（如过桥时多队变成一队）；多阶段服务的多通道变成了单通道（如多条子装配线汇成一条主装配线）上述形式的选择，一方面依赖于被服务顾客数；另一方面，依赖于服务顺序的特殊要求。队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交错通道图5-6队列结构队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交错通道图6-6队列结构顾客离开“经常发生事件（recurring-common-coldcase）”：顾客回到顾客源，马上成为一名新的顾客要求服务。如：机器例行修理后重新使用，可能再次出现故障而需要修理。“只发生一次事件（appendectomy-onlyoncecase）”：顾客重新要求服务的可能性极小，即不可能重新要求服务。如：机器进行彻底检查和修理后，在一段时间内不会重新维修。顾客接受服务后，离开的情况可能有两种顾客源有限时，对回头客服务的任何改变都会改变顾客到达率，引起排队问题的特征的改变。三、排队模型问题一：顾客等待。银行希望知道有多少顾客在等待其服务到车（drive-in）出纳员的服务？出纳员的效率是多少？如果要求在95%的时间内，任一时刻系统中不超过三辆车，则其服务率应达到什么水平？问题二：设备选择。公司有三中不同的设备可以提供同一种服务，设备功率越大，成本也越高，但服务速度越快。因此作决策时，成本与收入是紧密相联的。问题三：服务人数决策。经销公司的一个销售部门必须决定一个柜台雇佣多少职员。职员越多，成本也越高，但服务等待时间的减少能带来部分成本的节约。问题四：有限总体。前述都是无限总体，而对于有限顾客总体，如：车间有若干台设备，一名维修工负责4台设备的运转，在充分考虑设备闲置成本和维修工的服务成本的基础上，决定应该雇佣多少名维修工？四种典型的问题模型分布服务阶段顾客源到达人数分布排队规则服务时间分布允许的队列长度典型例子1单通道单一无限泊松先来先服务指数无限银行出纳员服务系统；单道收费桥系统2单通道单一无限泊松先来先服务常数无限自动洗车服务；游乐园的滑行铁道系统3多通道单一无限泊松先来先服务指数无限汽车经销公司零件柜台服务系统4单通道单一有限泊松先来先服务指数无限工厂里故障机器的维修服务表6-1特殊队列模型特征在研究上述问题时，给出四种排队模型及其求解公式。但一个基本假设是：所研究的过程是持续稳定的。如果在一个问题中，其服务率或者到达率随时间而改变的话，运用公式得出的结果将不很精确。四种队列问题的求解公式：)(2ln模型1：sn)(lt1stnnP))(1()1(0P（6-3）)(22lnlsnn)(2lt1lstt模型2：（6-4）)(MnPlwlsnnllnt1lsnt模型3：给出P与M值，查表可得ln（6-5）是有限排队问题，可以通过有限表来解决。模型4：UTTX0)!(!PXnNNPnnHLTLNUTLW)(FNXH)1(FNL)1(XNFJWUTUTF（6-6）HLn公式6-3、4、5、6中符号注释服务率到达率）与总服务率的比值（单个服务台的总到达率系统中的顾客数n完全相同的服务路线数M概率系统中恰有几个顾客的nP等待的概