《大学运筹学经典课件第十四章——队论》由会员分享，可在线阅读，更多相关《大学运筹学经典课件第十四章——队论（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) 损失制： 到达的顾客有一部分未接受服务就离去。5、平稳状态： 业务活
4、动与时间无关。,5,排队系统的符号表示:一个排队系统的特征可以用五个参数表示，形式为： ABCDE 其中 A 顾客到达的概率分布，可取M、 D、G 、Ek等； B 服务时间的概率分布，可取M、D、 G 、 Ek等； C 服务台个数，取正整数； D 排队系统的最大容量，可取正整数或； E 顾客源的最大容量，可取正整数或。例如 M / M / 1 / / 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,1 排队过程的组成部分,6,M / M / 1 / / 单位时间顾客平均到达数 ，单位平均服务顾客数 ( ) 数量指标公式:1. 系统中无顾客
5、的概率 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、客， 也就是 / c时,3 多服务台泊松到达、负指数服务时间的排队模型,14,例 在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是36人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理48位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。解 C = 2， 平均到达率 = 36/60 = 0.6，平均服务率 = 48/60 = 0.8。 P0 =0.4545, Lq = 0.1227 (个顾客), Ls = Lq + / = 0.8727 (个顾客), Wq = Lq / = 0.2045（分钟）,
7、 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 / 2模型与使用两个M / M / 1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M / M / 2中只排一队，在2个M / M / 1中排两个队，结果却不一 样。 M / M / 2使得服务水平有了很大的提高，每个顾客的平均排队时间从
8、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模型中，计算求得这些数量指标是很繁琐的。管理运筹学软件有排队论的程序，可以由它来计算。我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三个公式表示了任一个排队模型（不仅仅是M/M/1或M/M/2）中，Ls,Lq,Ws,Wq之间的关系，也就是说：,3 多服务台泊松到
9、达、负指数服务时间的排队模型,16,3 多服务台泊松到达、负指数服务时间的排队模型,对任一个排队模型成立，这里Ls,Lq,Ws,的定义如上所述，而 应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为这时，原来公式中的 应改为 。,17,我们把一个排队系统的单位时间的总费用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=44.73 元/每小时。,
