1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,排队论,Queuing Systems,1,Where the Time Goes,美国人一生中平均要花费,-,6,年 吃,5,年 排队等待,4,年 做家务,2,年 回电话不成功,1,年 寻找放置不当的物品,8,个月 打开邮寄广告,6,个月 停在红灯前,2,排队系统的基本特征,离开,排队规则,到达过程,排队结构,服务过程,退出,离开,需求群体,3,商业服务系统,系统类型顾客服务台,理发店人理发师,银行出纳服务人出纳,AT
2、M,机服务人,ATM,机,商店收银台人收银员,管道服务阻塞的管道管道工,电影院售票窗口人售票员,机场检票处人航空公司代理人,经纪人服务人股票经纪人,4,内部服务系统,系统类型顾客服务台,秘书服务雇员秘书,复印服务雇员复印机,计算机编程服务雇员程序员,大型计算机雇员计算机,急救中心雇员护士,传真服务雇员传真机,物料处理系统货物物料处理单元,维护系统设备维修工人,质检站物件质检员,5,运输服务系统,系统类型顾客服务台,公路收费站汽车收费员,卡车装货地卡车装货工人,港口卸货区轮船卸货工人,等待起飞的飞机飞机跑道,航班服务人飞机,出租车服务人出租车,电梯服务人电梯,消防部门火灾消防车,停车场汽车停车空
3、间,急救车服务人急救车,6,到达过程,静态,动态,预约,定价,接受,/,拒绝,不加入排队,退出排队,恒定到达率,的随机到达,变动到达率,的随机到达,由设施控制,顾客控制,到达过程,7,到达过程的内容,顾客总体数或顾客源数,有限或无限,顾客的到达类型,单个或成批,顾客的到达间隔时间,间隔时间分布,8,排队结构,领号,多条队列,有限队长,有限队长,有限或,无限队长,快速通道,排队结构,单一队列,允许或,不允许移动,9,排队结构,-,例,多队多服务台,领号,3,4,8,2,6,10,12,11,5,7,9,单队多服务台,入口,10,排队规则,排队规则,静态,(FCFS,规则,),(LCFS,规则,)
4、动态,基于排队,状况选择,即与特定顾,客特征选择,等待的,顾客数,协商,优先级,强占,顾客服务时间,(SPT,规则,),11,排队规则的内容,损失制系统,服务台被占用时新到的顾客将离开,等待制系统,FCFS,LCFS,RS,PR,混合制系统,损失制与等待制的混合,12,服务过程,服务过程,静态服务过程,动态服务过程,自我服务,机械速度,不同的服务率,开关服务通道,13,服务过程的内容,服务台数量,单个或多个,每次服务顾客的数量,单个或成批,服务顾客的时间分布,时间分布,14,Multiple Servers,Single Queue,15,Multiple Servers,Multipl
5、e 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,服务时间
6、的概率分布,可取,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),内到达,
7、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,流与负
8、指数分布之间的关系,定理,在排队系统中,如果单位时间内顾客到达数服从以,为参数的,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,基本排队模型,
9、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,得到,令,称,为服务强
10、度,则,得,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
11、/,=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,公式,系统总的
12、平均顾客数,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,和,Wq
13、38,解,根据题意,,=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,。由于系统不会无限止地接纳顾客,对,不必加以限制。,6
14、9,状态转移图与状态转移方程,对状态,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,模型,顾客到达,修理
15、速率,发生故障等待修理的机器,修理速率,修理速率,正在修理的机器,到达速率,(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,
16、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,*,),应为最小的特点,,,
17、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,(次,/,天);每设置一
18、个检验员的服务成本为,4,元,/,天,其它条件均适合,M/M/s/,系统。,问应设几个检验员可使总费用的平均值最少?,86,电话中心,美国共有35万多个电话中心。,对电话中心的投资已达到250亿美元,年增长率为20%。,在美国所有的客户与企业相互交往中,有70%发生在电话中心。,电话中心雇佣了超过3%的美国劳动力(150万人),87,电话中心,实例:,美国一个业绩突出的销售电话中心主要从事以下业务:,每天平均处理15,000个电话。,每个电话的平均持续时间为4分钟,但不同电话的持续时间有巨大的差别。,雇员使用率非常高(超过90%)。,几乎没有忙音。,平均等待时间几秒钟。,放弃率极低。,88,电
19、话中心:超越传统的排队,假设一个电话中心的顾客光顾率为每小时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,