管理运筹学排队论.ppt

1、运筹学排队论,Where the Time Goes,美国人一生中平均要花费-,6年 吃,5年 排队等待,4年 做家务,2年 回电话不成功,1年 寻找放置不当的物品,8个月 打开邮寄广告,6个月 停在红灯前,排队系统的基本特征,离开,排队规则,到达过程,排队结构,服务过程,退出,离开,需求群体,商业服务系统,系统类型顾客服务台 理发店人理发师 银行出纳服务人出纳 ATM机服务人ATM机 商店收银台人收银员 管道服务阻塞的管道管道工 电影院售票窗口人售票员 机场检票处人航空公司代理人 经纪人服务人股票经纪人,内部服务系统,系统类型顾客服务台 秘书服务雇员秘书 复印服务雇员复印机 计算机编程服务雇

2、员程序员 大型计算机雇员计算机 急救中心雇员护士 传真服务雇员传真机 物料处理系统货物物料处理单元 维护系统设备维修工人 质检站物件质检员,运输服务系统,系统类型顾客服务台 公路收费站汽车收费员 卡车装货地卡车装货工人 港口卸货区轮船卸货工人 等待起飞的飞机飞机跑道 航班服务人飞机 出租车服务人出租车 电梯服务人电梯 消防部门火灾消防车 停车场汽车停车空间 急救车服务人急救车,到达过程,到达过程的内容,顾客总体数或顾客源数 有限或无限 顾客的到达类型 单个或成批 顾客的到达间隔时间 间隔时间分布,排队结构,排队结构-例,排队规则,排队规则的内容,损失制系统 服务台被占用时新到的顾客将离开 等待

3、制系统 FCFS LCFS RS PR 混合制系统 损失制与等待制的混合,服务过程,服务过程,静态服务过程,动态服务过程,自我服务,机械速度,不同的服务率,开关服务通道,服务过程的内容,服务台数量 单个或多个 每次服务顾客的数量 单个或成批 服务顾客的时间分布 时间分布,常用的记号,n 系统中的顾客数 平均到达率，即单位时间内平均到达的顾客数 平均服务率，即单位时间内服务完毕的顾客数 Sn(t) 时刻t系统中有n个顾客 Pn(t) 时刻t系统状态Sn(t) 的概率 C 服务台的个数 M 顾客相继到达的时间间隔服从负指数分布 D 顾客相继到达的时间间隔服从定长分布 Ek 顾客相继到达的时间间隔服

4、从k阶Erlang分布,排队系统的符号表示,一个排队系统的特征可以用六个参数表示，形式为： ABC：def,其中 A 顾客到达的概率分布，可取M、D、Ek等； B 服务时间的概率分布，可取M、D、Ek等； C 服务台个数，取正整数； d 排队系统的最大容量，可取正整数或； e 顾客源的最大容量，可取正整数或； f 排队规则，可取FCFS、LCFS等。,M/M/1：/FCFS 表示： 顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统,顾客到达和服务的时间分布,Poisson流（Poisson过程）,定义 满足以下四个条

5、件的输入流称为Poisson流（Poisson过程） 1、平稳性：在时间区间t, t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。 2、无后效性：不相交的时间区间内到达的顾客数互相独立。 3、普通性：设在t, t+t）内到达多于一个顾客的概率为q(t），则 q(t)=o(t) 即 4、有限性：任意有限个区间内到达有限个顾客的概率等于一。即,Poisson流与Poisson分布,定理 对于一个参数为的Poisson流，在0，t内到达k个顾客的概率为 即服从以为参数的Poisson分布。,Poisson流与负指数分布之间的关系,定理 在排队系统中，如果单位时间内顾客到达数服从以为

6、参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。,l,=,0,.,4,1/为平均到达间隔时间,k阶Erlang分布,定理 设v1，v2，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量 S=v1+v2+vk 服从k阶Erlang分布，S的密度函数为,系统绩效度量,系统总的平均顾客数L 平均等待顾客个数Lq 包括服务的平均等待时间W 平均顾客等待时间Wq,基本排队模型 M/M/1:/FCFS,顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统,M/M/1:/FCFS的分析,假

7、设在t+t时刻系统中顾客数为n的概率Pn(t+t),Sn,Sn,Sn+1,Sn-1,Sn,Pn(t),Pn-1(t),Pn+1(t),Pn(t),t时刻,t +t时刻,无到达，无离开,无到达，离开一个,到达一个，无离开,到达一个，离开一个,系统的过渡状态与稳定状态,稳定状态下的状态概率,得到,令 称为服务强度，则,得,M/M/1:/FCFS的状态转移分析,例,高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆小时，收费时间服从负指数分布，平均收费时间为15秒辆。求 1、收费处空闲的概率； 2、收费处忙的概率； 3、系统中分别有1，2，3辆车的概率。,解,

8、根据题意, =100辆/小时,1/=15秒=1/240（小时/辆）,即240（辆/小时）。 因此，=/=100/240=5/12。 系统空闲的概率为： P0=1-=1-(5/12)=7/12=0.583 系统忙的概率为： 1-P0=1-(1-)=5/12=0.417 系统中有1辆车的概率为： P1=(1-)=0.4170.583=0.243 系统中有2辆车的概率为： P2=2(1-)=0.417 20.583=0.101 系统中有3辆车的概率为： P3=3(1-)=0.417 30.583=0.0421,Little公式,M/M/1:/FCFS的系统指标,系统中的平均顾客数L,队列中的平均顾客

9、数Lq,顾客在系统中的平均逗留时间W,顾客在队列中的平均逗留时间Wq,例,高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求L、Lq、W和Wq。,解,根据题意，=200辆/小时，=240辆/小时，=/=5/6。,有限队列模型 M/M/1:N/FCFS,当队列的容量从无限值变为有限值N时，M/M/1:/FCFS就转化成为M/M/1:N/FCFS,系统的状态转移图,系统的状态概率平衡方程,对于状态0：P0=P1 对于状态k：Pk-1+Pk+1=(+)Pk 0kN 对于状态N：PN-1=PN,系统的状

10、态概率,由,得到,系统的运行指标,对于1有,有效到达率,Little公式,例,一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求： 1、顾客到达不用等待就可理发的概率； 2、理发店里的平均顾客数以及等待理发的平均顾客数； 3、顾客来店理发一次平均花费的时间及平均等待的时间； 4、顾客到达后因客满而离去的概率； 5、增加一张椅子可以减少的顾客损失率。,解,这是一个M/M/1:N/FCFS系统，其中N=4+1=5，=4人/小时，=6人

11、/小时，=2/3。,因客满而离去的概率为0.0048,当N=6时,P5-P6=0.0480-0.0311=0.0169=1.69%,即增加一张椅子可以减少顾客损失率1.69%,M/M/1:/m/FCFS模型,设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中。如此循环往复 。,分析,假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为 。当正在等待及正在接受服务的顾客数为n时，则在单位时间内要求接受服务的平均顾客数为 ： n=(m-n),状态转移方程,0P0 = P1 n+Pn = Pn+1+n-1Pn-1(n=1，2，m-1) Pm=m-1Pm-1,(n

12、=1，2，m),运行指标,例,某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求: (1)修理工空闲的概率； (2)五台机器都出故障的概率； (3)出故障的平均台数； (4)平均停工时间； (5)平均等待修理时间； (6)评价这个系统的运行情况。,解,根据题意，m=5，=1/15，=1/12，=/=0.8,多服务台模型M/M/c,标准的M/M/c:/FCFS模型 系统容量有限的M/M/c:N/FCFS模型 有限顾客源的M/M/c:/m/FCFS模型,M/M/c:/FCFS模型,顾客到达后，进入队列尾端

13、；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即1=2=c,分析,系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1kc时，系统中的顾客全部在服务台中，这时系统的服务速率为k；当系统中的顾客数kc时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为c。,则当1时系统才不会排成无限的队列,状态转移图与状态转移方程,对状态0:P0=P1 对状态1:P0+2P2=(+)P1 对状态c：Pc-1+cPc+1=(+c)Pc 对状态n Pn-1+cPn+1=(+c)Pn,状态

14、概率,运行指标,例,某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人分。顾客到达后排成一队，依次到空闲窗口购票。求： (1)所有窗口都空闲的概率； (2)平均队长； (3)平均等待时间及逗留时间； (4)顾客到达后必须等待的概率。,解,/=2.25，=/c=0.75,(1)所有窗口都空闲的概率，即求P0的值,(2)平均队长，即求L的值，必须先求Lq,(3)平均等待时间和平均逗留时间，即求Wq和W和的值,(4)顾客到达后必须等待，即n3,M/M/c:N/FCFS模型,分析,设系统容量为N(Nc)，当系统中的顾数nN时

15、，到达的顾客就进入系统；当n=N时，到达的顾客就被拒绝。设顾客到达的速率为，m每个服务台服务的速率为，=/c。由于系统不会无限止地接纳顾客，对不必加以限制。,状态转移图与状态转移方程,对状态0:P0=P1 对状态1:P0+2P2=(+)P1 对状态c：Pc-1+cPc+1=(+c)Pc 对状态N PN-1=cPN ,状态概率,运行指标,例,某旅馆有8个单人房间，旅客到达服从Poisson流，平均速率为6人天，旅客平均逗留时间为2天，求： (1)每天客房平均占用数； (2)旅馆客满的概率。,解,旅馆8个房间全满的概率为0.423,平均占用客房数为6.9间。客房占用率为86.6%,M/M/c:/m/FCFS模型,状态概率,其中,运行指标,效到达速率e为单位时间内出现故障的机器数，有 e=(m-L),例,车间有5台机器，每台机器的故障率为1次小时，有2个修理工负责修理这5台机器，工作效率相同，为4台小时。求： (1)等待修理的平均机器数； (2)等待修理及正在修理的平均机器数； (3)每小时发生故障的平均机器数；