第14章排队论.ppt

《第14章排队论.ppt》由会员分享，可在线阅读，更多相关《第14章排队论.ppt（41页珍藏版）》请在三一文库上搜索。

1、1,第十四章 排队论,1 排队过程的组成部分 2 单服务台泊松到达、负指数服务时间的排队模型 3 多服务台泊松到达、负指数服务时间的排队模型 4 排队系统的经济分析 5 单服务台泊松到达、任意服务时间的排队模型 6 单服务台泊松到达、定长服务时间的排队模型 7 多服务台泊松到达、任意的服务时间、损失制排队模型 8 顾客来源有限制排队模型 9 单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型 10 多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型 *11 生灭过程及生灭过程排队系统,2,一、基本概念 一些排队系统的例子 排队系统 顾 客 服务台 服 务 电话系统 电话呼叫 电

2、话总机 接通呼叫或取消呼叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击，敌机被击落或离开 排队的过程可表示为：,排队,服务机构服务,服务后顾客离去,排队系统,顾客到达,1 排队过程的组成部分,3,考虑要点： 1、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。 2、顾客到达过程：本教材主要考虑顾客的泊松到达情况。 满足以下四个条件的输入流称为泊松流（泊松过程）。 *平稳性：在时间区间 t, t+t) 内到达k个顾客的概率与t无关，只与 t 有关，记为 pk(t）； *无后效性：不相交的时间区

3、间内到达的顾客数互相独立； *普通性：在足够短的时间内到达多于一个顾客的概率可以忽略； *有限性：任意有限个区间内到达有限个顾客的概率等于1。 泊松分布 为单位时间平均到达的顾客数 P (x) = x e- / x! (x = 0, 1, 2,),1 排队过程的组成部分,4,1 排队过程的组成部分,3、服务时间分布： 服从负指数分布， 为平均服务率，即单位时间服务的顾客数， P（服务时间 t ) = 1- e- t 。 4、排队规则分类 (1) 等待制： 顾客到达后，一直等到服务完毕以后才离去， 先到先服务，后到先服务，随机服务，有优先权的服务； (2) 损失制： 到达的顾客有一部分未接受服务

4、就离去。 5、平稳状态： 业务活动与时间无关。,5,排队系统的符号表示: 一个排队系统的特征可以用五个参数表示，形式为： ABCDE 其中 A 顾客到达的概率分布，可取M、 D、G 、Ek等； B 服务时间的概率分布，可取M、D、 G 、 Ek等； C 服务台个数，取正整数； D 排队系统的最大容量，可取正整数或； E 顾客源的最大容量，可取正整数或。 例如 M / M / 1 / / 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,1 排队过程的组成部分,6,M / M / 1 / / 单位时间顾客平均到达数 ，单位平均服务顾客数 (

5、) 数量指标公式: 1. 系统中无顾客的概率 P0 =1 / 2. 平均排队的顾客数 Lq =2/( ) 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平均等待时间 Wq = Lq / 5. 顾客在系统中的平均逗留时间 Ws = Wq+ 1/ 6. 顾客得不到及时服务必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn =( /)n P0,1 排队过程的组成部分,2 单服务台泊松到达、负指数服务时间的排队模型,7,2 单服务台泊松到达、负指数服务时间的排队模型,在上面的公式中，我们都认定 ,即到达率小于服务率，如果没有这个条件，则排队的长度将无

6、限制地增加，服务机构根本没有能力处理所有到达的顾客， 也就是 / 1,我们称 / 为服务强度。 例 某储蓄所只有一个服务窗口。根据统计分析，顾客的到达过程服从泊松分布，平均每小时到达顾客36人；储蓄所的服务时间服从负指数分布，平均每小时能处理48位顾客的业务。试求这个排队系统的数量指标。 解 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。 P0 =1 / = 10.6/0.8 = 0.25, Lq =2/( ) = (0.6)2 / 0.8(0.8 0.6) =2.25 (个顾客),8,Ls = Lq + / = 2.25+ 0.6/0.8 =3 (个顾客)

7、, Wq = Lq / = 2.25/0.6 = 3.75（分钟）, Ws = Wq+ 1/ = 3.75+1/0.8 =5 （分钟）, Pw = / = 0.6/0.8 = 0.75, Pn =( /)n P0 = (0.75)n 0.25, n=1, 2, 。 通过计算，可知储蓄所的排队系统里有n个顾客的概率，见表14-1。,2 单服务台泊松到达、负指数服务时间的排队模型,表14-1,9,2 单服务台泊松到达、负指数服务时间的排队模型,通过计算数据与表中数据，可知储蓄所的排队系统并不尽如人意，到达储蓄所有75%的概率要排队等待，排队的长度平均为2.25个人，排队的平均时间为3.75分钟，是

8、1.25分钟的3倍，而且储蓄所里有7个或更多的顾客的概率为13.35%，这个概率太高了。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。 如采取第一种方法，不增加服务窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的48人提高到60人，即每分钟平均服务的顾客数从0.8人提高到1人，这时 仍然为0.6， 为1，通过计算得到的结果如表14-2所示：,10,2 单服务台泊松到达、负指数服务时间的排队模型,从上表我们可以看出由于把服务率从0.8提高

9、到1，其排队系统有了很大的改进，顾客平均排队时间由3.75分钟减少到1.5分钟，顾客平均逗留时间从5分钟减少到2.5分钟，在系统里有7个或更多顾客的概率有大幅度的下降，从13.35%下降到2.79%。 如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去（譬如，当把这个服务台设在另一个地点，上述假设就成立了）。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系,表14-2,11,2 单服务台泊松到达、负指数服务时间的排队模型,统，每个排队系统中有一个服务台，每个系统的服务率仍然为0.8，但到达率由于分流，只有原

10、来的一半了， =0.3，这时我们可求得每一个排队系统的数量指标如表14-3所示：,表14-3,我们比较表14-1和14-3，知道采用第二个方法的服务水平也使得原来的服务水平有了很大的提高，采用第二种方法顾客平均排队时间减少到了0.75分钟，顾客平均逗留时间减少到了2分钟，第二种排队系统为两个M/M/1排队系统。如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，这样的排队系统就变成了 M/M/2排队系统。,12,M / M / C / / 单位时间顾客平均到达数 ，单位平均服务顾客数 。 1. 系统中无顾客的概率 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + /

11、 , 4. 顾客花在排队上的平均等待时间 Wq = Lq / ,3 多服务台泊松到达、负指数服务时间的排队模型,13,5. 顾客在系统中的平均逗留时间 Ws = Wq+ 1/ , 6. 系统中顾客必须排队等待的概率 7. 系统中恰好有 n 个顾客的概率,当nc时,当nc时,3 多服务台泊松到达、负指数服务时间的排队模型,14,例 在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是36人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理48位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。 解 C =

12、2， 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。 P0 =0.4545, Lq = 0.1227 (个顾客), Ls = Lq + / = 0.8727 (个顾客), Wq = Lq / = 0.2045（分钟）, Ws = Wq+ 1/ = 1.4545 （分钟）, Pw = 0.2045, P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067。 系统里有6个人的概率或多于6个人的概率为0.0040。,3 多服务台泊松到达、负指数服务时间的排队模型,15,在储蓄所里使用M / M

13、 / 2模型与使用两个M / M / 1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M / M / 2中只排一队，在2个M / M / 1中排两个队，结果却不一 样。 M / M / 2使得服务水平有了很大的提高，每个顾客的平均排队时间从0.75分钟减少到0.2045分钟，每个顾客在系统里逗留时间从2分钟减少到1.4545分钟，平均排队的人数也从0.2250人减少到0.1227人，系统里平均顾客数也从0.6*2=1.2人减少到0.8727人。如果把M / M / 2与原先一个M / M / 1比较，那么服务水平之间的差别就更大了。 当然在多服务台的M/M/C模型中，计算求得这些

14、数量指标是很繁琐的。管理运筹学软件有排队论的程序，可以由它来计算。 我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三个公式表示了任一个排队模型（不仅仅是M/M/1或M/M/2）中，Ls,Lq,Ws,Wq之间的关系，也就是说：,3 多服务台泊松到达、负指数服务时间的排队模型,16,3 多服务台泊松到达、负指数服务时间的排队模型,对任一个排队模型成立，这里Ls,Lq,Ws,的定义如上所述，而 应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为 这时，原来公式中的 应改为 。,17,我们把一个排队系统的单位时

15、间的总费用TC定义为服务机构的单位时间的费用和顾客在排队系统中逗留单位时间的费用之和。即 TC = cw Ls + cs c 其中 cw为一个顾客在排队系统中逗留单位时间付出的费用；Ls为在排队系统中的平均顾客数；cs为每个服务台单位时间的费用；c为服务台的数目。 例 在前两例中，设储蓄所的每个服务台的费用cs=18，顾客在储蓄所中逗留一小时的成本cw =10。这样，对储蓄所M / M / 1 模型可知 Ls =3， c=1，得 TC = cw Ls + cs c=48 元/每小时。 对储蓄所 M / M / 2 模型可知 Ls =0.8727， c=2，得 TC = cw Ls + cs c

16、=44.73 元/每小时。,4 排队系统的经济分析,18,M / G / 1 / / 单位时间顾客平均到达数 ，单位平均服务顾客数 ， 一个顾客的平均服务时间 1 / ，服务时间的均方差。 数量指标公式: 1. 系统中无顾客的概率 P0=1 / 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平均等待时间 Wq = Lq / 5. 在系统中顾客的平均逗留时间 Ws = Wq+ 1/ 6. 系统中顾客必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn,5 单服务台泊松到达、任意服务时间的排队模型,19,例1 某杂货店只有一

17、名售货员，已知顾客的到达过程服从泊松分布，平均到达率为每小时20人；不清楚这个系统的服务时间服从什么分布，但从统计分析知道售货员平均服务一名顾客的时间为2分钟，服务时间的均方差为1.5分钟。试求这个排队系统的数量指标。 解：这是一个 M / G / 1 的排队系统，其中 = 20/60 = 0.3333 人/分钟，1/ = 2分钟， = =0.5 人/分钟， =1.5。 P0 =1 / = 0.33334, Lq =1.0412 (人), Ls = Lq + / = 1. 7078 (人), Wq = Lq / = 2.25/0.6 = 3.1241（分钟）, Ws = Wq+ 1/ =5.1

18、241（分钟）, Pw = / = 0.6666。,5 单服务台泊松到达、任意服务时间的排队模型,20,6 单服务台泊松到达、定长服务时间的排队模型,M / D / 1 / / 注：它是 M / G / 1 / / 的特殊情况 = 0。 1. 系统中无顾客的概率 P0=1 / 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平均等待时间 Wq = Lq / 5. 在系统中顾客的平均逗留时间 Ws = Wq+ 1/ 6. 系统中顾客必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn,21,例2 某汽车冲洗服务营业部，有一套

19、自动冲洗设备，冲洗每辆车需要6分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到达6辆，试求这个排队系统的数量指标。 解：这是一个 M / D / 1 排队模型，其中 = 6辆/小时， = 60/6 =10辆/小时，得 P0 =1 / = 0.4, Lq =0.45, Ls = Lq + / = 1.05, Wq = Lq / = 0.0750， Ws = Wq+ 1/ =0.1750, Pw = / = 0.6。,6 单服务台泊松到达、定长服务时间的排队模型,22,M / G / C / C / 注：不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间 Wq。数量指标公式: 系

20、统中的平均顾客数 Ls = / (1 Pc ) 其中Pc 是系统中恰好有 c 个顾客的概率，也就是系统里c 个服务台都被顾客占满的概率。 系统中恰好有 n 个顾客的概率,7 多服务台泊松到达、任意的服务时间、损失制排队模型,23,例3. 某电视商场专营店开展了电话订货业务，到达过程服从泊松分布，平均到达率为每小时16个，而一个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化的，但平均每个人每小时可以处理8个订货电话，在此电视商场专营店里安装了一台电话自动交换台，它接到电话后可以接到任一个空闲的接话员的电话上，试问该公司应安装多少台接话员的电话，使得订货电话因电话占线而损失

21、的概率不超过10%。 解：这是一个 M / G / C / C / 模型。当c=3时，即正好有3位顾客的情况，,7 多服务台泊松到达、任意的服务时间、损失制排队模型,24,0.21050.1,所以不符合要求。 当c=4时， 因此，设置四个电话很合适。,7 多服务台泊松到达、任意的服务时间、损失制排队模型,25,M / M / 1 / / m 条件：单位时间顾客平均到达数 单位平均服务顾客数 关心的项目: 1. 系统中无顾客的概率 P0 2. 系统中平均排队的顾客数 Lq 3. 系统中的平均顾客数 Ls 4. 系统中顾客平均的排队等待时间 Wq 5. 系统中顾客的平均逗留时间 Ws 6. 系统中

22、顾客必须排队等待的概率 Pw 7. 系统中恰好有 n 个顾客的概率 Pn,8 顾客来源有限制的排队模型,26,M /M / 1 / /m 数量指标公式: 1. 系统中无顾客的概率 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + (1-p0) 4. 顾客在排队上的平均花费等待时间 Wq = Lq /（m-Ls) 5. 在系统中顾客的平均逗留时间 Ws = Wq+ 1/ 6. 系统中有 n 个顾客的概率, n=0,1,2,m,8 顾客来源有限制的排队模型,27,例4. 某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟，有一个修理工，每次修理时间

23、服从负指数分布，平均每次12分钟，求该排队系统的数量指标P0,Lq,Ls,Wq,Ws,以及P5。 解：这是一个M/M/1/ /5系统。其中，m=5, =1/15, =1/12,/ =0.8。 Lq=2.766 ; Ls=3.759 Wq=33.43 ; Ws=45.43 P5=0.2870,=0.0073,8 顾客来源有限制的排队模型,28,9 单服务台泊松到达、负指数服务时间、系统容量有 限制的排队模型,这种模型我们记为M/M/1/K/，这个记法中的第四位字母K表示这个系统的最大容量为N，因为这是一个单服务台的情况，所以排队的顾客服务最多为K-1，在某时刻一顾客到达时，如系统中已有N个顾客，

24、那么这个顾客就被拒绝进入系统。 这个模型可简写为M/M/1/K。 由于所考虑的排队子系统中最多只能容纳K个顾客（等待位置只有K-1个），因而有:,令 ， 有：,1.系统里没有顾客的概率,2.在系统里的平均顾客数,3. 平均的排队顾客数,29,9 单服务台泊松到达、负指数服务时间、系统容量有 限制的排队模型,4.有效顾客到达率,5.一位顾客花在排队上的平均时间,6.一位顾客在系统中的平均逗留时间,7.在系统里正好有n个顾客的概率,30,9 单服务台泊松到达、负指数服务时间、系统容量有 限制的排队模型,例5 某理发店只有一个理发师，且店里最多可容纳4名顾客，设顾客按泊松流到达，平均每小时5人，理发

25、时间服从负指数分布，平均每15分钟可为1名顾客理发，试求该系统的有关指标。 解：该系统可以看成一个M/M/1/4排队系统，其中,31,9 单服务台泊松到达、负指数服务时间、系统容量有 限制的排队模型,系统里平均顾客数,=,平均的排队顾客数,平均逗留时间,平均排队时间,32,10 多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,这种排队模型我们记为M/M/C/K/，这与第九节单服务台模型的 区别，就在于服务台的数量为C，我们可以把这个模型简记为M/M/C/K。 在此系统中到达率与服务率分别为:,1.系统里没有顾客的概率 2.系统里正好有n个顾客的概率,33,10 多服务台泊松到达、负

26、指数服务时间、系统容量有限制的排队模型,3.平均排队顾客数,4.系统里的平均排队顾客数,5.有效到达率,6.顾客花在排队上的平均时间,7.顾客在系统里的平均逗留时间,特别地，当k=c时即为第七节的M/M/C/C/的模型。,34,10 多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,例6 某公司维修服务中心有两名维修工，中心内至多可以停放6台机 器（包括正在维修的两台机器）。假设待修机器按泊松分布过程到达此中 心。平均每小时3台。维修每台机器平均需要20分钟，试求该系统的各项 性能指数。 解：该子系统可看成一个M/M/2/6排队系统,35,11* 生灭过程及生灭过程排队系统,1. 生

27、灭过程 生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队 模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/C和 M/M/C/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中， 一个新顾客的到达看作“生”，一个顾客服务完之后离开系统看作是 “死”，设N(t)的任意时刻t排队系统的状态（即排队子系统中的总顾客 数），则对M/M/C/K系统N(t)具有有限个状态0，1，,k,对M/M/C来说 N(t)具有可列个状态0，1，2。 一般来说，随机过程 满足以下条件，称为生灭过程： 1) 假设N(t)=n，则从时刻t起到下一个顾客到达时刻为止的时间服 从参数为 的负指数分布

28、，n=0,1,2, 2) 假设N(t)=n，则从时刻t起到下一个顾客离去时刻为止的时间服 从参数为 的负指数分布，n=0,1,2, 3) 同一时刻时只有一个顾客到达或离去。,36,11* 生灭过程及生灭过程排队系统,2. 生灭过程稳态方程,方程为：,由此可求得生灭过程的平稳状态分布：,由于,即有,即有,即有,37,11* 生灭过程及生灭过程排队系统,即当,时，此生灭过程存在平稳状态分布：,38,11* 生灭过程及生灭过程排队系统,M/M/C和M/M/C/K排队系统，顾客到达间隔服从参数为 的负指数分布，顾客在系统中服务时间服从参数为 的负指数分布，并满足生灭过程的其他条件。它们都是生灭过程的排队系统，我们都可以从生灭过程的平衡方程来推导出这些排队公式。我们以M/M/1系统为例进行推导。在这个系统中，,39,11* 生灭过程及生灭过程排队系统,同时也可计算出此系统的其他性能指标:,40,11* 生灭过程及生灭过程排队系统,同样我们也可用生灭过程的平衡方程推导出M/M/1/K系统的公式。 在这个系统中,41,11* 生灭过程及生灭过程排队系统,利用上面给出的平稳状态的分布，即可推出此系统的其他性能指标。这些指标我们已经在前面告诉大家了（计算过程从略）。,