十四章排队论.ppt

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

1、排队过程的组成部分 单服务台泊松到达、负指数服务时间的排队模型 多服务台泊松到达、负指数服务时间的排队模型 排队系统的经济分析 单服务台泊松到达、任意服务时间的排队模型 单服务台泊松到达、定长服务时间的排队模型 多服务台泊松到达、任意的服务时间、损失制排队模型 顾客来源有限制排队模型,1,第十三章 排队论 (Queuing Theory),排队论，又称随机服务系统理论或等待线理论，是研究要求获得某种服务的对象所产生的随机性聚散现象的理论。它是运筹学的一个重要分支。本章只介绍排队论的基本理论与方法。,2,第十三章 排队论 (Queuing Theory),1910年:丹麦电话工程师A.K.埃尔朗

2、在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。,3,第十三章 排队论 (Queuing Theory),自20世纪初以来，电话系统的设计一直在应用这个公式。 30年代苏联数学家.欣钦把处于统计平衡的电话呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他们用数学方法深入地分析了电话呼叫的本征特性，促进了排队论的研究。,4,第十三章 排队论 (Queuing Theory),50年代初，美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入

3、马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。,5,第十三章 排队论 (Queuing Theory),50年代初，美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。

4、,6,第十三章 排队论 (Queuing Theory),赌徒输光问题：两个赌徒甲、乙进行一系列赌博。在每一局中甲获胜的概率为p，乙获胜的概率为q，p+q=1，每一局后，负者要付一元给胜者。如果起始时甲有资本a元，乙有资本b元，a+b=c，两个赌徒直到甲输光或乙输光为止，求甲输光的概率。,7,第十三章 排队论 (Queuing Theory),排队是日常生活中经常遇到的现象，如顾客到商店去买东西，病人到医院去看病，当售货员、医生的数量满足不了顾客或病人及时服务的需要时，就出现了排队的现象。 出现这样的排队现象，使人感到讨厌，但由于顾客到达人数（即顾客到达率）和服务时间的随机性，可以说排队现象又

5、是不可避免的。当然增加服务设施（如售货员、医生）能减少排队现象，但这样势必增加投资且因供大于求使设施常常空闲。,8,第十三章 排队论 (Queuing Theory),作为管理人员来说，就要研究排队问题，把排队时间控制在一定的限度内，在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。 排队论就是解决这类问题的一门科学，它被广泛地应用于解决诸如电话局的占线问题，车站、码头、机场等交通枢纽的堵塞与疏导，故障机器的停机待修，水库的存贮调节等有形无形的排队现象的问题。,9,排队论模型是由一些数学公式和它们相应之间的关系所组成，这些数学公式使我们可以求出排队系统的数量指标，这些数量指标刻划了排队

6、系统运行的优劣情况。,10,1. 系统中无顾客的概率，即服务设施空闲的概率 P0 2. 排队的平均长度，即排队的平均顾客数 Lq 3. 系统中的平均顾客数(排队和被服务的顾客数) Ls 4. 顾客花在排队上的平均等待时间 Wq 5. 顾客在系统中的平均逗留时间 (排队和被服务) Ws 6. 顾客得不到及时服务必须排队等待的概率 Pw 7. 系统中恰好有 n 个顾客的概率 (排队和被服务) Pn,11,排队过程的基本组成部分为：顾客的到达、排队规则和服务机构的服务。,12,图 13-1,1 排队过程的组成部分,排队过程的基本组成部分为：顾客的到达、排队规则和服务机构的服务。,13,图 13-1,

7、1 排队过程的组成部分,排队过程的基本组成部分为：顾客的到达、排队规则和服务机构的服务。,14,服务后顾客离去,顾客到达,排队,服务机构 服务,1 排队过程的组成部分,服务机构 服务,服务机构 服务,排队过程的基本组成部分为：顾客的到达、排队规则和服务机构的服务。,15,服务后顾客离去,顾客到达,排队,服务机构 服务,1 排队过程的组成部分,服务机构 服务,服务机构 服务,排队,排队,服务后顾客离去,服务后顾客离去,排队过程的基本组成部分为：顾客的到达、排队规则和服务机构的服务。,16,服务后顾客离去,顾客到达,排队,服务机构 服务,1 排队过程的组成部分,排队,服务机构 服务,一些排队系统的

8、例子 排队系统 顾客 服务台 服 务 电话系统 电话呼叫 电话总机 接通呼叫/ 取消呼叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击直至 敌机被击落或离开,17,为了说明排队过程的这些组成部分，我们举例加以说明。中国工商银行在某居民小区的储蓄所，其主要业务是为居民的定期、活期储蓄提供服务和销售国库券和债券，虽然储蓄所希望当每一位顾客一到马上为其提供服务，但是有时顾客的人数一下到达过多，储蓄所不能同时为所有的顾客提供服务，顾客不得不排队等待服务。储蓄所的领导为了减少顾客的等待时间改进服务，开始对储蓄所的排队

9、系统进行了调查研究，首先做了以下的一些调查:,18,排队系统中的一些要素： 1、服务机构的服务台（或通道）的数目。这个储蓄所只设一个服务窗口，所有的业务都由这个窗口来处理，也就是说服务机构只有一个服务台，我们把这样的排队系统称之为单服务台（或通道）的排队系统。 服务台（或通道）数目：单服务台（或单通道）、多服务台（或多通道）。,19,2、顾客到达过程。一位顾客的到达相对于另外的顾客的到达是独立的，没有联系的。储蓄所通过调查又了解到顾客到达储蓄所的时间是随机的，有一个顾客到达的概率与某一时刻 t 无关，但与时间的间隔长度有关，即在较长的时间间隔里有一个顾客到达的概率越大，并且当时间的间隔长度 t

10、 充分小时，有一个顾客到达的概率与 t 的长度成正比例。 在充分小的时间间隔里有两个顾客同时到的概率极小，可以忽略不计。这些特征正好满足了泊松分布的三个条件，也就是说储蓄所的顾客到达过程形成了泊松流。 运用泊松概率分布函数，知道在单位时间里有 x个顾客到达的概率 P(x) = x e- / x! (x = 0, 1, 2,) 这里 x 为单位时间到达的顾客数， 为单位时间平均到达的顾客数， e 2.71828。,20,本教材主要考虑顾客的到达服从泊松分布的排队问题。 例: 这个储蓄所根据统计分析得知顾客的到达过程服从泊松分布，并且平均每小时到达顾客 36人，即平均每分钟到达的顾客人数为 36/

11、 60 = 0.6。若把时间单位定为分钟，则平均到达率 = 0.6 ，每分钟有 x 个顾客到达的概率,21,以上我们看到在一分钟 里没有人到达的概率为 0.5488， 正好有一人到达的概率为 0.3292， 正好有两个人到达的概率为 0.098。,22,满足下面四个条件的输入流称为泊松流 (泊松过程)： 平稳性：在时间区间 t，t + t) 内到达 k 个顾客的概率与 t 无关，只与 t 有关，记为 pk (t）； 无后效性：不相交的时间区间内到达的顾客数互相独立； 普通性：在充分小的时间间隔里多于一个顾客到达的概率极小，可以忽略不记； 有限性：任意有限个区间内到达有限个顾客的概率等于 1 。

12、,23,3.服务时间的分布 服务时间:是指顾客从开始接受服务到服务完成所花费的时间。 由于每位顾客要办的业务都不一样，又存在很多影响服务机构的服务时间的随机因素，因此服务时间也是一个随机变量。一般来说，负指数概率分布能较好地描述一些排队系统里的服务时间的概率分布情况，在负指数概率分布里，服务时间小于或等于时间长度 t 的概率 P(服务时间 t ) = 1e -t。 这里 为单位时间里被服务完的平均顾客数。,24,储蓄所认为负指数概率分布能近似地反映了储蓄所的服务时间的概率分布情况，并统计出这一个服务窗口平均每小时能处理 48 位顾客的业务，也就是说每分钟平均能处理 48/60=0.8 位顾客的

13、业务，即平均服务率 0.8，这样我们可求得 P（服务时间 0.5分 ) = 1 e(0.80.5)0.3297 P（服务时间 1分 ) = 1 e(0.81)0.5507 P（服务时间 2分 ) = 1 e(0.82)0.7981。 P(服务时间 t ) = 1e -t。,25,二、排队规则 排队规则也是排队系统的一个重要组成部分。当顾客到达时，所有服务台都正被占用时，在有些排队系统里顾客随即离去如电话呼唤系统，我们把它称为损失制。 在另一些排队系统里顾客会排队等待服务如机场候机排队系统，我们把它称为等待制。 对于等待制系统，为顾客进行服务的次序可以采用以下一些规则：先到先服务，这是最常见的情

14、形；后到先服务，如乘用电梯的顾客常是先入后出；随机服务，如邮局分信常常是随机分拣的；有优先权的服务，如医生对于病情严重的患者将给予优先治疗。 在这一章排队模型里都是按照先到先服务的规则处理问题的。储蓄所的排队规则显然也是先到先服务的。,26,排队规则分类 (1) 损失制：当顾客到达时，由于所有的服务台都被占用，有部分顾客未接受服务就离去了。 (2) 等待制：当顾客到达时，由于所有的服务台都被占用，顾客需要等待服务，直到接受服务完毕以后才离去，这时有：先到先服务，后到先服务，随机服务，有优先权的服务。 三、平稳状态 当储蓄所早上刚开门营业时，顾客很少，一般把这个时间称为过渡时期，过了过渡时期，储

15、蓄所的业务活动才进入正常的平稳状态，排队论的模型是描述排队系统的平稳状态 。,27,排队系统的 ( 肯道尔 ) 符号表示 一个排队系统的特征可以用六个参数表示，形式为： ABC （ DE F ） A 顾客到达的概率分布，可取 M、D、G、Ek 等； B 服务时间的概率分布，可取 M、D、G、Ek 等； C 服务台的个数，取正整数； D 排队系统的最大容量，可取正整数或 ； E 顾客源的最大容量，可取正整数或 ； F 排队规则。 其中： M 泊松分布、负指数分布 Ek k 阶爱尔朗分布 D 定长分布 G 一般分布 先到先服务（FCFS）； 后到先服务（LCFS）； 随机服务（SIRO）； 优先权

16、服务（PR）。,28,例如 M / M / 1 / / / FCFS 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制，排队（服务）规则是先到先服务。,29,泊松分布与负指数分布的联系 定理：顾客到达过程是一个具有参数 的泊松分布的充分必要条件是，相继到达间隔 Tk 是一簇相互独立的随机变量，且每个随机变量 Tk 都服从参数为 的负指数分布。 注：由定理知，“泊松流”与“到达间隔为相互独立的负指数分布”是一回事，都具有马尔科夫性，故肯道尔用记号 M（马尔科夫的头一个字母）表示这二者。,30,泊松分布与负指数分布的联系 马尔科夫（1856192

17、2），俄罗斯数学家。1907年提出马尔科夫链。在19061912年开创了对一种无后效性的随机过程马尔科夫过程的研究。 马尔科夫过程（也称马尔科夫性，无后效性），可以简单地这样表述 给定过程的“现在”，它的“将来”与“过去”无关。,31,32,11 生灭过程及生灭过程排队系统,1. 生灭过程 生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队 模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/C和 M/M/C/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中， 一个新顾客的到达看作“生”，一个顾客服务完之后离开系统看作是 “死”，设N(t)的任意时刻t排队系统的状态（

18、即排队子系统中的总顾客 数），则对M/M/C/K系统N(t)具有有限个状态0，1，,k,对M/M/C来说 N(t)具有可列个状态0，1，2。 一般来说，随机过程 满足以下条件，称为生灭过程： 1) 假设N(t)=n，则从时刻t起到下一个顾客到达时刻为止的时间服 从参数为 的负指数分布，n=0,1,2, 2) 假设N(t)=n，则从时刻t起到下一个顾客离去时刻为止的时间服 从参数为 的负指数分布，n=0,1,2, 3) 同一时刻时只有一个顾客到达或离去。,33,11 生灭过程及生灭过程排队系统,0,1,2,3,34,11 生灭过程及生灭过程排队系统,0,1,2,3,1+p1 =0+p0,35,1

19、1 生灭过程及生灭过程排队系统,0,1,2,3,1+p1 =0+p0,0+p0+2+p2,36,11 生灭过程及生灭过程排队系统,0,1,2,3,1p1 =0p0,0p0+2p2 = (1+1)p1,37,11 生灭过程及生灭过程排队系统,0,1,2,3,1p1 =0p0,0p0+2p2 = (1+1)p1,1p1+3p3 = (2+2)p2, n-2pn-2+npn = (n-1+n-1)pn-1, n-1pn-1+n+1pn+1 = (n+n)pn,p1 =p0 (0/1),p2 = p0 (10)/(2 1),p3 = p0 (21 0)/(3 2 1),pn = p0 (n-1n-2

20、0)/(n n-1 0),pn+1 = p0 (n+1n 0)/(n+1 n 0),38,11 生灭过程及生灭过程排队系统,2. 生灭过程稳态方程,方程为：,由此可求得生灭过程的平稳状态分布：,由于,即有,即有,即有,39,11 生灭过程及生灭过程排队系统,即当,时，此生灭过程存在平稳状态分布：,40,11 生灭过程及生灭过程排队系统,M/M/C和M/M/C/K排队系统，顾客到达间隔服从参数为 的负指数分布，顾客在系统中服务时间服从参数为 的负指数分布，并满足生灭过程的其他条件。它们都是生灭过程的排队系统，我们都可以从生灭过程的平衡方程来推导出这些排队公式。我们以M/M/1系统为例进行推导。在

21、这个系统中，,41,11 生灭过程及生灭过程排队系统,同时也可计算出此系统的其他性能指标:,42,11* 生灭过程及生灭过程排队系统,同样我们也可用生灭过程的平衡方程推导出M/M/1/K系统的公式。 在这个系统中,43,11 生灭过程及生灭过程排队系统,利用上面给出的平稳状态的分布，即可推出此系统的其他性能指标。这些指标我们已经在前面告诉大家了（计算过程从略）。,M / M / 1 / / 设单位时间内顾客的平均到达数为 ，单位时间内平均服务的顾客数为 ( )，则这个排队系统的数量指标公式为: 1、系统中无顾客的概率 P0 =1 / 2、平均排队的顾客数 Lq =2/ ( ),44,2 单服务

22、台泊松到达、负指数服务时间的排队模型,3、系统中的平均顾客数 Ls = Lq + / 4、顾客花在排队上的平均等待时间 Wq = Lq / 5、顾客在系统中的平均逗留时间 Ws = Wq+ 1/ 6、顾客得不到及时服务必须排队等待的概率 Pw = / 7、系统中恰好有 n 个顾客的概率 Pn = ( /)n P0,45,注： / 1。我们称 / 为服务强度。 一般地，在系统达到稳态时，假定平均到达率为 ，平均服务率为 ，则有下面的李特尔(John D. C. Little) 公式： Ls = Ws ， Lq = Wq ， Ws = Wq+ 1/ ， Ls = Lq + / 。,46,这样，只要

23、知道 Ls，Lq，Ws，Wq 四者之一，其余三者就可由李特尔公式求得。另外还有 于是，只要知道 Pn (n = 0, 1, 2)，Ls 或 Lq 就可由上式求得，从而就能求得主要的四项数量指标。,47,例（p310） 某储蓄所只有一个服务窗口。根据统计分析，顾客的到达过程服从泊松分布，平均每小时到达顾客 36人；储蓄所的服务时间服从负指数分布，平均每小时能处理 48 位顾客的业务。试求这个排队系统的数量指标。 解 ：已知 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。,48,P0 =1 / = 10.6/0.8 = 0.25, Lq =2/ ( ) = (0

24、.6)2 / 0.8(0.8 0.6) =2.25 (个顾客), Ls = Lq + / = 2.25+ 0.6/0.8 = 3 (个顾客), 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, 。,49,表 13-1,50,从以上的数据，我们知道储蓄所这个排队系统并不尽人意，到达储蓄所有 75 的概率要排队，排队的长度平均为 2.25 人，排队的平均时间为 3.75 分钟，是平均服务

25、时间 1.25 的 3 倍，而且在储蓄所里有7个或更多的顾客的概率为 13.35，这个概率太高了。 要提高服务水平，减少顾客在系统里的平均逗留时间，即减少顾客的平均排队时间和平均服务,51,时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。 如采取第一种方法，缩短平均服务时间，每小时服务的顾客数由原来的 48人提高到 60人，即每分钟平均服务的顾客数从 0.8 人提高到 1 人，这时 仍然是 0.6， = 1。用前面公式计算得到下表数据:,52,53,如采用第二种方法，再开设一个服务窗口，排队的规则为每个窗口排一队，先到先服务，并假设顾客一旦排了一个队，

26、就不能换到另一个队去。这种处理方法把一个排队系统分成两个排队系统，每个系统中有一个服务台，每个系统的服务率 仍然为 0.8，但到达率由于分流，只有原来的一半， 0.3，这时我们可以求得：,54,如果在第二种方法中把排队规则变一下，在储蓄所里只排一个队，这样的排队系统就变成了 M /M / 2 排队系统。,55,这种排队模型我们记为 M / M / c / / ，这与第二节单服务台的模型的差别，就在于服务台的数量为 c，我们可以把这个模型简记为 M / M / c。 在 M / M / c 模型里，顾客的到达过程为泊松流，每个服务台的服务时间服从同样的负指数分布,56,3 多服务台泊松到达、负指

27、数服务时间的排队模型,排队的长度与顾客的来源都无限制，其排队规则为只排一个队，先到先服务，当其中一个服务台有空时，排在第一个的顾客就上去接受服务。 M / M / c / / 单位时间顾客平均到达数 ， 每个服务台单位时间平均服务顾客数 ， c 。,57,1、系统中无顾客的概率 2、平均排队的顾客数 3、系统中的平均顾客数 Ls = Lq + / , 4、顾客花在排队上的平均等待时间 Wq = Lq / ,58,5、顾客在系统中的平均逗留时间 Ws = Wq+ 1/ , 6、系统中顾客必须排队等待的概率 7、系统中恰好有 n 个顾客的概率,59,当 n c 时，,当 n c 时。,例 在前例的

28、储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是 36 人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理 48 位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。 解： c = 2， 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。,60,P0 = 0.4545, Lq = 0.1227 (个顾客), Ls = Lq + / = 0.8727 (个顾客), Wq = Lq / = 0.2045 (分钟), Ws = Wq+ 1/ = 1.4545 (分钟), Pw =

29、0.2045, P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067， P6 = 0.0040。,61,注： 在储蓄所里使用 M / M / 2 模型与使用两个 M / M / 1 模型，它们的服务台数都是 2，服务率和顾客到达率都一样，只是在 M / M / 2 中只排一队，在 2 个 M / M / 1 中排两队，结果却不一样。 M / M / 2 使得服务水平有了很大提高。如果把 M / M / 2 与原来的一个 M / M / 1 比较，那么服务水平之间的差别就更大了。,62,值得注意，在一般排队模型中 Ls ，

30、 Lq， Ws，Wq 之间都有如下关系： LsLq / ， (13.5) WqLq / ， (13.6 ) Ws = Wq+ 1/ 。 (13.7 ) 对排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为 PN ，则实际进入系统平均到达率应为 (1PN)，这时（13.5）和（13.6）中的 应改写为 (1PN)。,63,我们把一个排队系统的单位时间的总费用 TC 定义为服务机构的单位时间的费用和顾客在排队系统中逗留单位时间的费用之和。即 TC = cw Ls + cs c 其中 cw 为一个顾客在排队系统中逗留单位时间付出的费用；Ls 为在排队系统中的平均顾客数；cs 为每个服务台

31、单位时间的费用；c 为服务台的数目。,64,4 排队系统的经济分析,例 在前两例中，设储蓄所的每个服务台一小时的费用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 元 / 每小时。 通过经济分析知 M / M / 2 系统是一个更为经济的模型。当顾客和服务机构从属于一个单位时，经济分析可取。,65,M / G

32、/ 1 / / 设单位时间顾客平均到达数为 ，单位时间平均服务顾客数为 ，则一个顾客的平均服务时间为 1 /。又设服务时间的均方差为 ，则系统的数量指标公式: 1、系统中无顾客的概率 P0=1 /,66,5 单服务台泊松到达、任意服务时间的排队模型,2、平均排队的顾客数 3、系统中的平均顾客数 Ls = Lq + / 4、顾客花在排队上的平均等待时间 Wq = Lq / 5、系统在中顾客的平均逗留时间 Ws = Wq+ 1/ 6、系统中顾客必须排队等待的概率 Pw = / 7、系统中恰好有 n 个顾客的概率 Pn,67,例1. 某杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，平均到达率

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

34、分钟) , Pw = / = 0.6666。,69,M / D / 1 / / 注：它是 M / G / 1 / / 的特殊情况： = 0。 1、系统中无顾客的概率 P0=1 / 2、平均排队的顾客数,70,6 单服务台泊松到达、定长服务时间的排队模型,3、系统中的平均顾客数 Ls = Lq + / 4、顾客花在排队上的平均等待时间 Wq = Lq / 5、系统在中顾客的平均逗留时间 Ws = Wq+ 1/ 6、系统中顾客必须排队等待的概率 Pw = / 7、系统中恰好有 n 个顾客的概率 Pn,71,例2 . 某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要 6 分钟，到此营业部来冲

35、洗的汽车到达过程服从泊松分布，每小时平均到达 6 辆，试求这个排队系统的数量指标。 解：这是一个 M / D / 1 排队模型，其中 = 6 辆 / 小时， = 60 / 6 =10 辆 / 小时，,72,得 P0 = 1 / = 0.4, Lq = 0.45, Ls = Lq + / = 1.05, Wq = Lq / = 0.0750， Ws = Wq+ 1 / = 0.1750, Pw = / = 0.6。,73,这种排队模型记为 M / G / c / c / ，式中第一位 M 表示到达过程服从泊松分布，第二位 G 表示服务时间的概率分布可以是任意的，第三位 c 表示有 c 个服务台，

36、第四位 c 表示系统里至多能容纳 c 个顾客，顾客排队的长度为有限制 cc = 0，也就是顾客一看服务台都被占了，就走开，不会排队等待服务的，第五位的 表示顾客源无限制。,74,7 多服务台泊松到达、任意的服务时间、损失制排队模型,这种模型是一种损失制模型，它要解决的主要问题是在服务机构的空闲与顾客的流失之间找到平衡，找出最合适的服务台数，使得该系统收益最大。例如民航电话订票系统就是典型的这样的排队模型。如果服务台（接受订票的电话）太少，顾客常常会因为打不通电话而去别的公司订票；如果服务台太多，那么公司将会为服务台的设置付出过多的费用.,75,下面我们给出计算该模型数量指标的一些公式，由于是损

37、失制，故不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间 Wq。 设 仍为平均到达率， 为平均服务率，则系统中的平均顾客数 Ls = / (1 Pc ) （13. 27） 其中 Pc 是系统中恰好有 c 个顾客的概率，也就是系统里 c 个服务台都被顾客占满的概率。,76,系统中恰好有 n 个顾客的概率,77,例3. 某电视商场专营店开展了电话订货业务，电话的到达过程服从泊松分布，平均到达率为每小时 16 个，而一个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化的，但平均每个人每小时可以处理 8 个订货电话。在此电视商场专营店里安装了一台电话自动交换台，它接到电话后

38、可以接到任一个空闲的接话员的电话上，试问该公司应安装多少台接话员的电话，使得订货电话因电话占线而损失的概率不超过 10% 。,78,解：这是一个 M / G / c / c / 模型。当 c =3 时，系统中正好有 3 位顾客的概率为 因为 21.05% 10%，所以不符合要求。,79,当 c = 4 时，系统中正好有 4 位顾客的概率为 因为 9.52% 10%，所以设置四个电话较合适。此时，电话系统里的平均顾客数为,80,Ls = ( / )(1 P4 ) = (16/8) (1 0.0952) =1.81 。 这种形式的更一般形式为 M / G /c / N / ，这个一般形式和 M /

39、 G / c / c / 的区别在于一般形式允许排队，但排队长度不超过 Nc 。 例如，在理发室里为顾客安排一些等侯理发坐的椅子，就属于这种情况。,81,1. c = 1 的情形 设 则有,82,M / M / c / N / 模型,Lq = Ls(1P0 )， e = (1P0 )， Ws = Ls / e ， Wq = Lq / e = Ws1 / 。,83,2. c 1 的情形 设,84,85,Ls = Lq + (1PN )， e = (1PN )， Ws = Ls / e ， Wq = Lq / e = Ws1 / 。,86,M / M / 1 / m / m 模型 前面所介绍的排队

40、系统都是顾客来源无限制的情况，这一节我们将介绍顾客来源有限制的情况。 从 M / M / 1 / m / m 这个记号中我们可以知道这个排队模型的顾客的总数为有限数 m。这时 ：每个顾客在单位时间里到达系统的平均次数 ：一个服务台在单位时间里所服务顾客的平均数,87,8 顾客来源有限制的排队模型,系统的数量指标公式为: 1、系统里无顾客的概率 2、平均排队的顾客数 3、系统里的平均顾客数 Ls = Lq + (1p0),88,4、 顾客在排队上平均花费的等待时间 Wq = Lq / (m Ls) 5、顾客在系统里的平均逗留时间 Ws = Wq+ 1/ 6、系统中有 n 个顾客的概率,89, n

41、 = 0,1,2, , m,例 4. 某车间有 5 台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为 15 分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12 分钟，求该排队系统的数量指标 P0， Lq， Ls， Wq， Ws， P5 。,90,解： 这是一个 M / M / 1 / 5 /5 系统。其中，m = 5, =1/15, = 1/12, / = 0.8 = 0.0073 Lq= 2.766 (台) ; Ls = 3.759 (台)； Wq= 33.43 (分钟);,91,Ws = 45.43 (分钟) ； P5 = 0.2870。 从上面讨论可见，修理工人几

42、乎没有空闲时间，机器排队的时间过长，为了提高服务水平可以提高服务率或增加服务台数目。 以上介绍的排队论模型，都可以使用 “管理运筹学软件” 求解。,92,M / M / c / m / m 模型 前面介绍的顾客来源有限制的排队系统是最简单的情况（M / M / 1 / m / m ），下面我们将介绍顾客来源有限制的一般情况，即 M / M / c / m / m 模型。 从这个记号中我们可以知道这个排队模型的顾客的总数为有限数 m。这时,93,顾客来源有限制的排队模型 (补充), ： 单位时间里顾客平均到达的次数 ：仍为单位时间里平均服务的顾客数 系统的数量指标公式为: 1、系统里无顾客的概率

43、,94,2、系统中有 n 个顾客的概率 3、平均排队的顾客数 4、系统里的平均顾客数,95,5、顾客在排队上平均花费的等待时间 Wq = Lq / (m Ls) 。 6、顾客在系统里的平均逗留时间 Ws = Wq+ 1/ 。 Lq = e Wq ， Ls = e Ws ， Ls = Lq + e / ， e = (m Ls)。,96,5、解：已知 平均到达率 = 10 人/小时， 平均服务率 =（1/3）= 20 人/小时。 从而电话亭前平均排队的顾客数（公式（13.4） 一位顾客花在排队上的平均时间（公式（13.6）,97,P323 习题 5、7、8,因此，去另一个电话亭(平均) 需要在 4

44、+3 = 7 分钟后才能通话，而在本电话亭 (平均) 需要等待 3+3 = 6 分钟后能通话。由此可知，顾客应在原地等候。 如果顾客认为只相差 1 分钟，也可以考虑去另一个电话亭，这时顾客应事先计算一下另一电话亭里没有顾客使用电话的概率（公式（13.3） P0 = 1 / = 110/20 =1/2， 这个概率太大，没有必要去另一个电话亭。,98,7、解：这是一个 M / G / c / c / 模型。 内部一小时平均使用外线电话次数： (30030%)2 + 30070% = 180 +210 = 390 (次)； 外部一小时平均打来电话次数： 602 =120 (次)； 内外部一小时平均共

45、使用交换台次数： 390+120 =510 (次)， 于是， = 510/60 =8.5 次/分钟， =1/3 个/分钟，,99, / = 25.5。 系统中恰好有 n 个顾客的概率（公式（13.26） 在 c 个服务台的系统中恰好有 c 个顾客的概率 求 c 使满足 1Pc 95% 。,100,8、解：这是一个 M / M / c / 10 / 10 模型。 = 1， = 4， cw = 60， cs = 90， TC = cw Ls + cs c 。 a. 当 c = 1 时， TC = 451.2738（元）； 当 c = 2 时， TC = 369.9522（元）； 当 c = 3 时， TC = 405.5552（元）， 故该车间设 2 名修理工，总费用为 369.9522 元 。 b. 当 c = 2 时，Ws = 0.4632（小时） （小时）。,101,