第十四章排队模型与仿真

1,Data,ModelandDecisions数据、模型与决策,Session14QueuingTheoryandSimulation排队与仿真,2,SessionTopics,SystemCharacteristics系统特征MeasuresofSystemPerformance系统绩效度量SomeQueuingModels一些排队模型ApplicationofQueuingTheory排队论的应用IntroductiontoSimulation仿真介绍TypesofSimulation仿真类型SimulationSteps仿真步骤ApplicationsofSimulation仿真应用,3,QueuingTheory排队理论,哪儿有排队现象呢?机器等待修理电话忙音银行排队邮局排队餐厅排队商场排队,4,14.1排队模型的要素,基本排队系统:,顾客:一个挨着一个的到来,接受某种服务.队列:等待的服务的顾客服务台:提供服务,5,一个例子:HerrCuttersBarberShop,赫尔卡特先生是一个德国理发师,他经营着一家单人理发店.赫尔卡特先生每天早上8:00开始营业.下表给出了这个排队系统的的有关信息.,6,连续两个顾客到达排队系统的时间间隔称为到达间隔时间(interarrivaltimes).到达时间的巨大差异对于排队系统来说是很正常的.通常不可能预测要过多长时间下一个顾客才会到来.单位时间里顾客到达的期望数称为平均到达率l(meanarrivalrate).l=顾客到达排队系统的平均到达率到达时间间隔的平均值是:1/l=到达间隔时间的期望大多数的排队模型假设到达间隔时间的概率分布的形式是指数分布.,到达,7,到达间隔时间的指数分布,注意在曲线的最高点时间非常小,随着时间变长曲线以“指数形式”下降.这表明低于均值的较小的到达间隔时间有大的可能性.而分布向右伸展很长表明比均值大得多的到达间隔时间出现的概率很小.,对于大多数的排队系统,服务台无法控制顾客何时到达.在这种情况下,顾客总的来说是随机到达的.随机到达意味着到达时间是完全无法凭感觉预测的,下一分钟有顾客到达的概率和其他分钟相同(不多也不少).从上一个到达发生经过了多长时间并不重要.唯一符合随机到达的到达间隔时间分布是指数分布.下一分钟到达的概率完全不受上一次到达的影响的事实称为无记忆性(lack-of-memoryproperty).指数分布具有无记忆性.,8,队列中的顾客数(numberofcustomersinthequeue)是等候服务的顾客数量.系统中的顾客数(numberofcustomersinthesystem)是队列中的顾客数加上正在接受服务的顾客数量.队列容量(queuecapacity)是队列所能容纳顾客的最大数量.无限队列(infinitequeue)是为了应用的方便,可以容纳无限数量的顾客的队列.当容量很小,需要将其考虑在内时,这个队列就称为有限队列这个队列(finitequeue).,队列,9,先到先服务(FCFS):,多种优先权:,队列规则(queuediscipline)指:选择队列中的成员接受服务有顺序.Themostcommonisfirst-come,first-served(FCFS).Otherpossibilitiesincluderandomselection,somepriorityprocedure,orevenlast-come,first-served.,10,服务,对于一个基本的排队系统,每一个顾客单独接受一个服务者提供的服务.拥有多于一个服务台的系统称为多服务台系统,单服务台系统只有一个服务台.,单服务台,多服务台,11,当一个顾客接受服务时,从服务开始到结束经过的时间称为服务时间(servicetime).每一位置顾客的服务时间是不同的.然而基本的排队模型假设服务时间是一个特定的概率分布,与哪一个服务台正在提供的服务无关.服务时间分布的平均值表示为:1/m=期望服务时间m是平均服务率(meanservicerate).m=一个连续工作的服务台单位时间的服务量的期望值,12,一些服务时间的分布,指数分布最应用最多的服务时间的概率分布.比其他分布分析容易得多.尽管这个分布在大多数情况下非常适合于到达间隔时间的分布,但对于服务时间实际是却不全是这样.当服务的提供是随机的,指数分布是一个相当不错的近似.Standarddeviation:s=Mean固定服务时间(ConstantServiceTimes)当排队系统包含一系列固定顺序的操作,对于每一位顾客要花费大约相同的时间时,固定服务时间是一个很好的近似.Standarddeviation:s=0.爱尔良分布(ErlangDistribution)波动量介于指数分布和固定分布之间的一个分布.有一个分布参数k,称为形状参数,它决定了标准差.Inparticular,s=mean/(k),13,服务时间分布标准差与均值的关系,14,排队模型的符号表示,排队模型通常用下列形式来表示:服务时间的分布/服务台数目到达间隔时间的分布用于表示可能分布的符号是:M=Exponentialdistribution(Markovian)D=Degeneratedistribution(constanttimes)Ek=Erlangdistribution(shapeparameter=k)GI=Generalindependentinterarrival-timedistribution(anydistribution)G=Generalservice-timedistribution(anyarbitrarydistribution),15,SomeModels一些模型,单服务台指数服务时间(M/M/1)单服务台一般服务时间(M/G/1)多服务台指数服务时间(M/M/s),16,模型假设的总结,1、到达间隔时间是独立的，服从一种特定的概率分布。2、所有到达的顾客都进入排队系统，并等待直到服务结束。3、排队系统有一个无限队列，因此队列将可以容纳无限量的顾客。4、顾客服务优先规划是先到先服务。5、排队系统拥有特定数量级的服务台，每一个服务台能够为任意一位置顾客提供服务。6、每一位顾客由一个服务台单独提供服务。7、服务时间是独立的，服从特定的概率分布。,17,排队系统的一些例子,系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员管道服务阻塞的管道管道工电影院售票窗口人售票员机场检票处人航空公司代理人经纪人服务人股票经纪人,CommercialServiceSystems商业服务系统,18,系统类型顾客服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心雇员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员,InternalServiceSystem内部服务系统,19,系统类型顾客服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车,TransportationServiceSystem运输服务系统,20,14.3排队系统的绩效测度,当顾客是提供服务的组织(内部服务系统)的内部顾客时,第一个测度比较重要.在这种情况下,让顾客等待会损失生产力,损失的生产力直接与等待的顾客顾客数量有关.商业服务系统(外部顾客接受商业组织的服务)会认为第二个测度更加重要.对于这样的排队系统,一个重要的目标是保持顾客满意.比起已经有多少顾客在等待,顾客更关心他们会等多久.使顾客等待时间过长会导致未来业务利润损失.,平均顾客等待个数平均顾客等待时间系统利用率,21,定义绩效测度,=顾客到达率=服务率(1/=平均服务时间)Lq=队列中的顾客数L=系统中平均顾客数(包括正在接受服务的顾客)Wq=队列中平均等待时间W=包括服务的平均等待时间Pn=有n个顾客在系统的概率=系统利用率,这些定义假设排队系统处于平衡状态.考虑整个排队系统(L和W)或仅仅是队列(Lq和Wq),这取决于排队系统本身.对于医院的急诊室和消防部门,队列可能更重要.对于一个内部服务系统,整个排队系统更加重要.,22,系统利用率系统中平均顾客数队列中平均等待时间包括服务的平均等待时间,BasicRelationships基本关系,23,14.4案例研究:杜皮特公司问题,杜皮特公司(DupitCorporation)在办公复印机市场上长期牌领导地位.杜皮特公司有一个服务部门,负责为公司的顾客提供高质量的服务支持,在需要的时候维修公司的设备.这项工作由公司的技术服务代表在顾客所在地进行.Currentpolicy:每一位技术代表的地域应当有足够的设备,合得技服务代表在大约75%的时间里处于维修工作状态(或在到维修地点的路上).当连续工作时,每一个技术服务代表应当能够平均一天修4台设备(每台设备平均需要2小时,包括先进时间)为了使顾客的等待时间最短.每一个工作日平均要接到3个维修电话.公司的设备平均50个工作日需要一次维修,因此要为每一个技术服务代表负责的区域指定大约150台设备.提出的新的服务标准:在技术服务代表开始前往顾客所在地修理设备之前,顾客的平均等待时间不应超过2小时.,24,解决问题可供选择的方案,ApproachSuggestedbyJohnPhixitt:个性目前的政策,降低期望技术服务代表进行维修工作的时间百分率.这涉及到简单地降低分配给每一个技术服务代表的设备的数量以及增加更多的技术服务代表.这个方法可以使得过去为公司服务得很好的服务部门的工作方式能够延续下去,同时还可以提高服务水平,满足市场上新的需求.ApproachSuggestedbytheVicePresidentforEngineering:为技术服务代表提供新的装备,这样可以大大降低所需的较长时间的修理时间尽管这很昂贵,但显著地缩短平均维修时间.ApproachSuggestedbytheChiefFinancialOfficer:将现在的单个技术服务代表负责区域转变为较大的区域.由多个技术服务代表提供服务.在忙的时候通过团队支持可以大缩短平均维修等待时间而不需要雇用新的技术服务代表.ApproachSuggestedbytheVicePresidentforMarketing:授予这种新的打印复印机的所有者比其他公司的顾客优先接受服务的权利.,25,每一个技术服务代表的排队系统,Thecustomers:需要修理的设备.Customerarrivals:打给每一个技术服务代表要求修理的电话.Thequeue:顾客所在地等待修理的所有设备.Theserver:技术服务代表.Servicetime:技术服务代表花在一台设备上的总时间,包括到等待维修设备所在地的行进时间和维修时间.(因此,当技术服务代表开始前往设备所在地时,这台设备就可以视为已经离开队列进入服务系统了),26,单服务台排队模型,l=到达排队系统的顾客的平均到达率=单位时间期望到达顾客数1/l=期望到达间隔时间m=平均服务率=单位时间期望服务完成的顾客数1/m=期望服务时间r=有效因子(利用率)=它代表了一个服务台用于服务顾客的的平均时间比例=l/m,27,假设:到达时间服从均值为1/l的指数分布.服务时间服从均值为1/m的指数分布.排队系统只有一个服务台.系统中期望的顾客数:L=r/(1r)=l/(ml)顾客在系统中的期望等待时间W=(1/l)L=1/(ml)顾客在队列中的期望等待时间Wq=W1/m=l/m(ml)在队列中的期望顾客数Lq=lWq=l2/m(ml)=r2/(1r),Model1(M/M/1),系统空闲的概率:系统中有n个顾客的概率:,28,TheM/M/1Model,系统中恰好有n个顾客的概率Pn=(1r)rn这样就有,P0=1rP1=(1r)rP2=(1r)r2:系统中等待时间超过t的概率P(Wt)=em(1r)tfort0队列中等待时间超过t的概率P(Wqt)=rem(1r)tfort0,29,电子表格:杜皮特公司的M/M/1模型,30,JohnPhixitts方法(ReduceMachines/Rep),新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq1/4工作日).JohnPhixitts的建议是:降低技术服务代表的有效因子以适应新的服务要求.Lowerr=l/m,untilWq1/4day,wherel=(指定给每一位技术服务代表的设备数)/50.,由于l的降低引起了Wq的降低,使得Wq1/4天的最大的l值是使得Wq等于1/4天的l值.找出这个值的最容易的方法是用Excel模板进行试算,尝试各种l值,直到找到一个使得Wq=0.25值.,31,JohnPhixitts方法(ReduceMachines/Rep),将l从3降到2需要将指派给每一位技术服务代表的设备数从容不迫50降低到100.100是难免满足Wq1/4天的最大值.在l=2,=4的条件下,每一位技术代表的有效因子将只有:,32,TheM/G/1Model,假设:到达间隔时间服从均值为1/l的指数分布.服务时间可能是任意形式的概率分布.不需要明确概率分布的具体形式,只需要估计这个分布的均值(1/m)和标准差(s).排队系统只有一个服务台.系统中有0个顾客(即系统空闲)的概率是:P0=1r队列中的期望等待的顾客数:Lq=l2s2+r2/2(1r)系统中的期望等待顾客数:L=Lq+r队列中的期望等待时间:Wq=Lq/l系统中的期望等待时间:W=Wq+1/m,33,M/G/1模型不同服务时间分布的s和Lq值,34,将M/G/1模型应用于工程副总裁提出的建议(NewEquipment),新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq1/4工作日).VicePresidentforEngineering建议技术服务代表提供新式的设备以大大降低需要较长时间的修理工作.这样做会使平均维修时间有所降低,也会大大降低维修时间的波动.在获得了更多的信息并进一步分析之后,对服务时间分布作出了如下估计:均值从1/4天降到1/5天.标准差从1/4降到1/10天.,35,将M/G/1模型应用于工程副总裁提出的建议(NewEquipment),36,14.6一些多服务台排队模型M/M/s,假设:到达间隔时间服从均值为1/l的指数分布.服务时间服从均值1/m的指数分布.对于一个排队系统可以选择任意数量的服务台(denotedbys).对于多服务台,有效因子的计算公式为r=l/sml=单位时间期望到达顾客sm=当所有的s个服务台都连续工作时,单位时间期望服务完成量.,37,ValuesofLfortheM/M/sModelforVariousValuesofs,38,CFO建议的方法(CombineIntoTeams),新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq1/4工作日).TheChiefFinancialOfficer建议将目前的单人技术服务表区域合并为一些较大的区域,由多位技术服务代表一起提供服务.每一个区域2个技术服务代表的情况:设备数=300(versus150before)平均到达率l=6(versusl=3before)平均服务率m=4(asbefore)服务台数s=2(versuss=1before)有效因子r=l/sm=0.75(asbefore),39,M/M/s模型应用于CFOs的建议(两个技术服务代理),40,应用于CFO的建议(三个技术服务代理),新的服务标准是:每一个服务开始前的平均等待时间降为2小时(i.e.,Wq1/4工作日).TheChiefFinancialOfficer建议将目前的单人技术服务表区域合并为一些较大的区域,由多位技术服务代表一起提供服务.每一个区域3个技术服务代表的情况:设备数=450(versus150before)平均到达率l=9(versusl=3before)平均服务率m=4(asbefore)服务台数s=3(versuss=1before)有效因子r=l/sm=0.75(asbefore),41,应用于CFO的建议(三个技术服务代理),42,杜皮特公司问题不同大小的区域对应Wq值的比较,从表中可以看到,在不改变有效因子的情况下Wq值随着技术服务代表(服务台)的数量的上升而急剧下降.s=2的Wq值比s=1的Wq值一半还要小,s=3的Wq值大约是s=1的1/4.,43,M/D/S模型,一些排队系统的服务时间不像M/M/S模型假设的那样波动那么大.在一些情况中,服务时间根本就没有波动或几乎没有波动).M/D/S模型就是为这种情况设计的.假设:除了现在所有服务时间都相同之外,其他与M/M/S模型相同.固定服务时间是1/.当为每一位顾客提供的服务完全相同时就会出现固定服务时间.当服务台是机器设备时,服务时间可能是完全没有波动的.如果服务者是人,为所有的顾客提供相同常规服务,固定服务时间的假设也可以作为合理的类似.当S=1时M/D/1模型的Lq值仅仅是M/M/1模型的一半.当S1时,两个多服务台模型之间也有类似的Lq值的差异.计算M/D/S模型的各种绩效测度的过程要比M/M/S模型复杂得多.,44,M/D/s中不同服务台数s对应的L值,45,M/Ek/2模型中不同形状参数k对应的L值,当服务时间有些波动,但不象指数分布那样剧烈时,M/Ek/S模型提供了一个介于M/M/S和M/D/S模型的相当好的中间类型.假设:除了服务时间服从均值为1/和形状参数为k(k=1,2,)的爱尔朗分布外,与M/M/S模型相同.,形状参数为k(k=1,2,)的爱尔朗分布的标准差为:,当远小于平均值时,取适当k(k=1,2,)值M/Ek/S模型可以提供比M/M/S模型准确的结果.,46,M/Ek/2模型中不同形状参数k对应的L值,47,14.7有优先权的排队模型,一般假设:有两类或更多类的顾客.每一类都具有一个优先级(priorityclass).优先级1的顾客将比优先级2的顾客优先接受服务.如果优先级2的顾客将具有优先于优先级3的顾客的权利.除了在较高优先级的顾客后面接受服务外,同一优先级内的顾客服从先到先服务的规则.因此,在一个优先级内接受服务的优先权是以已经在排队系统中花费的等待时间为基础的.两种类型的优先权无强制的优先规则(Nonpreemptivepriorities):当一个服务台开始为一个顾客服务时,服务必须在不被打断的条件下完成,即使在服务的过程中有更高优先级的顾客到来.然而,这个服务一完成,如果队列中有顾客,将根据优先权从中选出一个顾客进行服务.被选中的顾客是在具有最高优先级的顾客中等待时间最长的一个.强制优先规则(Preemptivepriorities):当一个具有更高优先权的顾客进入系统时,正在接受服务的最低优先级的顾客被挤出(退回到队列中).,48,强制优先规则排队模型,附加假设:强制优先级如上所述.对于优先级i(i=1,2,n),这个优先级顾客的到达间隔时间服从均值为1/li的指数分布.不管优先级是多少,所有服务时间服从均值为1/m,的指数分布.排队系统有一个服务台.服务台的有效因子为:r=(l1+l2+ln)/m,使用优先级的原因是降低高优先级顾客的等待时间.这样做的代价是增加低优先级顾客的等待时间.,49,无强制优先规则排队模型,附加假设:无强制优先级如上所述.对于优先级i(i=1,2,n),这个优先级顾客的到达间隔时间服从均值为1/li的指数分布.不管优先级是多少,所有服务时间服从均值为1/m,的指数分布.排队系统有一个服务台.服务台的有效因子r=(l1+l2+ln)/sm,50,将无强制优先规则排队模型应用于营销副总裁的建议(PriorityforNewCopiers),新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq1/4工作日).营销副总裁建议,给打印复印机高于其他设备的接受服务的优先权。这样建议的一个理由是打印复印机有很多的关键功能，如果这台设备的停机等待维修时间与其他设备一样长，其拥有者是无法忍受的。两个优先级的平均到达率：l1=1位顾客(打印复印机)每天(now)l2=2顾客(其他机器)每天(now)在这几年里这种打印机复印机的比例会逐渐上升到顶峰，在这种情况下，平均到达率会变为：l1=1.5顾客(打印机复印机)每天(later)l2=1.5顾客(其他机器)每天(later),51,无强制规则排队模型应用于杜皮特公司营销副总裁的建议(CurrentArrivalRates),使用优先级后，因为每一个技术服务代表的平均服务率不变，因此对其最好的估计仍然是每个工作日=4位顾客。在公司目前的单人技术服务代表负责区域的政策下，每一个区域的排队系统有一个服务台（S=1）。由于不管是现在还是以后1+2=3，有效因子的值始终是,52,无强制规则排队模型应用于杜皮特公司营销副总裁的建议(FutureArrivalRates),53,无强制优先规则应用于杜皮特公司问题时的期望等待时间,54,决策：采纳第四个建议,管理层的结论,55,14.8关于设计排队系统的一些启示,启示1:当设计一个单服务台排队系统时,注意相对较高的服务台有效因子(工作强度)将使得系统的绩效测度令人吃惊地低下.,56,启示2:降低服务时间的波动(不改变均值)可以大大改进单服务台排队系统的绩效(对于多服务台排队系统也是这样,特别是有较高有效因子的系统).,57,启示3:具有较高有效因子的多服务台排队系统能够比单服务台排队系统表现得更令人满意.例如,通过将分立的单服务台排队系统组合为一个多服务台排队系统产生的联合服务台大大改善了系统的绩效.联合服务台的影响:假设你有一定数量(以n表示)的符合M/M/1模型的单服务台排队系统.然后假设你将这n个系统组合为一个符合M/M/S模型的排队系统,服务台数为s=n.这种变化总会比通过将Wq除以n得到更多的改善.启示4:应用优先级选择顾客服务可以大大改善对高优先级顾客服务的绩效测度.,58,14.9服务台数量的经济分析,许多情况下,一个组织让顾客等待的结果可以称为等待成本(waitingcost).管理人员感兴趣的是最小化总成本.TC=单位时间期望总成本SC=单位时间期望服务成本WC=单位时间期望等待成本