第十四章排队模型与仿真

第十四章排队模型与仿真1第1页，共61页，2023年，2月20日，星期二SessionTopicsSystemCharacteristics系统特征MeasuresofSystemPerformance系统绩效度量SomeQueuingModels一些排队模型ApplicationofQueuingTheory排队论的应用IntroductiontoSimulation仿真介绍TypesofSimulation仿真类型SimulationSteps仿真步骤ApplicationsofSimulation仿真应用第2页，共61页，2023年，2月20日，星期二QueuingTheory

排队理论哪儿有排队现象呢?机器等待修理电话忙音银行排队邮局排队餐厅排队商场排队

第3页，共61页，2023年，2月20日，星期二14.1排队模型的要素基本排队系统:顾客:一个挨着一个的到来,接受某种服务.队列:等待的服务的顾客服务台:提供服务第4页，共61页，2023年，2月20日，星期二一个例子:HerrCutter’sBarberShop赫尔卡特先生是一个德国理发师,他经营着一家单人理发店.赫尔卡特先生每天早上8:00开始营业.下表给出了这个排队系统的的有关信息.CustomerTimeof

ArrivalHaircut

BeginsDuration

ofHaircutHaircut

Ends18:038:0317minutes8:2028:158:2021minutes8:4138:258:4119minutes9:0048:309:0015minutes9:1559:059:1520minutes9:3569:43———第5页，共61页，2023年，2月20日，星期二连续两个顾客到达排队系统的时间间隔称为到达间隔时间(interarrivaltimes).到达时间的巨大差异对于排队系统来说是很正常的.通常不可能预测要过多长时间下一个顾客才会到来.单位时间里顾客到达的期望数称为平均到达率l(meanarrivalrate). l=顾客到达排队系统的平均到达率到达时间间隔的平均值是: 1/l=到达间隔时间的期望

大多数的排队模型假设到达间隔时间的概率分布的形式是指数分布.到达第6页，共61页，2023年，2月20日，星期二到达间隔时间的指数分布注意在曲线的最高点时间非常小,随着时间变长曲线以“指数形式”下降.这表明低于均值的较小的到达间隔时间有大的可能性.而分布向右伸展很长表明比均值大得多的到达间隔时间出现的概率很小.对于大多数的排队系统,服务台无法控制顾客何时到达.在这种情况下,顾客总的来说是随机到达的.随机到达意味着到达时间是完全无法凭感觉预测的,下一分钟有顾客到达的概率和其他分钟相同(不多也不少).从上一个到达发生经过了多长时间并不重要.唯一符合随机到达的到达间隔时间分布是指数分布.下一分钟到达的概率完全不受上一次到达的影响的事实称为无记忆性(lack-of-memoryproperty).指数分布具有无记忆性.第7页，共61页，2023年，2月20日，星期二队列中的顾客数(numberofcustomersinthequeue)是等候服务的顾客数量.系统中的顾客数(numberofcustomersinthesystem)是队列中的顾客数加上正在接受服务的顾客数量.队列容量(queuecapacity)是队列所能容纳顾客的最大数量..无限队列(infinitequeue)是为了应用的方便,可以容纳无限数量的顾客的队列..当容量很小,需要将其考虑在内时,这个队列就称为有限队列这个队列(finitequeue).队列第8页，共61页，2023年，2月20日，星期二先到先服务(FCFS):多种优先权:队列规则(queuediscipline)指:选择队列中的成员接受服务有顺序

.Themostcommonisfirst-come,first-served(FCFS).Otherpossibilitiesincluderandomselection,somepriorityprocedure,orevenlast-come,first-served.第9页，共61页，2023年，2月20日，星期二服务对于一个基本的排队系统,每一个顾客单独接受一个服务者提供的服务.拥有多于一个服务台的系统称为多服务台系统,单服务台系统只有一个服务台.单服务台多服务台第10页，共61页，2023年，2月20日，星期二当一个顾客接受服务时,从服务开始到结束经过的时间称为服务时间(servicetime).每一位置顾客的服务时间是不同的.然而基本的排队模型假设服务时间是一个特定的概率分布,与哪一个服务台正在提供的服务无关.服务时间分布的平均值表示为:

1/m=期望服务时间

m

是平均服务率(meanservicerate).

m=一个连续工作的服务台单位时间的服务量的期望值第11页，共61页，2023年，2月20日，星期二一些服务时间的分布指数分布最应用最多的服务时间的概率分布.比其他分布分析容易得多.尽管这个分布在大多数情况下非常适合于到达间隔时间的分布,但对于服务时间实际是却不全是这样.当服务的提供是随机的,指数分布是一个相当不错的近似.Standarddeviation:s=Mean固定服务时间(ConstantServiceTimes)当排队系统包含一系列固定顺序的操作,对于每一位顾客要花费大约相同的时间时,固定服务时间是一个很好的近似.Standarddeviation:s=0.爱尔良分布(ErlangDistribution)波动量介于指数分布和固定分布之间的一个分布.有一个分布参数

k,称为形状参数,它决定了标准差.Inparticular,s=mean/(k)第12页，共61页，2023年，2月20日，星期二服务时间分布标准差与均值的关系DistributionStandardDeviationExponentialmeanDegenerate(constant)0Erlang,anyk(1/k)(Mean)Erlang,k=2(1/2)(Mean)Erlang,k=4(1/2)(Mean)Erlang,k=8(1/22)(Mean)Erlang,k=16(1/4)(Mean)第13页，共61页，2023年，2月20日，星期二排队模型的符号表示排队模型通常用下列形式来表示:

服务时间的分布

—/—/—

服务台数目

到达间隔时间的分布用于表示可能分布的符号是:

M=Exponentialdistribution(Markovian)

D=Degeneratedistribution(constanttimes)

Ek=Erlangdistribution(shapeparameter=k)

GI=Generalindependentinterarrival-timedistribution(anydistribution)

G=Generalservice-timedistribution(anyarbitrarydistribution)第14页，共61页，2023年，2月20日，星期二SomeModels

一些模型单服务台指数服务时间(M/M/1)单服务台一般服务时间(M/G/1)

多服务台指数服务时间(M/M/s)A/B/s到达分布服务台数服务分布第15页，共61页，2023年，2月20日，星期二模型假设的总结1、到达间隔时间是独立的，服从一种特定的概率分布。2、所有到达的顾客都进入排队系统，并等待直到服务结束。3、排队系统有一个无限队列，因此队列将可以容纳无限量的顾客。4、顾客服务优先规划是先到先服务。5、排队系统拥有特定数量级的服务台，每一个服务台能够为任意一位置顾客提供服务。6、每一位顾客由一个服务台单独提供服务。7、服务时间是独立的，服从特定的概率分布。第16页，共61页，2023年，2月20日，星期二排队系统的一些例子系统类型 顾客 服务台理发店 人 理发师银行出纳服务 人 出纳ATM机服务 人 ATM机商店收银台 人 收银员管道服务 阻塞的管道 管道工电影院售票窗口 人 售票员机场检票处 人 航空公司代理人经纪人服务 人 股票经纪人CommercialServiceSystems

商业服务系统第17页，共61页，2023年，2月20日，星期二系统类型 顾客 服务台秘书服务 雇员 秘书复印服务 雇员 复印机计算机编程服务 雇员 程序员大型计算机 雇员 计算机急救中心 雇员 护士传真服务 雇员 传真机物料处理系统 货物 物料处理单元维护系统 设备 维修工人质检站 物件 质检员InternalServiceSystem

内部服务系统第18页，共61页，2023年，2月20日，星期二系统类型 顾客 服务台公路收费站 汽车 收费员卡车装货地 卡车 装货工人港口卸货区 轮船 卸货工人等待起飞的飞机 飞机 跑道航班服务 人 飞机出租车服务 人 出租车电梯服务 人 电梯消防部门 火灾 消防车停车场 汽车 停车空间急救车服务 人 急救车TransportationServiceSystem

运输服务系统第19页，共61页，2023年，2月20日，星期二14.3排队系统的绩效测度当顾客是提供服务的组织(内部服务系统)的内部顾客时,第一个测度比较重要.在这种情况下,让顾客等待会损失生产力,损失的生产力直接与等待的顾客顾客数量有关.

商业服务系统(外部顾客接受商业组织的服务)会认为第二个测度更加重要.对于这样的排队系统,一个重要的目标是保持顾客满意.比起已经有多少顾客在等待,顾客更关心他们会等多久.使顾客等待时间过长会导致未来业务利润损失.

平均顾客等待个数

平均顾客等待时间系统利用率第20页，共61页，2023年，2月20日，星期二定义绩效测度

λ =顾客到达率

µ =服务率(1/µ=平均服务时间) Lq =队列中的顾客数

L =系统中平均顾客数(包括正在接受服务的顾客)

Wq =队列中平均等待时间

W =包括服务的平均等待时间

Pn =有

n

个顾客在系统的概率 ρ =系统利用率这些定义假设排队系统处于平衡状态.考虑整个排队系统(L和W)或仅仅是队列(Lq和Wq),这取决于排队系统本身.对于医院的急诊室和消防部门,队列可能更重要.对于一个内部服务系统,整个排队系统更加重要.第21页，共61页，2023年，2月20日，星期二系统利用率系统中平均顾客数队列中平均等待时间包括服务的平均等待时间BasicRelationships基本关系第22页，共61页，2023年，2月20日，星期二14.4案例研究:杜皮特公司问题杜皮特公司(DupitCorporation)在办公复印机市场上长期牌领导地位.杜皮特公司有一个服务部门,负责为公司的顾客提供高质量的服务支持,在需要的时候维修公司的设备.这项工作由公司的技术服务代表在顾客所在地进行.Currentpolicy:

每一位技术代表的地域应当有足够的设备,合得技服务代表在大约75%的时间里处于维修工作状态(或在到维修地点的路上)..当连续工作时,每一个技术服务代表应当能够平均一天修4台设备(每台设备平均需要2小时,包括先进时间)为了使顾客的等待时间最短.每一个工作日平均要接到3个维修电话.公司的设备平均50个工作日需要一次维修,因此要为每一个技术服务代表负责的区域指定大约150台设备.提出的新的服务标准:在技术服务代表开始前往顾客所在地修理设备之前,顾客的平均等待时间不应超过2小时.第23页，共61页，2023年，2月20日，星期二解决问题可供选择的方案ApproachSuggestedbyJohnPhixitt:个性目前的政策,降低期望技术服务代表进行维修工作的时间百分率.这涉及到简单地降低分配给每一个技术服务代表的设备的数量以及增加更多的技术服务代表.这个方法可以使得过去为公司服务得很好的服务部门的工作方式能够延续下去,同时还可以提高服务水平,满足市场上新的需求.ApproachSuggestedbytheVicePresidentforEngineering:为技术服务代表提供新的装备,这样可以大大降低所需的较长时间的修理时间尽管这很昂贵,但显著地缩短平均维修时间.ApproachSuggestedbytheChiefFinancialOfficer:将现在的单个技术服务代表负责区域转变为较大的区域.由多个技术服务代表提供服务.在忙的时候通过团队支持可以大缩短平均维修等待时间而不需要雇用新的技术服务代表.ApproachSuggestedbytheVicePresidentforMarketing:授予这种新的打印复印机的所有者比其他公司的顾客优先接受服务的权利.第24页，共61页，2023年，2月20日，星期二每一个技术服务代表的排队系统Thecustomers:需要修理的设备.Customerarrivals:打给每一个技术服务代表要求修理的电话.Thequeue:顾客所在地等待修理的所有设备.Theserver:技术服务代表.Servicetime:

技术服务代表花在一台设备上的总时间,包括到等待维修设备所在地的行进时间和维修时间.(因此,当技术服务代表开始前往设备所在地时,这台设备就可以视为已经离开队列进入服务系统了)第25页，共61页，2023年，2月20日，星期二单服务台排队模型

l =到达排队系统的顾客的平均到达率

=单位时间期望到达顾客数

1/l =期望到达间隔时间

m =平均服务率

=单位时间期望服务完成的顾客数

1/m =期望服务时间

r =有效因子(利用率)

=它代表了一个服务台用于服务顾客的的平均时间比例

=l/m第26页，共61页，2023年，2月20日，星期二假设:到达时间服从均值为1/l的指数分布.服务时间服从均值为1/m的指数分布.排队系统只有一个服务台.系统中期望的顾客数: L=r/(1–

r)=l/(m

–l)顾客在系统中的期望等待时间 W=(1/l)L=1/(m–l)顾客在队列中的期望等待时间

Wq

=W–1/m=l/[m(m–l)]在队列中的期望顾客数

Lq

=lWq=l2/[m(m–l)]=r2/(1–r)Model1(M/M/1)系统空闲的概率:系统中有n个顾客的概率:第27页，共61页，2023年，2月20日，星期二TheM/M/1Model系统中恰好有n个顾客的概率

Pn=(1–r)rn

这样就有,

P0=1–r

P1=(1–r)r

P2=(1–r)r2

:

:系统中等待时间超过t的概率 P(W>t)=e–m(1–r)tfort≥0队列中等待时间超过t的概率

P(Wq>t)=re–m(1–r)tfort≥0第28页，共61页，2023年，2月20日，星期二电子表格:杜皮特公司的M/M/1模型第29页，共61页，2023年，2月20日，星期二JohnPhixitt’s方法(ReduceMachines/Rep)新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq

≤1/4

工作日).JohnPhixitt’s的建议是:降低技术服务代表的有效因子以适应新的服务要求.

Lowerr=l/m,untilWq

≤1/4day,

where

l=(指定给每一位技术服务代表的设备数)/50.由于l的降低引起了Wq的降低,使得Wq

≤1/4天的最大的l值是使得Wq等于1/4天的l值.找出这个值的最容易的方法是用Excel模板进行试算,尝试各种l值,直到找到一个使得Wq=0.25值.第30页，共61页，2023年，2月20日，星期二JohnPhixitt’s方法(ReduceMachines/Rep)将l从3降到2需要将指派给每一位技术服务代表的设备数从容不迫50降低到100.100是难免满足Wq

≤1/4天的最大值.在l=2,μ=4的条件下,每一位技术代表的有效因子将只有:第31页，共61页，2023年，2月20日，星期二TheM/G/1Model假设:到达间隔时间服从均值为1/l的指数分布..服务时间可能是任意形式的概率分布..不需要明确概率分布的具体形式,只需要估计这个分布的均值(1/m)和标准差(s).排队系统只有一个服务台.系统中有0个顾客(即系统空闲)的概率是: P0=1–r队列中的期望等待的顾客数:

Lq

=[l2s2

+r2]/[2(1–r)]系统中的期望等待顾客数: L=Lq+r队列中的期望等待时间:

Wq

=Lq

/l系统中的期望等待时间: W=Wq

+1/m第32页，共61页，2023年，2月20日，星期二M/G/1模型不同服务时间分布的s

和Lq

值DistributionMeansModelLqExponential1/m1/mM/M/1r2/(1–r)Degenerate(constant)1/m0M/D/1(1/2)[r2/(1–r)]Erlang,withshapeparameterk1/m(1/k)(1/m)M/Ek/1(k+1)/(2k)[r2/(1–r)]第33页，共61页，2023年，2月20日，星期二将M/G/1模型应用于工程副总裁提出的建议(NewEquipment)新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq

≤1/4

工作日).VicePresidentforEngineering建议技术服务代表提供新式的设备以大大降低需要较长时间的修理工作.这样做会使平均维修时间有所降低,也会大大降低维修时间的波动.在获得了更多的信息并进一步分析之后,对服务时间分布作出了如下估计:均值从1/4天降到

1/5

天.标准差从1/4

降到

1/10

天.第34页，共61页，2023年，2月20日，星期二将M/G/1模型应用于工程副总裁提出的建议(NewEquipment)第35页，共61页，2023年，2月20日，星期二14.6一些多服务台排队模型

M/M/s假设:到达间隔时间服从均值为1/l的指数分布.服务时间服从均值1/m的指数分布.对于一个排队系统可以选择任意数量的服务台(denotedbys).对于多服务台,有效因子的计算公式为

r=l/sm

l=单位时间期望到达顾客

sm=当所有的s个服务台都连续工作时,单位时间期望服务完成量.第36页，共61页，2023年，2月20日，星期二ValuesofLfortheM/M/sModelforVariousValuesofs第37页，共61页，2023年，2月20日，星期二CFO建议的方法(CombineIntoTeams)新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq

≤1/4

工作日).TheChiefFinancialOfficer建议将目前的单人技术服务表区域合并为一些较大的区域,由多位技术服务代表一起提供服务..每一个区域2个技术服务代表的情况:设备数=300(versus150before)平均到达率l=6 (versusl=3before)平均服务率m=4 (asbefore)服务台数s=2 (versuss=1before)有效因子r=l/sm=0.75 (asbefore)第38页，共61页，2023年，2月20日，星期二M/M/s

模型应用于CFO’s的建议

(两个技术服务代理)第39页，共61页，2023年，2月20日，星期二应用于CFO的建议(三个技术服务代理)新的服务标准是:每一个服务开始前的平均等待时间降为2小时(i.e.,Wq

≤1/4

工作日).TheChiefFinancialOfficer建议将目前的单人技术服务表区域合并为一些较大的区域,由多位技术服务代表一起提供服务..每一个区域3个技术服务代表的情况:设备数=450 (versus150before)平均到达率l=9 (versusl=3before)平均服务率m=4 (asbefore)服务台数s=3 (versuss=1before)有效因子r=l/sm=0.75 (asbefore)第40页，共61页，2023年，2月20日，星期二应用于CFO的建议(三个技术服务代理)第41页，共61页，2023年，2月20日，星期二杜皮特公司问题不同大小的区域对应Wq

值的比较技术服务代表数设备数lmsrWq11503410.750.75workday(6hours)23006420.750.321workday(2.57hours)34509430.750.189workday(1.51hours)从表中可以看到,在不改变有效因子的情况下Wq值随着技术服务代表(服务台)的数量的上升而急剧下降.s=2的Wq值比s=1的Wq值一半还要小,s=3的Wq值大约是s=1的1/4.第42页，共61页，2023年，2月20日，星期二M/D/S模型一些排队系统的服务时间不像M/M/S模型假设的那样波动那么大.在一些情况中,服务时间根本就没有波动或几乎没有波动).M/D/S模型就是为这种情况设计的.假设:除了现在所有服务时间都相同之外,其他与M/M/S模型相同.固定服务时间是1/μ.当为每一位顾客提供的服务完全相同时就会出现固定服务时间.当服务台是机器设备时,服务时间可能是完全没有波动的.如果服务者是人,为所有的顾客提供相同常规服务,固定服务时间的假设也可以作为合理的类似.当S=1时M/D/1模型的Lq值仅仅是M/M/1模型的一半.当S>1时,两个多服务台模型之间也有类似的Lq值的差异.计算M/D/S模型的各种绩效测度的过程要比M/M/S模型复杂得多.第43页，共61页，2023年，2月20日，星期二M/D/s

中不同服务台数s对应的L值第44页，共61页，2023年，2月20日，星期二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模型准确的结果.第45页，共61页，2023年，2月20日，星期二M/Ek/2模型中不同形状参数k对应的L值第46页，共61页，2023年，2月20日，星期二14.7有优先权的排队模型一般假设:有两类或更多类的顾客.每一类都具有一个优先级(priorityclass).优先级1的顾客将比优先级2的顾客优先接受服务.如果优先级2的顾客将具有优先于优先级3的顾客的权利.除了在较高优先级的顾客后面接受服务外,同一优先级内的顾客服从先到先服务的规则.因此,在一个优先级内接受服务的优先权是以已经在排队系统中花费的等待时间为基础的.

两种类型的优先权无强制的优先规则(Nonpreemptivepriorities):当一个服务台开始为一个顾客服务时,服务必须在不被打断的条件下完成,即使在服务的过程中有更高优先级的顾客到来.然而,这个服务一完成,如果队列中有顾客,将根据优先权从中选出一个顾客进行服务.被选中的顾客是在具有最高优先级的顾客中等待时间最长的一个.强制优先规则(Preemptivepriorities):当一个具有更高优先权的顾客进入系统时,正在接受服务的最低优先级的顾客被挤出(退回到队列中).第47页，共61页，2023年，2月20日，星期二强制优先规则排队模型附加假设:强制优先级如上所述.对于优先级i(i=1,2,…,n),这个优先级顾客的到达间隔时间服从均值为1/li的指数分布.不管优先级是多少,所有服务时间服从均值为1/m,的指数分布.排队系统有一个服务台.服务台的有效因子为:

r=(l1+l2+…+ln)/m使用优先级的原因是降低高优先级顾客的等待时间.这样做的代价是增加低优先级顾客的等待时间.第48页，共61页，2023年，2月20日，星期二无强制优先规则排队模型附加假设:无强制优先级如上所述.对于优先级i(i=1,2,…,n),这个优先级顾客的到达间隔时间服从均值为1/li的指数分布.不管优先级是多少,所有服务时间服从均值为1/m,的指数分布.排队系统有一个服务台.服务台的有效因子

r=(l1+l2+…+ln)/sm第49页，共61页，2023年，2月20日，星期二将无强制优先规则排队模型应用于营销副总裁的建议(PriorityforNewCopiers)新的服务标准是:每一个服务开始前的平均等待时间降为2小时.(i.e.,Wq

≤1/4

工作日).营销副总裁建议,给打印——复印机高于其他设备的接受服务的优先权。这样建议的一个理由是打印——复印机有很多的关键功能，如果这台设备的停机等待维修时间与其他设备一样长，其拥有者是无法忍受的。两个优先级的平均到达率：

l1=1位顾客(打印——复印机)每天 (now)

l2=2顾客(其他机器)每天 (now)在这几年里这种打印机——复印机的比例会逐渐上升到顶峰，在这种情况下，平均到达率会变为：

l1=1.5顾客(打印机——复印机)每天 (later)

l2=1.5顾客(其他机器)每天 (later)第50页，共61页，2023年，2月20日，星期二无强制规则排队模型应用于杜皮特公司营销副总裁的建议(CurrentArrivalRates)使用优先级后，因为每一个技术服务代表的平均服务率不变，因此对其最好的估计仍然是每个工作日μ=4位顾客。在公司目前的单人技术服务代表负责区域的政策下，每一个区域的排队系统有一个服务台（S=1）。由于不管是现在还是以后λ1+λ2=3，有效因子的值始终是第51页，共61页，2023年，2月20日，星期二无强制规则排队模型应用于杜皮特公司营销副总裁的建议(FutureArrivalRates)第52页，共61页，2023年，2月20日，星期二无强制优先规则应用于杜皮特公司问题时的期望等待时间sWhenl1l2mrWqforPrinterCopiersWq

forOtherMachines1Now1240.750.25workday(2hrs.)1workday(8hrs.)1Later1.51.540.750.3workday(2.4hrs.)1.2workday(9.6hrs.)2Now2440.750.107workday(0.86hr.)0.439workday(3.43hrs.)2Later3340.750.129workday(1.03hrs.)0.514workday(4.11hrs.)3Now3640.750.063workday(0.50hr.)0.252workday(2.02hrs.)3Later4.54.540.750.076workday(0.61hr.)0.303workday(2.42hrs.)第53页，共61页，2023年，2月20日，星期二决策：采纳第四个建议管理层的结论建议人建议增加的成本约翰保持单人负责区域，但是将每个区域指派的设备数从150减少到100每年3亿美元工程副总裁保持现在的单人负责区域一次性成本5亿美元首席财务官变为三人负责区域没有，除了较大区域的缺点营销副总裁变为两人负责区域，给打印——复印机维修优先权没有，除了较大区域的缺点第54页，共61页，2023年，2月20日，星期二14.8关于设计排队系统的一些启示启示1