运筹学课件7.排队论

《运筹学课件7.排队论》由会员分享，可在线阅读，更多相关《运筹学课件7.排队论（84页珍藏版）》请在金锄头文库上搜索。

1、1,第十二章 排队论,2,知识点 排队系统的组成 排队模型的研究方式 典型排队系统模型的结构,3,引言,从两个角度来考虑 （1）计算数据和参数（性态问题） 包括售票处的空闲概率、平均队长、平均等待时间、平均逗留时间等等 统计的方法 （2）优化排队系统（最优化问题） 站在顾客的角度，怎样让顾客尽量的少排队； 站在服务机构的角度，怎样让总费用降低，达到资源的充分利用 Queueing Theory、Random Service System Theory,最优设计（静态）,最优控制（动态）,4,引言,起源 20世纪初 Bell电话公司 1909年 丹麦工程师A.K，Erlang “概率论与电话交换

2、” 排队问题在现实世界中非常常见 （被服务者是人） 乘公交 到超市购买物品 到医院看病 去售票处购买车票 食堂（饭店）就餐 打电话,5,引言,（被服务者是物） 生产线上的半成品 因故障停止运转的机器 码头的船只 要降落的飞机,6,引言,特点 （1）都有请求服务的人或物 （2）有为顾客服务的人或物 （3）具有随机性,顾客,服务机构,7,第一节 基本概念,一、排队系统的一般表示 二、排队系统的组成和特征 三、排队模型的分类 四、研究目的和问题,8,一、排队系统的一般表示,例1 各个顾客由顾客源出发，到达服务机构前排队等候 服务，服务完了后就离开。,排队结构指队列的数目和排列方式,排队规则和服务规则

3、是说明顾客在排队系统中按怎样的规则、次序接受服务的。,排队规则,排队系统,第一节 基本概念,9,现实生活中的排队系统,10,二、排队系统的组成和特征,输入即指顾客到达排队系统，可能有以下不同情况。,1、输入过程,定长分布,11,2、排队规则,顾客在排队系统中按怎样的规则、次序接受服务的。,（1）顾客到达时，所有服务台被占用,First Come First Serve/FCFS,Last Come First Serve/LCFS,Serve in Random Order/SIRO,Preference/PR,混合制（Losing System and Waiting System）,队长有

4、限,等待时间有限,12,3、服务机构,（2）服务台数量及构成,单队单服务台,多队多服务台（并列）,单队多服务台（并列）,顾客到达,服务台,服务完成后离去,队列,13,（5）服务时间的分布总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响,单队-多服务台（串列）,单队-多服务台（混合）,定长分布,二项分布、泊松分布、爱尔朗分布,14,顾客源,排队规则,服务机构,顾客总体数,顾客到达方式,顾客流的概率分布,损失制,等待制,混合制,服务台数量及构成,服务方式,服务时间,单个、成批,确定型、随机型,5种结构,FCFS LCFS SIRO PR,有限、无限 (m),一个一个、成批,确定型、随机型

5、,顾客到达,输入过程,占有空间,队列,具体、抽象；容量(N)有限、无限,单列、多列 (c)；互相转移；中途退出,独立、不独立,平稳、不平稳,服务时间的分布,平稳、非平稳,服务员数量,没有、一个或多个,15,三、排队模型的分类,1、1953年，D.G.Kendall提出第一种分类方法,X/Y/Z,X处填写表示相继到达间隔时间的分布;,Y处填写表示服务时间的分布;,Z处填写并列的服务台的数目c.,表示相继到达间隔时间和服务时间的各种分布的符号:,M负指数分布,D确定型,Ekk阶爱尔朗分布,GI 一般相互独立的时间间隔的分布,G 一般服务时间的分布,c=1 单服务台,c1 多服务台,16,2、197

6、1年关于排队论符号的标准化会议上决定，将Kendall符号扩展成为：,X/Y/Z/A/B/C,前三项意义不变，而,A处填写系统容量限制N；,B处填写顾客源数m（有限、无限）；,C处填写服务规则（FCFS/LCFS/SIRO/PR）。,约定：,N=c,损失制,N=,等待制系统,Nc,混合制系统,GI/Ek/1/N/ FCFS；M/M/1/ FCFS,17,四、研究目的和问题,研究目的 了解系统的基本特征和性态，揭示其表现出来的概率规律性，以便对系统做出评价或者优化。 研究的问题 排队系统的数量指标（特征量） 统计推断问题的研究 排队系统的优化,18,排队系统的数量指标,3、队长(Ls)：排队系统

7、中顾客的平均数 。,4、队列长(Lq)： 指系统中排队等候服务的顾客数。,5、逗留时间(Ws)：指一个顾客在系统中的停留时间。,Ls=Lq+正被服务的顾客数,1、平均到达率()：单位时间内平均到达的顾客数。,平均到达间隔 (1/),=3（个/小时） 1/=1/3（小时）,2、平均服务率()：单位时间内平均服务的顾客数。,平均服务时间(1/),=4（个/小时）；1/=1/4（小时）,队列长队长,队长：等待服务,接受服务,逗留时间：排队时间,接受服务时间,19,排队系统的数量指标,6、等待时间(Wq)：指一个顾客在系统中排队等待的时间。,Ws=Wq+服务时间,7、忙期：指从顾客到达空闲服务机构起到

8、服务机构再次空闲止 这段时间长度，即服务机构连续繁忙的时间长度。,等待时间逗留时间,8、闲期：服务台连续保持空闲的时间长度。,9、服务设备利用率： 服务设备工作时间占总时间的比例,10、顾客损失率：由于规模有限、服务能力不足而造成的顾客 流失的概率,等待制的排队系统需不需要考虑顾客损失率？,20,排队系统的数量指标,11、系统的状态：描述系统中的顾客数,12、系统的状态概率Pn( t ) ：指t时刻、系统状态为n的概率,13、稳定状态（统计平衡状态）：limPn(t)Pn,Pn=PN=n 稳态 系统中有n个顾客 概率 P1 稳态 系统中有1个顾客 概率 P0 稳态 所有服务台全部空闲 概率,1

9、4、有效平均到达率(e)：每单位时间内进入系统的平均顾客数,等待制 =e,损失制、服务台个数c,系统容量N,系统容量无限,损失制 e,t,0,1,2,.,N,0,1,2,.,0,1,2,.,c,21,排队系统的优化,排队系统的最优化的目的在于使得服务系统既能在适当的程度满足顾客的需求，同时又使所需的费用达到最小。,极小,提高服务水平会降低顾客的等待费用，但又增加了服务机构的成本。,费用：可以从两个方面来考虑,服务水平：服务台、平均服务率，反映了服务台的服务能力,双赢,顾客的角度,服务机构的角度,22,第二节 时间分布,一、经验分布 二、定长分布 三、Poisson分布 四、负指数分布,23,一

10、、经验分布,例2 某服务机构单服务台，先到先服务，对41顾客记录到达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。,第二节 时间分布,24,25,i,i+1,wi,si,wi+si-ti,wi+siti,0,wi+1=,wi+siti,ti=i+1-i,ti,wi+1,ti,空闲,i+1 第i+1个顾客到达的时刻,i 第i个顾客到达的时刻,wi 第i个顾客等待的时间,si 对第i个顾客服务的时间,i+1,ti 前后两个顾客到达时间间隔,wi+1 第i+1个顾客的等待时间,26,到达间隔分布表,服务时间分布表,平均间隔时间： 1/ 142/40=

11、3.55(分钟/人),平均到达率： 41/142=0.28(人/分钟),平均服务率： 41/127=0.32(人/分钟),平均服务时间： 1/ 127/41=3.12(分钟/人),27,二、定长分布,定长分布 顾客有规则的等距到达，每间隔时间到达一个顾 客。相继顾客到达间隔T的分布函数F(t)为：,28,三、Poisson分布,设N(t)表示在时间0, t)内到达顾客数,令Pn(t1, t2)表示在时间区间t1, t2)（t2 t1）内有n（0）个顾客到达的概率，即,Pn(t1, t2)=P N(t2) N(t1)=n （t2t1，n0）,Poisson分布的三个条件：,(1) 无后效性：不相

12、重叠的时间区间内顾客到达数相互独立,(2) 平稳性：在长度为t的时间段内，有1个顾客到达的概率仅与时间长度有关，而与时间段的起始时刻无关。,N(t)=2,N(t)=n,29,(3) 普通性：表明在很短的一个时间段内顾客是一个一个来到系统的,初始条件：P0(0)=1,t,P0(t,t+t) =1- P1(t,t+t)- =1-t+o(t),30,Poisson分布流的合成/分解 相互独立的Poisson流经过合成后的流仍然是Poisson流（到达十字路口的车流可以看成是流的合成） 1+2 Poisson分布流的过滤 一个流经过一个随机过滤器后得到的子流仍是Poisson流 p 随机过滤器,31,

13、Pn(t+t)= Pn(t) ( 1-t+o(t)+ Pn-1(t)t+ o(t),在上述条件下，研究顾客到达数 n 的概率分布,Poisson流的概率分布,Pn(t),PN(t)=n,Pn(t+t),32,Pn(t+t)= Pn(t)(1-t )+Pn-1(t)t+ o(t),Pn(t+t)-Pn(t)/t =-Pn(t)+Pn-1(t)+o(t)/t,令t0, P0(t)=e -t,Pn(t)=(t)n e -t /n,t 0, n=0，1，2,解得,33,EN(t) 在长为t的时间段内到达顾客数的期望值,平均到达率,Poisson流的期望值和方差,34,四、负指数分布,T-随机变量,排队

14、系统中顾客到达的时间间隔（无后效性）,概率密度,分布函数,35,如果输入过程是Poisson流，那么顾客相继到达的间隔时间T必服从负指数分布,相继到达间隔时间独立、负指数分布,输入过程是Poisson分布,M,36,第三节 单服务台负指数分布排队系统的分析,一、M/M/1 模型 二、M/M/1/N/ 模型 三、M/M/1/m模型,37,一、M/M/1 模型,1、假设,第三节 单服务台负指数分布排队系统的分析,（2）顾客到达的间隔时间满足参数为的负指数分布,（5）服务时间满足参数为的负指数分布（ ）,（4）单服务台 c=1,（1）顾客源是无限的，顾客相互独立,（3）单队排列，对队长没有限制，FC

15、FS,（6）到达间隔时间和服务时间是相互独立的,等待制系统,(M/M/1/FCFS),服务机构,排队规则,输入过程,38,2、Pn(t)的计算,O表示发生（1个） ， 表示没有发生,Pn(t+t)= Pn(t)(1-t)(1- t),t,t,t,Pn(t),Pn(t),Pn+1(t),Pn-1(t),1-t,1-t,t,1-t,1-t,+ Pn-1(t)t(1- t),+ Pn(t)tt,+ Pn+1(t)(1-t)t,（在时刻t系统中有n个顾客的概率）,39,整理得：,Pn(t+t)= Pn(t)(1-t-t)+Pn+1(t)t+Pn-1(t)t+o(t),Pn(t+t)-Pn(t)/t =

16、Pn-1(t)+Pn+1(t)-(+)Pn(t),令t0 dPn(t)/dt=Pn-1(t)+Pn+1(t)(+)Pn(t) ( n1) (1),关于Pn(t)的微分差分方程,40,t,P0(t),P1(t),1-t,1-t,1,考虑P0(t)的情况：,P0(t+t)=P0(t)(1-t)+P1(t)(1-t)t,令t0 dP0(t)/dt=-P0(t)+P1(t) (2),令dPn(t)/dt=0，由(1)和(2)得到,关于P0(t)的微分差分方程,稳态,41,由 (3)式得,通过求解可得, 单位时间内到达的平均顾客数, 单位时间内服务的平均顾客数, 服务强度 1( ),参数意义：,令n=1，由(4)式得,服务机构的繁忙程度,Pn?,42,n-1,n,0,1,n+1,.,.,P0=P1,Pn-1+Pn+1 = (+)Pn,对