运筹学排队论合工大的-免财富值PPT课件

.,1,第十二章排队论,.,2,一、排队系统的一般表示,例1各个顾客由顾客源出发，到达服务机构前排队等候服务，服务完了后就离开。,排队结构指队列的数目和排列方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。,排队规则,排队系统,第一节基本概念,.,3,现实生活中的排队系统,.,4,二、排队系统的组成和特征,输入即指顾客到达排队系统，可能有以下不同情况。,1、输入过程,.,5,2、排队规则,顾客在排队系统中按怎样的规则、次序接受服务的。,（1）顾客到达时，所有服务台被占用,.,6,3、服务机构,（2）多服务台时,单队单服务台,多队多服务台（并列）,单队多服务台（并列）,.,7,（5）服务时间的分布我们总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响,多服务台（串列）,多服务台混合,.,8,三、排队模型的分类,1、1953年，D.G.Kendall提出第一种分类方法,X/Y/Z,X处填写表示相继到达间隔时间的分布;,Y处填写表示服务时间的分布;,Z处填写并列的服务台的数目.,表示相继到达间隔时间和服务时间的各种分布的符号:,M负指数分布,D确定型,Ekk阶爱尔朗分布,GI一般相互独立的时间间隔的分布,G一般服务时间的分布,.,9,2、1971年关于排队论符号的标准化会议上决定，将Kendall符号扩展成为：,X/Y/Z/A/B/C,前三项意义不变，而,A处填写系统容量限制N；,B处填写顾客源数m；,C处填写服务规则。,约定：,.,10,四、排队系统的参数,1、队长(Ls)：指在系统中的顾客数。,2、排队长(Lq)：指系统中排队等候服务的顾客数。,3、逗留时间(Ws)：指一个顾客在系统中的停留时间。,4、等待时间(Wq)：指一个顾客在系统中排队等待的时间。,Ls=Lq+正被服务的顾客数,Ws=Wq+服务时间,5、忙期：指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度，即服务机构连续繁忙的时间长度。,6、系统的状态概率Pn(t)：指系统中的顾客数为n的概率。,7、稳定状态：limPn(t)Pn,.,11,一、经验分布,例2某服务机构单服务台，先到先服务，对41顾客记录到达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。,第二节时间分布,.,12,.,13,到达间隔分布表,服务时间分布表,平均间隔时间：=142/40=3.55(分钟/人),平均到达率：41/142=0.28(人/分钟),平均服务率：41/127=0.32(人/分钟),平均服务时间：127/41=3.12(分钟/人),.,14,二、Passion分布,设N(t)表示在时间0,t)内到达顾客数；,令Pn(t1,t2)表示在时间区间t1,t2)（t2t1）内有n（0）个顾客到达的概率，即,Pn(t1,t2)=PN(t2)N(t1)=n（t2t1，n0）,Passion分布的三条件：,(1)无后效性：不相重叠的时间区间内顾客到达数相互独立,.,15,Pn(t+t)=Pn(t)(1-t+o(t)+Pn-1(t)t+o(t),在上述条件下，研究顾客到达数n的概率分布,.,16,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)ne-t/n,t0,n=0，1，2,.,17,三、负指数分布,.,18,一、M/M/1模型,1、假设,第三节单服务台负指数分布排队系统的分析,.,19,2、Pn的计算,O表示发生（1个），表示没有发生,Pn(t+t)=Pn(t)(1-t)(1-t)+Pn+1(t)(1-t)t+Pn-1(t)t(1-t)+Pn(t)tt,.,20,整理得：,Pn(t+t)=Pn(t)(1-t-t)+Pn+1(t)t+Pn-1(t)t+o(t),Pn(t+t)-Pn(t)/t=Pn-1(t)+Pn+1(t)-(+)Pn(t)(1),t0dPn(t)/dt=Pn-1(t)+Pn+1(t)(+)Pn(t),考虑P0(t)的情况：,P0(t+t)=P0(t)(1-t)+P1(t)(1-t)t,t0dP0(t)/dt=-P0(t)+P1(t)(2),由dPn(t)/dt=0得到,.,21,由式(3)得,通过求解可得,单位时间内到达的平均顾客数,单位时间内服务的平均顾客数,服务强度,参数意义：,.,22,3、M/M/1参数计算,（1）系统中平均顾客数（Ls）,记,.,23,（2）队列中等待的平均顾客数（Lq）,（3）顾客逗留时间（Ws）,（4）队列中顾客等待时间（Wq）,.,24,它们的相互关系如下：,.,25,例3100个工作小时内每小时来就诊的病人数n出现次数如下,100个完成手术的病例所用时间v(小时)出现的次数如下,.,26,解：,.,27,假定系统最大容量为N，单服务台情形排队等待的顾客最多为N-1，下面只考虑稳态情形：,二、M/M/1/N/模型,解得：,.,28,根据上式我们可以推导出系统的各项指标：,有效到达率e=(1-PN),可以验证：1-P0=e/,(4)顾客等待时间,(3)顾客逗留时间,(1)队长,(2)队列长,.,29,例4单人理发馆有六个椅子接待客人。当6个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则：,N=7为系统中最大的顾客数，=3人/小时，=4人/小时,（1）求某顾客一到达就能理发的概率。,（2）求需要等待的顾客数的期望值。,.,30,（3）求有效到达率。,（4）求一顾客在理发馆内逗留的时间。,（5）在可能到达的顾客中有百分之几不等待就离开。,（人/小时）,.,31,机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。,顾客总体虽然只有m个，但每个顾客服务后仍回到总体，仍然可以到来。,三、顾客源为有限的情形（M/M/1/m）,.,32,根据上式我们可以推导出系统的各项指标：,在机器故障问题中Ls就是平均故障台数，而,.,33,例5某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。,求（1）修理工空闲的概率；（2）五台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的台数；（5）平均停工时间；（6）平均等待时间；（7）评价这些结果。,.,34,解：,（7）机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。,.,35,一、M/M/c,第四节多服务台指数分布排队系统的分析,.,36,用递推法解上述差分方程，可求得状态概率。,根据上式我们可以推导出系统的各项指标：,.,37,例6某售票所有三个窗口，顾客到达服从Passion过程，平均到达率每分钟=0.9(人),服务(售票)时间服从负指数分布,平均服务率每分钟=0.4(人).,=0.9,.,38,代入公式得,(1)整个售票所空闲的概率,（2）平均队长,（3）平均等待时间和逗留时间,（4）顾客到达后必须等待（即系统中顾客数已有3人）的概率,.,39,M/M/c型系统和c个M/M/1系统的比较,上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，如下图二每个队列平均到达率为=0.9/3=0.3（每分钟），这样原来的系统就变成3个M/M/1型的子系统。,.,40,现按M/M/1型解决这个问题，并与上表比较：,从表中各指标的对比可以看出单队比三队有显著的优越性,.,41,系统的状态概率和运行指标如下:,二、M/M/c/N/,.,42,三、M/M/c/m,(2)平均故障台数：,有效到达率：,.,43,（1）等待修理的机器平均数（2）需要修理的机器平均数（3）有效损坏数（4）等待修理时间（5）停工时间,例7设有两个修理工人，负责5台机器的正常运行，每台机器平均损坏的概率为每运转一小时1次，两个工人能以相同的平均修复率4（次/小时）修好机器。求:,.,44,(1)Lq=P3+2P4+3P5=0.118,(3)e=1(5-1.094)=3.906,(4)Wq=0.118/3.906=0.03小时,(5)Ws=1.094/3.906=0.28小时,.,45,服务时间是任意分布的情形：,一、M/G/1,服务时间T的分布是一般的其它的条件和标准的M/M/1型相同。为了达到稳态，1这一条件是必要的,其中=ET.,第五节一般服务时间M/G/1模型,.,46,例8有一售票口,已知顾客按平均为2分30秒的时间间隔的负指数分布到达.顾客在售票口前服务时间平均为2分钟.(1)若服务时间也服从负指数分布,求顾客为购票所需的平均逗留时间和等待时间;(2)若经过调查,顾客在售票口前至少要占用1分钟,且认为服从服务时间服从负指数分布是不恰当的;而应服从以下概率密度分布.,.,47,(2)令y为服务时间，那么Y=1+X,X服从均值为1的负指数分布。于是,.,48,二、M/D/1,服务时间是确定的常数，例如在一条装配线上完成一件工作的时间应是常数。自动的汽车的冲洗台，冲洗一台汽车的时间也是常数，这时,例9某实验室有一台自动检验机器性能的仪器，要求检验机器的顾客按Passion分布到达，每小时平均4个顾客，检验每台机器所需时间为6分钟。,求:（1）在检验室内机器台数Ls(期望值)（2）等候检验的机器台数Lq（3）每台机器在室内消耗（逗留）时间Ws（4）每台机器平均等待检验的时间Wq,.,49,注：在一般服务时间分布的Lq和Wq中以定长服务时间的为最小，这符合我们通常的理解服务时间越有规律，等候的时间就越短,.,50,三、M/Ek/1模型,.,51,对于M/Ek/1模型（除服务时间外，其它条件与标准的M/M/1型相同）,.,52,例10某单人裁缝店做西服，每套需经过4个不同的工序，4个工序完成后才开始另一套。每一套工序的时间服从负指数分布，期望值为2小时。顾客到来服从Passion分布，平均订货率为5.5套/周(设一周6天,每天8小时).以顾客为等到做好一套西服期望时间有多少?,解顾客到达=5.5套/周,设为平均服务率(单位时间完成的套数);1/为