排队模型(掌握mm1,mmc,mm1k)

1、编辑ppt1排队模型凯里学院余英编辑ppt2模型要点模型要点1、掌握排队模型的基本概念、掌握排队模型的基本概念2、了解常见的分布函数及生灭过程、了解常见的分布函数及生灭过程3、掌握典型排队系统模型的结构及应用、掌握典型排队系统模型的结构及应用编辑ppt3排队模型的基本概念排队模型的基本概念1、什么是排队模型（排队论）？、什么是排队模型（排队论）？排队论是研究拥挤现象的一门学科。它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优化设计（静态）和最优控制（动态）问题。一、引言一、引言编辑ppt4现实生活中的排队系统现实生活中的排队系统序序号号到达的顾客到达的顾客要求服务内容要求服务内

2、容服务机构服务机构1 1不能运转的机器不能运转的机器修理修理修理技工修理技工2 2修理技工修理技工领取修配零件领取修配零件发放修配零件的管理员发放修配零件的管理员3 3病人病人诊断或做手术诊断或做手术医生医生( (或包括手术台或包括手术台) )4 4电话呼唤电话呼唤通话通话交换台交换台5 5文件搞文件搞打字打字打字员打字员6 6提货单提货单提取存货提取存货仓库管理员仓库管理员7 7驶入港口的货船驶入港口的货船装装( (卸卸) )货货装装( (卸卸) )货码头货码头( (泊位泊位) )8 8上游河水进入水库上游河水进入水库 放水，调整水位放水，调整水位水闸管理员水闸管理员编辑ppt52、排队论的

3、起源与应用领域1）、20世纪初Bell电话公司为减少用户呼叫， 研究电话线路合理配置问题；2）、1909年丹麦工程师A.K.Erlang受热力学统计平衡概念启发发表论文概率论与电话交换，解决上述问题；3）、应用于：通讯系统、交通运输、机器维修、库存控制、计算几设计等领域。编辑ppt6二、排队系统的特征及其组成1、排队系统的特征即拥挤现象的共性1）、有请求服务的人或物2）、有为顾客服务的人或物3）、具有随机性4）、服务的数量超过服务机构的容量编辑ppt72、排队系统的三大基本组成部分1）、输入过程）、输入过程(顾客到达的方式顾客到达的方式)a、顾客的总体（顾客源）的组成可能是有限的，也、顾客的总

4、体（顾客源）的组成可能是有限的，也可能是无限的；可能是无限的；b、顾客相继到达的时间间隔可以是确定的，也可以、顾客相继到达的时间间隔可以是确定的，也可以是随机的，对于随机的情形，要知道单位时间内的是随机的，对于随机的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布；顾客到达数或相继到达的间隔时间的概率分布；c 、输入过程可以是平稳的（描述相继到达的间隔时、输入过程可以是平稳的（描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间分布和所含参数（如期望值、方差等）都是与时间无关的），否则成为非平稳的，我们研究平稳的。间无关的），否则成为非平稳的，我们研究平稳的。编辑

5、ppt82、排队系统的三大基本组成部分2）、排队规则a、顾客到达时，如所有服务台都被占用，在这种情形下，顾客可以随即离去，也可以排队等待，前者成为损失制，后者成为等待制，我们研究后者；其次还有混合制，它是介于等待制和损失制之间的；b、从占有的空间来看，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限，有的没有这种限制编辑ppt92、排队系统的三大基本组成部分3）、服务过程）、服务过程a、可以是没有服务员，单个的，多个的，对于多个、可以是没有服务员，单个的，多个的，对于多个的，它们之间可以是平行排列（并列）的，也可以的，它们之间可以是平行排列（并列）的，也可以是前后排列（串列）的，也可以

6、是混合的；是前后排列（串列）的，也可以是混合的；b、服务时间可以是确定的，也可以是随机的，对于、服务时间可以是确定的，也可以是随机的，对于后者要知道它的概率分布；后者要知道它的概率分布；c、服务时间可以是平稳的，也可以是非平稳的，我、服务时间可以是平稳的，也可以是非平稳的，我们研究前者；们研究前者；d、对于等待制，服务规则又可以分为先到先服务、对于等待制，服务规则又可以分为先到先服务（FCFS），后到先服务（），后到先服务（LCFS），随机服务和有），随机服务和有优先权的服务。优先权的服务。编辑ppt10三、排队模型的分类（符号表示） 我们采用Kendall记号 顾客相继到达时间间隔分布/服务

7、时间分布/服务台数目/排队系统允许的最大顾客容量（系统容量）/顾客总体数量（顾客源数量）/排队规则说明：如果说明：如果Kendall记号中略去后记号中略去后3项，表示项，表示x/y/z/FCFS相继到达时间间隔和服务时间分布的符号如下：相继到达时间间隔和服务时间分布的符号如下：M负指数分布负指数分布D确定型确定型Ekk阶爱尔朗分布阶爱尔朗分布GI一般相互独立的时间间隔分布一般相互独立的时间间隔分布G一般服务时间分布一般服务时间分布编辑ppt11四、排队模型的数量指标四、排队模型的数量指标1、平均队长、平均队长(Ls)： 指在系统中的顾客数（包括正被服务的顾客指在系统中的顾客数（包括正被服务的顾

8、客 和排队等待的顾客）的期望值。和排队等待的顾客）的期望值。2、平均排队长、平均排队长(Lq)： 指系统中排队等候服务的顾客数指系统中排队等候服务的顾客数的期望值的期望值。3、平均平均逗留时间逗留时间(Ws)：指一个顾客在系统中的停留时间指一个顾客在系统中的停留时间期望值。期望值。 4、平均平均等待时间等待时间(Wq)：指一个顾客在系统中排队等待的时间的指一个顾客在系统中排队等待的时间的期望值。期望值。 Ls=Lq+正被服务的顾客数正被服务的顾客数Ws=Wq+服务时间服务时间5、忙期：、忙期：指从顾客到达空闲服务机构起到服务机构再次空闲止指从顾客到达空闲服务机构起到服务机构再次空闲止 这段时间

9、长度，即服务机构连续繁忙的时间长度。这段时间长度，即服务机构连续繁忙的时间长度。6、系统的状态概率、系统的状态概率Pn( t ) ：指系统中的顾客数为指系统中的顾客数为n的概率。的概率。7、稳定状态：、稳定状态：limPn(t)Pn编辑ppt12四、排队模型的数量指标8、n n 系统有系统有n n个顾客时的平均到达率个顾客时的平均到达率9 9、n n 系统有系统有n个顾客时的平均服务率个顾客时的平均服务率1010、 对任何对任何n都是常数的平均都是常数的平均到达到达率率1111、 对任何对任何n都是常数的平均服务率都是常数的平均服务率1212、 服务强度，或称使用因子，平均到达率与服务强度，或

10、称使用因子，平均到达率与服务台与平均服务率的乘积的比值服务台与平均服务率的乘积的比值13、系统的状态、系统的状态系统中的顾客数，如果系统中有系统中的顾客数，如果系统中有n个顾客，就说系统的状态是个顾客，就说系统的状态是n，系统的状态是随着时间，系统的状态是随着时间在变化的在变化的14、pn(t):时刻时刻t系统状态为系统状态为n的概率，稳态时系统状态的概率，稳态时系统状态为为n的概率用的概率用pn表示。表示。编辑ppt13五、常见的分布函数及生灭过程常见的分布函数及生灭过程1、poisson流流定义：设定义：设N（t）为时间）为时间0，t内到达系统的顾客数，如果满足下内到达系统的顾客数，如果满

11、足下面三个条件：面三个条件： a、平稳性：在、平稳性：在t,t+t内有一个顾客到达的概率为内有一个顾客到达的概率为 t+o(t+o(t);); b、独立性（无后效性）：任意两个不相交区间内顾客到达情、独立性（无后效性）：任意两个不相交区间内顾客到达情况相互独立；况相互独立； c、普遍性：在、普遍性：在t,t+t内多于一个顾客到达的概率为内多于一个顾客到达的概率为o(o(t););则称则称N（t），），t0为为poisson流。流。2、poisson分布分布 设设N（t）为时间）为时间0，t内到达系统的顾客数，则内到达系统的顾客数，则N（t），），t0为为poisson流的充要条件是：流的充要条

12、件是：() ( )(1,2,.)!nttp N tnenn编辑ppt14五、常见的分布函数及生灭过程常见的分布函数及生灭过程3、负指数分布、负指数分布定理：设定理：设N（t）为时间）为时间0，t内到达系统的顾客数，则内到达系统的顾客数，则N（t），），t0为参数为为参数为 的的poisson流的充要条件是：流的充要条件是：相继到达时间间隔服从相互独立的参数为相继到达时间间隔服从相互独立的参数为的负指数分的负指数分布。布。4、k阶爱尔朗分布阶爱尔朗分布设设v1, v2,., vk是是k个相互独立的随机变量，服从相同参数个相互独立的随机变量，服从相同参数k的负指数分布，那么的负指数分布，那么 T=

13、 T= v1+v2+.+ vk服从服从k阶爱尔朗分布。阶爱尔朗分布。编辑ppt15五、常见的分布函数及生灭过程常见的分布函数及生灭过程5、生灭过程定义：设N（t），），t0为一随机过程，若为一随机过程，若N（t）的概率）的概率分布具有以下性质：分布具有以下性质： a、假设、假设N（t）=n,则从时刻则从时刻t起到下一个顾客到达时刻起到下一个顾客到达时刻止的时间服从参数为止的时间服从参数为n的负指数分布，的负指数分布，n=0,1,2, b、假设假设、假设假设N（t）=n,则从时刻则从时刻t起到下一个顾客离去起到下一个顾客离去时刻止的时间服从参数为时刻止的时间服从参数为n的负指数分布，的负指数分布

14、，n=0,1,2, c、同一时刻时只有一个顾客到达或离去。、同一时刻时只有一个顾客到达或离去。 则称则称N（t），），t0为一个生灭过程。为一个生灭过程。编辑ppt16五、常见的分布函数及生灭过程常见的分布函数及生灭过程根据系统平稳状态时根据系统平稳状态时“流入流入=流出流出”原理，得到如原理，得到如下任一状态下的平衡方程：下任一状态下的平衡方程：0 1 1p p1 1= = 0 0p p0 01 1 0 0p p0 0+ + 2 2p p2 2= =（ 1 1+ + 1 1 ）p p1 12 2 1 1 p p1 1+ + 3 3p p3 3 = =（ 2 2+ + 2 2）p p2 2 n

15、-1 n-1 n-2n-2p pn-2 n-2 + + n np pn n = =（ n-1n-1+ + n-1n-1 ）p pn-1n-1n n n-1n-1p pn-1 n-1 + + n+1n+1p pn+1 n+1 = =（ n n+ + n n ）p pn n 生灭过程中Cn与p0的推导及应用编辑ppt17五、常见的分布函数及生灭过程常见的分布函数及生灭过程由上述方程可求得0 p1 1 = p= p0 00/ 0/ 1 11 p1 p2 2 =1 1p p1 1/2 2+(+(1 1p p1 1- p- p0 00 0)/ )/ 2 2 =p =p0 00 01 1/(/(2 21

16、1) )2 p2 p3 3 =2 2p p2 2/3 3+(+(2 2p p2 2- p- p1 11 1)/)/3 3 =p =p0 02 21 10 0/(/(3 32 21 1) ) n-1 pn-1 pn n =n-1n-1p pn-1n-1/n n+(+(n-1n-1p pn-1n-1- p- pn-2n-2n-2n-2)/)/n n =p =p0 0n-2n-2n-1n-10 0/(/(n nn-1n-11 1) )n pn p3 3 =n np pn n/n+1n+1+(+(n np pn n- p- pn-1n-1n-1n-1)/)/n+1n+1 =p =p0 0n nn-1n

17、-10 0/(/(n+1n+1nn1 1) )编辑ppt18五、常见的分布函数及生灭过程常见的分布函数及生灭过程记则平稳状态的分布为pn=cnp0。由此可得生灭过程排队系统的各项指标，即12010.(1,2,.).nnnnncn 0111nnpc0,(),qnqnqnn ceeelllnp lnc p ww其中 是整体平均到达率编辑ppt196、经验分布、经验分布例例1 1 某服务机构单服务台，先到先服务，对某服务机构单服务台，先到先服务，对4141顾客记录到达顾客记录到达时刻时刻 和服务时间和服务时间s s（单位：分钟）如下表，表中第（单位：分钟）如下表，表中第1 1号顾客到号顾客到达时刻为

18、达时刻为0 0。全部服务时间为。全部服务时间为127127（分钟）。（分钟）。(1) i(2)i(3)si(4)ti(5)wi(1)i(2)i(3)si(4)ti(5)wi(1)i(2)i(3)si(4)ti(5)wi10520512271093612022743619435103827036156722346114552041191282631051247423五、常见的分布函数及生灭过程常见的分布函数及生灭过程编辑ppt20(1) i(2) i(3)si(4)ti(5)wi(1) i(2)i(3)si(4)ti(5)wi(1) i(2) i(3)si(4)ti(5)wi1349135238

19、6622331174471452293248854634121267156111025921373512712316622302695365361296121765150271012423713033718703202810521038133527197248129106131391352410208031030109250401394382181222311141204114219228333232116810编辑ppt21到达间隔分布表到达间隔分布表服务时间分布表服务时间分布表平均间隔时间：平均间隔时间：=142/40=3.55(分钟分钟/人人)平均到达率：平均到达率：41/142=0.2

20、8(人人/分钟分钟)平均服务率：平均服务率：41/127=0.32(人人/分钟分钟)平均服务时间：平均服务时间：127/41=3.12(分钟分钟/人人)到达间隔到达间隔(分钟分钟)次次数数12345678910以上以上61086322111合计合计40服务时间服务时间(分钟分钟)次次数数123456789以上以上10107542111合计合计41编辑ppt22六、典型排队系统模型的结构及应用六、典型排队系统模型的结构及应用M/M/C等待制排队模型研究要点：a、系统意义b、状态转移速度图与状态转移速度矩阵c、状态概率方程d、系统的基本数量指标编辑ppt23PassionPassion分布分布设设

21、N(t)表示在时间表示在时间0, t)内到达顾客数；内到达顾客数；令令Pn(t1, t2)表示在时间区间表示在时间区间t1, t2)（t2 t1）内有）内有n（ 0）个顾客到达的概率，即个顾客到达的概率，即Pn(t1, t2)=P N(t2) N(t1)=n （t2t1，n 0）Passion分布的三条件：分布的三条件：(1) 无后效性：不相重叠的时间区间内顾客到达数相互独立无后效性：不相重叠的时间区间内顾客到达数相互独立 1(2)( ,)()P t tttt 2(3)( ,)()nnP t ttt 编辑ppt24Pn(t+t)= Pn(t) ( 1-t+o(t) + Pn-1(t)t + o

22、(t)情情况况0, t)t, t+t )0, t+t )个个数数概率概率个个数数概率概率个个数数概率概率(A)(B)(C)nn-1n-2n-30Pn(t)Pn-1(t)Pn-2(t)Pn-3(t)P0(t)0123n1-t+o(t)to(t)nnnnnPn(t) ( 1-t+o(t)Pn-1(t)to(t) 在上述条件下，研究顾客到达数在上述条件下，研究顾客到达数 n 的概率分布的概率分布编辑ppt25 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 令令t0d Pn(t)/dt= -Pn(t)

23、 +Pn-1(t)Pn(0)=0（n 1）d P0(t)/dt= -P0(t)P0(0)=1（n=0） P0(t)=e -t Pn(t)=(t)n e -t /n t 0, n=0，1，2编辑ppt26负指数分布负指数分布fT（t）=e -t ， t 00 ，t0 1 ttttttttE Ttedttedttdeteedtedtedte( )（）（） 0000000011 ttttV TE TE Ttedtt etedttedt（ ）（）（ ） 2222022200022211122211 编辑ppt27一、一、M/M/1 M/M/1 模型模型1 1、假设、假设（1）顾客到达的间隔时间满足参数

24、为）顾客到达的间隔时间满足参数为的负指数分布的负指数分布（2）服务时间满足参数为）服务时间满足参数为的负指数分布（的负指数分布（ ）（3）服务机构是单服务台）服务机构是单服务台（4）顾客源是无限的，顾客相互独立）顾客源是无限的，顾客相互独立（5）单队排列，且对队长没有限制）单队排列，且对队长没有限制第三节 单服务台负指数分布排队系统的分析编辑ppt282 2、P Pn n的计算的计算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情况情况在时刻在

25、时刻t顾客数顾客数在区间（在区间（t, t+t）在时刻在时刻t+t顾客数顾客数到达到达离去离去(A)(B)(C)(D)nn+1n-1nOOOOnnnn编辑ppt29整理得：整理得：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)t0 dPn(t)/dt=Pn-1(t)+Pn+1(t)(+)Pn(t)考虑考虑P0(t)的情况：的情况：P0(t+t)=P0(t)(1-t)+P1(t)(1-t)tt0 dP0(t)/dt=-P0(t)+P1(t) (2)由由dPn(t)/d

26、t=0得到得到-P0+P1=0 (3)Pn-1+Pn+1-(+)Pn=0 (4)编辑ppt30 nnPP ()P200111111 nnPPn01(1),1 1 PP0 由式由式(3)得得, 0 1 2nnPPn（ ）， ，0 通过求解可得通过求解可得 单位时间内到达的平均顾客数单位时间内到达的平均顾客数 单位时间内服务的平均顾客数单位时间内服务的平均顾客数 服务强度服务强度参数意义：参数意义：编辑ppt313 3、M/M/1M/M/1参数计算参数计算（1）系统中平均顾客数（）系统中平均顾客数（Ls） SnnLnP230(1)2(1)3(1) 23(1)(23)S S232342323 S23

27、(1)1 sL1 记记编辑ppt32（2）队列中等待的平均顾客数（）队列中等待的平均顾客数（Lq） 2111(1)()qnnnsnnnLnPnPPL （3）顾客逗留时间（）顾客逗留时间（Ws）sWE W1（4）队列中顾客等待时间（）队列中顾客等待时间（Wq）1()qsWW 编辑ppt33它们的相互关系如下：它们的相互关系如下：, , 1ssqqsqsqLWLWWWLL 其中其中称为称为little公式，它是排队论中的一个重要公式。公式，它是排队论中的一个重要公式。, ssqqLWLW 编辑ppt34例例3 100个工作小时内每小时个工作小时内每小时来就诊的病人数来就诊的病人数n出现次数如下出现

28、次数如下 100个完成手术的病例所用时间个完成手术的病例所用时间v(小时小时)出现的次数如下出现的次数如下到达的病到达的病人数人数n出现次数出现次数tn0123456102829161061合计合计100为病人完成手术为病人完成手术时间时间v(小时小时)出现次数出现次数tv0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上以上3825179650合计合计100编辑ppt35解：解：)/( 1 . 2100)1(小时小时人人病人平均到达率病人平均到达率 nnf)/(4 . 0100人人小小时时每每次次手手术术平平均均时时间间vvf)/(5 . 24 .

29、 01小小时时人人平平均均服服务务率率）每每小小时时完完成成手手术术人人数数（ 0.842.52.1 5 . 2 , 1 . 2)2( 则则取取)(25. 51 . 25 . 21 . 2)3(人人 sL)( 1 . 21 . 25 . 284. 0小小时时qW)(5 . 21 . 25 . 21小小时时sW)(41. 425. 584. 0人人qL编辑ppt36 假定系统最大容量为假定系统最大容量为N N，单服务台情形排队等待的顾客，单服务台情形排队等待的顾客最多为最多为N-1N-1，下面只考虑稳态情形：，下面只考虑稳态情形： nnnNNPPPPPnNPP10111(),1n 1 nN Nn

30、NPP0111111 二、二、M/M/1/N/ M/M/1/N/ 模型模型解得：解得：编辑ppt37根据上式我们可以推导出系统的各项指标：根据上式我们可以推导出系统的各项指标：有效到达率有效到达率e=(1-PN)可以验证：可以验证：1-P0= e /qsW1W (4) 顾客等待时间顾客等待时间qsNLLPPt01W11（）（）(3) 顾客逗留时间顾客逗留时间 NNnNnNnP1s101L, 111 （）(1) 队长队长 NnsonnPLPq1L11 （）（）(2) 队列长队列长编辑ppt38例例4 4 单人理发馆有六个椅子接待客人。当单人理发馆有六个椅子接待客人。当6 6个椅子都坐满时，个椅子

31、都坐满时，后来的顾客不进店就离开。顾客平均到达率为后来的顾客不进店就离开。顾客平均到达率为3 3人人/ /小时，理发小时，理发需时平均需时平均1515分钟。则：分钟。则： N=7为系统中最大的顾客数，为系统中最大的顾客数，=3=3人人/ /小时，小时，=4=4人人/ /小时小时（1）求某顾客一到达就能理发的概率。）求某顾客一到达就能理发的概率。2778. 04/314/31P 80）（概概率率为为相相当当于于没没有有顾顾客客，所所求求（2）求需要等待的顾客数的期望值。）求需要等待的顾客数的期望值。11. 2)4/3(1)4/3(84/314/3L88s39. 1)2778. 01(11. 2)

32、1(L0qPLs编辑ppt39（3）求有效到达率。）求有效到达率。e P0(1)4(10.2778)2.89 分分钟钟小小时时8 .4373. 089. 2/11. 2/s esLW（4）求一顾客在理发馆内逗留的时间。）求一顾客在理发馆内逗留的时间。（5）在可能到达的顾客中有百分之几不等待就离开。）在可能到达的顾客中有百分之几不等待就离开。7 P7788311/34() ()( ) ()3.7%31(/)41( )4 （人（人/ /小时）小时）编辑ppt40一、一、M/M/cM/M/c.,.1,率率或或服服务务机机构构的的平平均均利利用用这这个个系系统统的的服服务务强强度度称称它它为为列列时时

33、才才不不会会排排成成无无限限的的队队只只有有当当令令 cc () (c) 101111(1)() ,1() ,nnnnnnPPnPPn Pn cc PPcPn.110 ，且且这这里里iiP第四节 多服务台指数分布排队系统的分析规定各服务台工作相互独立且平均分配服务率相同，即规定各服务台工作相互独立且平均分配服务率相同，即1=2=c= 整个服务机构的平均服务率为整个服务机构的平均服务率为c, (nc) n, (n c) 编辑ppt41用递推法解上述差分方程，可求得状态概率。用递推法解上述差分方程，可求得状态概率。-1-1n-1 () !1 ()! 1 ()! 0000111ckcknnncP()kc!() PncnP() Pncc c根据上式我们可以推导出系统的各项指标：根据上式我们可以推导出系统的各项指标： 021(),()(1)！csqqnn ccLLLnc PPc右边右边）（！）（因为因为 0111PcccnPnPcncnnnncncnn qsqsLLWW， 编辑ppt42例例6 6 某售票所有三个窗口，顾客到达服从某售票所有三个窗口，顾客到达服从PassionPassion过程，平均到过程，平均到达率每分钟达率每分钟=0.9(=0.9(人人),),服务服务(