排队论PPT文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,排队论,Queuing Systems,1,Where the Time Goes,美国人一生中平均要花费,-,6,年 吃,5,年 排队等待,4,年 做家务,2,年 回电话不成功,1,年 寻找放置不当的物品,8,个月 打开邮寄广告,6,个月 停在红灯前,2,排队系统的基本特征,离开,排队规则,到达过程,排队结构,服务过程,退出,离开,需求群体,3,商业服务系统,系统类型顾客服务台,理发店人理发师,银行出纳服务人出纳,ATM,机服务人,ATM,机,商店收银台人收银员,管道服务阻塞的管道管道工,电影院售票窗口人售票员,机场检票处人航空公司代理人,经纪人服务人股票经纪人,4,内部服务系统,系统类型顾客服务台,秘书服务雇员秘书,复印服务雇员复印机,计算机编程服务雇员程序员,大型计算机雇员计算机,急救中心雇员护士,传真服务雇员传真机,物料处理系统货物物料处理单元,维护系统设备维修工人,质检站物件质检员,5,运输服务系统,系统类型顾客服务台,公路收费站汽车收费员,卡车装货地卡车装货工人,港口卸货区轮船卸货工人,等待起飞的飞机飞机跑道,航班服务人飞机,出租车服务人出租车,电梯服务人电梯,消防部门火灾消防车,停车场汽车停车空间,急救车服务人急救车,6,到达过程,静态,动态,预约,定价,接受,/,拒绝,不加入排队,退出排队,恒定到达率,的随机到达,变动到达率,的随机到达,由设施控制,顾客控制,到达过程,7,到达过程的内容,顾客总体数或顾客源数,有限或无限,顾客的到达类型,单个或成批,顾客的到达间隔时间,间隔时间分布,8,排队结构,领号,多条队列,有限队长,有限队长,有限或,无限队长,快速通道,排队结构,单一队列,允许或,不允许移动,9,排队结构,-,例,多队多服务台,领号,3,4,8,2,6,10,12,11,5,7,9,单队多服务台,入口,10,排队规则,排队规则,静态,(FCFS,规则,),(LCFS,规则,)动态,基于排队,状况选择,即与特定顾,客特征选择,等待的,顾客数,协商,优先级,强占,顾客服务时间,(SPT,规则,),11,排队规则的内容,损失制系统,服务台被占用时新到的顾客将离开,等待制系统,FCFS,LCFS,RS,PR,混合制系统,损失制与等待制的混合,12,服务过程,服务过程,静态服务过程,动态服务过程,自我服务,机械速度,不同的服务率,开关服务通道,13,服务过程的内容,服务台数量,单个或多个,每次服务顾客的数量,单个或成批,服务顾客的时间分布,时间分布,14,Multiple Servers,Single Queue,15,Multiple Servers,Multiple Queues,16,常用的记号,n ,系统中的顾客数,平均到达率，即单位时间内平均到达的顾客数,平均服务率，即单位时间内服务完毕的顾客数,S,n,(t),时刻,t,系统中有,n,个顾客,P,n,(t),时刻,t,系统状态,S,n,(t),的概率,C ,服务台的个数,M ,顾客相继到达的时间间隔服从负指数分布,D ,顾客相继到达的时间间隔服从定长分布,E,k,顾客相继到达的时间间隔服从,k,阶,Erlang,分布,17,排队系统的符号表示,一个排队系统的特征可以用六个参数表示，形式为：,A,B,C,：,d,e,f,其中,A,顾客到达的概率分布，可取,M,、,D,、,E,k,等；,B,服务时间的概率分布，可取,M,、,D,、,E,k,等；,C,服务台个数，取正整数；,d,排队系统的最大容量，可取正整数或,；,e,顾客源的最大容量，可取正整数或,；,f,排队规则，可取,FCFS,、,LCFS,等。,18,M/M/1,：,/,/FCFS,表示：,顾客到达的时间间隔是负指数分布,服务时间是负指数分布,一个服务台,排队系统和顾客源的容量都是无限,实行先到先服务的一个服务系统,19,顾客到达和服务的时间分布,20,Poisson,流（,Poisson,过程）,定义,满足以下四个条件的输入流称为,Poisson,流（,Poisson,过程）,1,、平稳性：,在时间区间,t,t+,t),内到达,k,个顾客的概率与,t,无关，只与,t,有关。记为,p,k,(,t,）。,2,、无后效性：,不相交的时间区间内到达的顾客数互相独立。,3,、普通性：,设在,t,t+,t,）内到达多于一个顾客的概率为,q(,t,），则,q(,t)=o(,t),即,4,、有限性：,任意有限个区间内到达有限个顾客的概率等于一。即,21,Poisson,流与,Poisson,分布,定理 对于一个参数为,的,Poisson,流，在,0,，,t,内到达,k,个顾客的概率为,即服从以,为参数的,Poisson,分布。,l,l,l,=1,=3,=7,P,k,(1),x,.4,.3,.2,.1,0,22,Poisson,流与负指数分布之间的关系,定理,在排队系统中，如果单位时间内顾客到达数服从以,为参数的,Poisson,分布，则顾客相继到达的时间间隔服从以,为参数的负指数分布。,l,=,0,.,4,1/,为平均到达间隔时间,23,k,阶,Erlang,分布,定理 设,v,1,，,v,2,，,，,v,k,是,k,个互相独立的，具有相同参数,的负指数分布随机变量，则随机变量,S=v,1,+v,2,+v,k,服从,k,阶,Erlang,分布，,S,的密度函数为,24,系统绩效度量,系统总的平均顾客数,L,平均等待顾客个数,L,q,包括服务的平均等待时间,W,平均顾客等待时间,W,q,系统利用率,r,25,基本排队模型,M/M/1:,/,/FCFS,顾客到达的时间间隔是负指数分布,服务时间是负指数分布,一个服务台,排队系统和顾客源的容量都是无限,实行先到先服务的一个服务系统,26,M/M/1:,/,/FCFS,的分析,假设,在,t+,t,时刻系统中顾客数为,n,的概率,P,n,(t+,t),S,n,S,n,S,n+1,S,n-1,S,n,P,n,(t),P,n-1,(t),P,n+1,(t),P,n,(t),t,时刻,t+,t,时刻,无到达，无离开,无到达，离开一个,到达一个，无离开,到达一个，离开一个,27,28,系统的过渡状态与稳定状态,过渡,稳定,29,稳定状态下的状态概率,30,得到,令,称,为服务强度，则,得,31,M/M/1:,/,/FCFS,的状态转移分析,0,1,2,n-1,n,n+1,32,例,高速公路入口收费处设有一个收费通道，汽车到达服从,Poisson,分布，平均到达速率为,100,辆小时，收费时间服从负指数分布，平均收费时间为,15,秒辆。求,1,、收费处空闲的概率；,2,、收费处忙的概率；,3,、系统中分别有,1,，,2,，,3,辆车的概率。,表示单位时间能被服务完成的顾客数，称为平均服务率，而,1/u,表示一个顾客的平均服务时间,注：对于泊松流,表示单位时间平均到达的顾客数,所以,1/,就表示相继顾客到达平均间隔时间,.,33,解,根据题意,=100,辆,/,小时,1/,=15,秒,=1/240,（小时,/,辆）,即,240,（辆,/,小时）。,因此，,=,/,=100/240=5/12,。,系统空闲的概率为：,P,0,=1-,=1-(5/12)=7/12=0.583,系统忙的概率为：,1-P,0,=1-(1-,)=,=5/12=0.417,系统中有,1,辆车的概率为：,P,1,=,(1-,)=0.4170.583=0.243,系统中有,2,辆车的概率为：,P,2,=,2,(1-,)=0.417,2,0.583=0.101,系统中有,3,辆车的概率为：,P,3,=,3,(1-,)=0.417,3,0.583=0.0421,34,Little,公式,系统总的平均顾客数,L,平均等待顾客个数,L,q,包括服务的平均等待时间,W,平均顾客等待时间,W,q,系统利用率,r,表示单位时间平均到达的顾客数,表示单位时间能被服务完成的顾客数,L,：,平均队长,L,q,：平均排队长,35,M/M/1:,/,/FCFS,的系统指标,系统中的平均顾客数,L,队列中的平均顾客数,L,q,36,顾客在系统中的平均逗留时间,W,顾客在队列中的平均逗留时间,Wq,37,例,高速公路入口收费处设有一个收费通道，汽车到达服从,Poisson,分布，平均到达速率为,200,辆,/,小时，收费时间服从负指数分布，平均收费时间为,15,秒,/,辆。求,L,、,Lq,、,W,和,Wq38,解,根据题意，,=200,辆,/,小时，,=240,辆,/,小时，,=,/,=5/6,。,39,有限队列模型,M/M/1:N/,/FCFS,当队列的容量从无限值变为有限值,N,时，,M/M/1:,/,/FCFS,就转化成为,M/M/1:N/,/FCFS,40,系统的状态转移图,0,1,2,n-1,n,41,系统的状态概率平衡方程,对于状态,0,：,P,0,=,P,1,对于状态,k,：,P,k-1,+,P,k+1,=(,+,)P,k,0kN,时，到达的顾客就被拒绝。设顾客到达的速率为,，,m,每个服务台服务的速率为,，,=,/c,。由于系统不会无限止地接纳顾客，对,不必加以限制。,69,状态转移图与状态转移方程,对状态,0:P,0,=P,1,对状态,1:P,0,+2P,2,=(+)P,1,对状态,c,：,P,c-1,+cP,c+1,=(+c)P,c,对状态,N,P,N-1,=c,P,N,0,1,c,N,70,状态概率,71,运行指标,72,例,某旅馆有,8,个单人房间，旅客到达服从,Poisson,流，平均速率为,6,人天，旅客平均逗留时间为,2,天，求：,(1),每天客房平均占用数；,(2),旅馆客满的概率。,73,解,旅馆,8,个房间全满的概率为,0.423,平均占用客房数为,6.9,间。客房占用率为,86.6%,74,M/M/c:/m/FCFS,模型,顾客到达,修理速率,发生故障等待修理的机器,修理速率,修理速率,正在修理的机器,到达速率,(m-n),修理速率,c,运行的机器数,m-n,75,状态概率,其中,76,运行指标,效到达速率,e,为单位时间内出现故障的机器数，有,e=,(m-L),77,例,车间有,5,台机器，每台机器的故障率为,1,次小时，有,2,个修理工负责修理这,5,台机器，工作效率相同，为,4,台小时。求：,(1),等待修理的平均机器数；,(2),等待修理及正在修理的平均机器数；,(3),每小时发生故障的平均机器数；,(4),平均等待修理的时间；,(5),平均停工时间。,78,解,可以计算得到（算式略）：,P,1,=0.394,，,P,2,=0.197,，,P,3,=0.074,，,P,4,=0.018,，,P,5,=0.002,79,由此，计算系统的各项运行指标如下：,80,排队系统的优化,一般排队系统的总费用构成：,总费用,=,服务能力费,+,顾客损失费,最佳服务能力,服务能力,顾客损失费,服务能力费,总费用,费用,81,M/M/1:/FCFS,模型的,单位时间总费用,单位时间服务成本,单位顾客停留单位时间损失成本,82,对,u,求解最优值（驻点）,83,M/M/c:/FCFS,模型的,c,因为,c,只取整数，,z(c),不是连续函数，故不能用经典的微分法，下面采用边际分析方法。根据,z(c,*,),应为最小的特点,，,84,85,习题,1,：假定有一混合制排队系统,M/M/1/K,，其中,K=3,，顾客的到达率为每,小时,3.6,人，其到达间隔服从,Poisson,过程，系统服务一个顾客收费,2,元。又设系统的服务强度,（,=1/,T,T,为服务时间）服从负指数分布，其服务成本为每小时,0.5,元。,求系统为每个顾客的最佳服务时间。（答案：,0.2238,小时）,习题,2,：某检验中心为各工厂服务，要求进行检验的工厂（顾客）的到来服从,Poisson,流，平均到达率为,=48,（次,/,天）；每天来检验由于停工等原因损失,6,元；服务（检验）时间服从负指数分布，平均服务率为,=25,（次,/,天）；每设置一个检验员的服务成本为,4,元,/,天，其它条件均适合,M/M/s/,系统。,问应设几个检验员可使总费用的平均值最少？,86,电话中心,美国共有35万多个电话中心。,对电话中心的投资已达到250亿美元，年增长率为20%。,在美国所有的客户与企业相互交往中，有70%发生在电话中心。,电话中心雇佣了超过3%的美国劳动力（150万人）,87,电话中心,实例：,美国一个业绩突出的销售电话中心主要从事以下业务：,每天平均处理15,000个电话。,每个电话的平均持续时间为4分钟，但不同电话的持续时间有巨大的差别。,雇员使用率非常高（超过90%）。,几乎没有忙音。,平均等待时间几秒钟。,放弃率极低。,88,电话中心：超越传统的排队,假设一个电话中心的顾客光顾率为每小时1599人，平均服务时间为3.,75,分钟，,N100,个服务员,。,使用率为,99.9%；,平均等待时间1小时,如果,N101，,那么平均等待时间3分钟,如果,N105（95%）,使用率，平均等待时间23秒；大约50%的人等待时间少于2秒钟。,89,电话中心：超越传统的排队,同一个电话中心，现在假设顾客的平均耐心时间为5分钟。,N=100,时的使用率为 96%，有 50%的人会立即得到服务；平均等待时间为 11秒；放弃率为4%。,N=104,时的使用率为 93.5%，有70%的人会立即得到服务；平均等待时间为5秒；放弃率为1.8%。,90,优化电话中心的人员配置,为提供可接受的服务质量，应该安排多少名雇员？,假设某个电话中心制定的服务质量标准为：需要等待的顾客不能超过 1%。那么意味着顾客时间的估价与雇员时间的估价比值是多少？,91,