第十一章 排队论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本版式,第二层,第三层,第四层,第五层,*,第十一章 排队论,教材第,12,章 服务业的作业计划,P313,1,第十一章 排队论,教学目的,：,了解排队论的经济含义；排队系统的一般概念和简单的排队系统；了解排队问题的计算机仿真。,2,学习内容,大纲内容,知识要点,基本概念,排队系统,泊松分布、负指数分布,排队系统,排队系统的一般指标,排队模型的运用,M/M/1,、,M/M/C,排队问题的仿真,Excel,仿真,3,引导案例,-1,时间花在哪里？,4,引导案例,-2,银行排队系统,5,引导案例,-3,医院排队系统,6,形形色色的排队系统,达到的顾客,要求服务的内容,服务的机构,出故障的机器,修理技工,病人,电话呼叫,进港货船,入水库河水,达到机场上空的飞机,刑事案件,达到路口的车辆,来犯敌机,修理,领取修配零件,诊断（或治疗）,通话,装（卸）货,放水、调整水位,降落,侦破,通过路口,截击,修理技工,发放,修配零件,的管理员,医生（或治疗设备）,交换台,装（卸）货码头（泊位）,水闸、管理员,跑道,刑侦部门,交通信号灯,我防空部队,7,为什么会出现排队现象？,假定每小时平均有,4,位顾客到达，服务人员为每位顾客的平均服务时间为,15,分钟。如果顾客到达的间隔时间正好是,15,分钟，而服务人员为每位顾客的服务时间也正好是,15,分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。,在以下情况将出现排队现象：,平均到达率高于平均服务率,顾客到达的间隔时间不一样（随机）,服务时间不一样（随机）,顾客离开,顾客,顾客排队,服务设施,8,到达数量,时 间,普通能力,排队问题并不是系统的固定状态，它与系统设计与管理的控制有很大关系。如快餐店只允许很短的队长，也可为特定的顾客留出特定的时间段；也可以通过使用更快的服务人员、机器或采用不同的设施布局和政策来影响顾客的到达时间和服务时间。,9,1,排队论的基本问题,1.1,排队论的主要研究内容,数量指标,研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统的基本运行特征。,统计推断检验系统是否达到平稳状态；检验顾客达到间隔的独立性；确定服务时间分布及参数。,系统优化,系统的最优设计和最优运营问题。,10,1.2,排队论的经济含义,排队问题的核心问题实际上就是对不同因素做权衡决策。管理者必须衡量为提供更快捷的服务（如更多的车道、额外的降落跑道、更多的收银台）而增加的成本和相应的等待造成的费用之间的关系。,11,服务成本与等待成本的权衡（成本效益平衡）,总成本,成本,最佳能力,等待成本,服务成本,最小值,排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小,12,2,排队论概述,2.1,基本概念,概念,在队列中，等待服务的顾客（,customer,）和服务台（,server,）就构成了一个排队系统（,queuing system,）。,本质,研究服务台与顾客之间服务与接收服务的效率问题。,总体目标,以最少的服务台满足最多的客户需求。,13,2.2,排队系统的一般形式,排队可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。,顾客源,排队结构,服,务,机,构,顾客到来,排队规则,服务规则,顾客离去,服务系统,14,3,排队问题的特征,总体来源,到达与服务模式,排队纪律（服务顺序）,服务员数量（通道）,15,有限顾客源,例如：公司只有三台机器时，需要维修的数量,潜在顾客数量,无限顾客源,例如：排队等候公共汽车的乘客人数,3.1,总体来源,分析排队问题所用方法取决于潜在顾客数量是否有限。,本章讨论的重点,16,3.2,顾客到达与服务模式,常用的模型,假定,顾客到达速度服从,泊松分布,，服务时间服从,指数分布,。,17,3.2.1,泊松分布,定义：设,N,（,t,）为时间,0,，,t,内达到系统的顾客数，如果满足下面三个条件：,平稳性：在,t,，,t+,t,内有一个顾客达到的概率与,t,无关；,独立性：在任意两个不相交时间区间内顾客达到相互独立；,普通性：在,t,，,t+,t,内多于一个顾客达到的概率极小，为,(,t),，可以忽略。,则称,N,（,t,），,t 0,为,Poisson,过程，其对应的分布为泊松分布（,Poisson,分布）。,18,泊松分布的形式,相对,频度,0 1 2 3 4 5 6 7 8 9 10 11 12,0.20,0.18,0.16,0.14,0.12,0.10,0.08,0.06,0.04,0.02,0.00,泊松分布,（比率）,每单位时间顾客数,图,泊松分布,19,泊松分布的概率密度函数,如果一个系统的平均到达率是每分钟有,3,个顾客到达（,=3,），求,1,分钟内有,5,个人到达的概率,20,3.2.2,指数分布,当顾客以完全随机的方式到达服务实施时，相邻到达间隔时间服从指数分布，但,平均到达率不变,；,随机服务时间服从指数分布，但,平均服务率不变,；,21,（负）指数分布的形式,图,负指数分布,指数分布,（时间）,相对频率,0,时间,22,（负）指数分布的概率密度函数,23,（,1,）,（,2,）,（,3,）,t,（分钟）,下一个顾客在大于等于,t,分钟内到达的概率,下一个顾客在小于等于,t,分钟内到达的概率,0,1.00,0,0.5,0.61,0.39,1.0,0.37,0.63,1.5,0.22,0.78,2.0,0.14,0.86,表 下一个到达的顾客的时间间隔的概率,24,3.2.3,泊松分布和指数分布的关系,泊松分布与指数分布可以互相推导得到。泊松分布的期望值和方差相等，都为,；指数分布期望值为,1/,方差为,1/,2,。,相邻顾客到达,时间间隔,服从指数分布，单位时间段内,到达的顾客数服从泊松分布。,25,3.3,排队纪律,/,排队规则,/,服务顺序,排队规则的,3,种类型,损失制,等待制,排队规则,混合制,26,等待制的四种类型,等待制,最短处理时间,SPT,随机服务,RS,后到先服务,LCFS,先到先服务,FCFS,27,3.4,服务员数量,排队系统中的常见变形,Title in here,多通道,单阶段,Title in here,单通道,多阶段,Title in here,单通道,单阶段,Title in here,多通道,多阶段,排队系统,28,排队系统的四种变形,-1,单通道,多阶段,服务台,单通道，单阶段,排队,单通道、单阶段排队系统,单通道、多阶段排队系统,排队,服务台,服务台,29,多通道,单阶段,多通道,多阶段,多通道、单阶段排队系统,多通道、多阶段排队系统,排队系统的四种变形,-2,30,4,排队模型,4.1,排队问题的一般表达方式,一般形式：,X/Y/Z/A/B/C,X,顾客相继达到,时间间隔,的概率分布；,Y,服务时间的概率分布；,Z,服务台的个数；,A,服务机构的容量（,容纳所有顾客的数量,）；,B,顾客源的容量,C,排队规则,31,4.2,一些特殊排队模型,模型,分布,服务,阶段,顾客源,到达,分布,排队,规则,服务时间分布,队列,长度,典型例子,模型表示,1,单通道,单一,无限,泊松,FCFS,指数,无限,只有一个出口的收费桥,M/M/1,2,单通道,单一,无限,泊松,FCFS,常数,无限,游乐园的,过山车,M/G/1,3,多通道,单一,无限,泊松,FCFS,指数,无限,银行柜台,服务,M/M/C,4,多通道,单一,有限,泊松,FCFS,指数,无限,工厂里故障机器的维修,指数分布,常数分布,32,4.3,模型符号定义（无限顾客源）,符号,代表,顾客到达速度（到达率）；,1/,代表相邻到达平均时间间隔,服务速度（服务率）；,1/,代表平均服务时间,系统利用率，即到达率与服务率的比值,L,q,等候服务的顾客平均数,L,s,系统中的顾客平均数（正在等候的正在接受服务的）,W,q,顾客排队等候的平均时间W,s,顾客在系统中花费的平均时间（排队等候时间服务时间）,r,正在接受服务的顾客平均数,n,系统中的平均顾客数,C,服务者（通道）数量,P,0,系统,0,单位概率,P,n,系统有,n,单位的概率,L,max,队列中等候的最大期望值,33,系统利用率,正在接受服务的顾客平均数,系统中的平均顾客数,系统中等待的平均顾客数,顾客平均逗留时间,顾客平均等待时间,4.4,模型参数计算,-1,（,M/M/1,）,34,三种重要的关系,“管道原理”,:,稳定系统中平均输出,=,平均输入（率）,=,时间的可加性,在系统中逗留的时间等于服务时间加排队,利特尔法则,35,4.4,模型参数计算,-2,（,M/G/1,）,系统利用率,正在接受服务的顾客平均数,系统中等待的平均顾客数,系统中的平均顾客数,顾客平均逗留时间,顾客平均等待时间,常数服务时间能将系统的平均顾客数砍掉一半,36,4.4,模型参数计算,-3,（,M/M/C,）,-1,系统利用率,正在接受服务的顾客平均数,系统中等待的平均顾客数,系统中的平均顾客数,顾客平均逗留时间,顾客平均等待时间,37,4.4,模型参数计算,-3,（,M/M/C,）,-2,38,例,1,一个码头，设待卸货船到达时间间隔服从负指数分布，平均到达,2,艘,/,小时；服务台是,1,台吊车，卸货时间服从负指数分布，平均每,20,分钟可卸一艘货船，当被占用时，新到货船只能停在码头等待。求在平稳状态下码头上货船的平均数；等待卸货船只的平均数；每艘货船在码头的平均停留时间；货船平均需等待多长时间可以开始卸货。,39,解：,这是一个典型的,M/M/1,排队,问题,40,例,2,某医院手术室根据病人就诊和完成手术时间的记录，任意抽查,100,个工作小时，每小时来就诊的病人数,n,的出现次数如表,6,所示。又任意抽查了,100,个完成手术的病例，所用时间,t,出现的次数如下表所示。试分别用公式、,excel,和仿真求解：,41,到达病人数,n,出现次数,f,n,0,10,1,28,2,29,3,16,4,10,5,6,6,1,合计,100,到达病人数,为病人完成手术,时间,t/,小时,出现次数,f,t,0.00.2,38,0.20.4,25,0.40.6,17,0.6 1.8,9,0.81.0,6,1.01.2,5,1.2,0,合计,100,手术时间,42,解：,这也是一个,M/M/1,排队,问题,（,1,）计算平均到达率,平均手术时间,平均服务率,43,（,2,）取,=2.1,，,=2.5,，通过统计检验方法认为病人到达数服从参数为,2.1,的泊松分布，手术时间服从参数为,2.5,的指数分布。,（,3,）,服务设备利用率,这说明服务机构（手术室）有84%的时间是繁忙,的,（被利用），有16%的时间是空闲的。,44,（,4,）,依次带入公式，算出各指标得：,45,单通道仿真视频,46,排队系统仿真软件,Flexsim-1,Flexsim,是建立在系统理论、控制理论、数理统计、信息技术和计算机技术等理论基础之上的仿真软件，它是系统模型规范化和数字化相结合的过程。,47,排队系统仿真软件,Flexsim-2,Flexsim,在排队系统中的应用主要是利用仿真模型来研究排队系统，首先通过仿真模型的运行，便于更好的观测排队系统过程中出现的一系列复杂变化和动态过程；其次通过仿真模型稳定后的相关值与排队系统理论值的比较，得出他们的值正好相等。,Flexsim,在排队系统中的应用有助于我们进一步理解排队系统的相关概念和加深对排队系统的全面认识，从而对改进排队系统做出正确的举措。,48,单通道,Excel,求解,49,例,3-1,Robot,公司在全美经营把加油和汽车冲洗合并在一起的业务。,Robot,公司对加满油的车辆提供免费冲洗，对于不加油只冲洗的车收费,0.5,美元。以往的经验表明：加油并且洗车的顾客数和单独洗车的顾客数大致相等。平均加一次油可盈利,0.7,美元，洗一次车的成本是,0.1,美元，公司每天营业,14,小时。,Robot,有三档功率和清洗组合不同的设备。选择,I,档功率时，可以每,5,分钟洗,1,辆车，每天的成本是,12,美元。,II,档功率高于,I,档，每,4,分钟洗,1,辆车，但每天的成本是,16,美元；选择,III,档功率时，每洗,1,辆车需,3,分钟，但每天的成本是,22,美元。,50,例,3-2,Robot,公司估计，每个顾客洗,1,辆车不愿等待的时间不超过,5,分钟，若等待的时间过长，公司将失去顾客。,若估计每小时有,10,名顾客前来洗车，那么该选择哪档功率的设备？,51,解：,这是一个典型的,M/G/1,排队,问题,（,1,）选择功率,I,时,顾客平均等待时间,52,（,2,）选择功率,II,时,顾客平均等待时间,如果等待时间是唯一标准，则应选择功率,II,的设备，但在我们做出最后结论之前，还必须看一下二者的利润差异。,53,(3),对于功率,I,，由于等待时间为,12.5,分钟，部分顾客会放弃接受服务。尽管这将使数学分析复杂化，我们仍可以估计出选择功率,I,时营业额的减少量。我们可以通过假设,Wq=5,分钟（,1/12,小时），并从中解得,，这将是最有效的顾客到达率。,54,因此，既然,的最初估计是,10,人,/,小时，则每小时将失去,2,名顾客。,每天的损失,(S),：,而选择功率,II,，成本只增加了,4,美元,/,天，显然，相比较于损失的,15.4,美元，我们都会选择功率,II,设备。,功率,II,能满足最初设定的,5,分钟等待最大限度，因而功率,III,可不予考虑，除非,变大。,55,例,4 Disneyland,乐园中的排队,在游乐园中的频频排队会极为扫兴，,Disneyland,中的FastPass(QuickPass),系统就是想解决这个问题的。其工作原理如下：,到达的顾客将自己的票插入,FastPass,的,slot,中；,FastPass,计算出建议顾客返回的时间间隔或时间点或时间窗；,顾客无需排队，在指定的时间返回就可持票进入。,56,思考,QuickPass,对排队系统的那些特征参数做了改变？,改变顾客到达模式，是如何影响系统绩效？,57,解：,泊松分布到达,常数分布到达,平均达到率,11,人,/,分钟,11,人,/,分钟,平均服务率,12,人,/,分钟,12,人,/,分钟,排队长度,5.04,0,系统队长,5.96,0,平均排队时间,0.46,0,系统利用率91.70%,91.70%,58,Disneyland,问题解决了吗？,如果游客不按时间返回？,是否让游客等待时间太久了？,过山车是按时间开还是人数一够就开？,www.stanford.edu/yaoxie/Pubs_2.htm,59,例,5,某售票所有三个窗口，顾客的到达服从泊松分布，平均到达速率,=0.9,人,/min,；售票时间服从负指数分布，平均服务速率,=0.4,人,/min,。现设顾客到达后排成一队，依次向空闲的窗口购票，如图所示。试分别用公式、,excel,和仿真求解：,(1),整个售票所空闲概率,(2),平均队列长和平均队长,(3),平均等待时间和逗留时间,(4),顾客到达后必须等待的概率（,n3),60,顾客到达和服务图,61,解：,这是一个典型的,M/M/C,排队,问题,(1),整个售票所空闲概率,62,(2),平均排队长度和平均队列长,(3)平均等待时间和逗留时间,63,(4),顾客到达后必须等待的概率（,n3),64,M/M/3,仿真视频,65,M/M/3 Excel,求解,66,例,6,银行取号系统有用吗？,就例,5,，如果其他条件不变，顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，就形成,3,个队列，如下图所示。试分别用公式、,excel,求解：,(1),整个售票所空闲概率,(2),平均队列长度和平均队长,(3),平均等待时间和逗留时间,(4)顾客到达后必须等待的概率（,n3),67,顾客到达和服务图,68,解：,这是,3,个,M/M/1,同时服务的,排队,问题,(1),整个售票所空闲概率,(,每个窗口空闲,),(4),顾客到达必须等待的概率（每个窗口,n1),69,(2),平均排队长度和平均队列长,(3)平均等待时间和逗留时间,70,3,个,M/M/1 Excel,求解,71,结论：银行取号系统是有效的,指标,数值,排队长度,1.70,系统队长,3.95,平均排队时间,1.89,服务台空闲概率,0.075,顾客必须等待的概率,0.57,指标,数值,排队长度,2.25,系统队长,9,平均排队时间,7.5,服务台空闲概率,0.25,顾客必须等待的概率,0.75,72,结论：银行取号系统是有效的,从这两个系统的主要指标比较可以看出,混合排队比独立排队具有显著的优越性,，这一点是在排队系统的排队方式的设计时应该注意的。,73,普遍结论：集中使用优于分散使用,将资源组合在一起为所有的顾客提供服务，可以在等待时间不变的条件下，减少所需要的资源总量。如果是两列独立排队，那么客户可能要等那位指定的服务人员提供服务，这位服务人员可能当时正忙得抽不开身，而另一位服务人员却闲着没事干。在集中使用的系统中就不会出现这种现象。,大规模制造或服务设施的规模经济学,在保持同样利用率的情况下减少平均等待时间,在保持同样平均等待时间的情况下提高利用率74,5,排队系统最优设计,成本分析,5.1,概述,排队系统的最优设计和最优控制，即排队系统的最优化问题，其目的在于使排队系统达到,最大效益,或者说在一定指标下使排队系统,最为经济,。,75,服务成本与等待成本的权衡（成本效益平衡）,总成本,成本,最佳能力,等待成本,服务成本,最小值,排队分析的目的是使顾客等待成本与服务能力成本这两项成本之和最小,76,5.2 M/M/1,模型中的最优服务率,u,-1,最佳服务能力是使总成本最小化：,总成本,=,顾客等候成本,+,服务能力成本,77,5.2 M/M/1,模型中的最优服务率,u,-2,所以,M/M/1,模型的最优服务率为：,78,例,7,设某服务机构，单服务台，顾客到达率为每小时,12,位顾客。假定每位接受顾客的顾客其等待费用为每小时,5,元，服务成本为每位顾客,2,元，欲使总平均费用最小，服务率应为多少？,79,解：,这是一个标准的,M/M/1,排队,问题,80,5.3,、,L,q,、,L,s,三者的关系,-1,当系统利用率增加时，队列平均等候数与顾客排队等候的平均时间呈指数增长。,81,队列中平均等 侯数,100%,系统利用率,0,5.3,、,L,q,、,L,s,三者的关系,-2,82,5.3,、,L,q,、,L,s,三者的关系,-3,平均队长（和平均等待时间）与服务台利用率之间的关系不是线性的关系。资产利用率太高会造成服务质量急速下降，因而要权衡利弊。,要保证服务质量，就必须保持“过剩的”生产或服务能力。,83,6,解决排队问题的方法,6.1,理论方法,减少平均服务时间,减少服务时间的可变性,增加服务人员,减少平均到达人数,通过顾客预约等办法来减少到达的可变性,集中使用服务资源,更好地计划和调度,84,6,解决排队问题的方法,6.2,其他方法,服务场所提供娱乐设施,医生等候室放报纸杂志,自动维修间用收音机或电视,航空公司提供空中电影,等候电梯处放镜子,超级市场把冲动性商品摆放在收款台附近,85,6,解决排队问题的方法,6.3,掌握客户的感受:等待心理学,客户所感受到的等待可能与实际的等待有很大的差别。研究结果表明：,服务越有价值，人们就越愿意多等一会儿。,服务开始之前的等待感觉要比服务过程中的等待要长。,心急会让人觉得等待的时间很长。,不公平的等待比公平的等待要长。,不确定的等待比已知的等待要长。,不明情况的等待要比知情的等待要长。,没事干的时候会让人觉得比有事干的时候要长。,独自等待会让人觉得比大家一起等待要长。,86,结 束,87,