排队论(脱产).ppt

《排队论(脱产).ppt》由会员分享，可在线阅读，更多相关《排队论(脱产).ppt（113页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、排队论排队论(脱产脱产)例某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每小时到达=54人，服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：1.顾客排成一队，依次购票；2.顾客每个窗口排一队，不准串队。考虑:1、售票处空闲的概率；2、顾客在系统中平均等待时间和逗留时间3、系统中平均总顾客数和排队的顾客数。2 排排队队论论(Queuing(Queuing Theory)Theory)，又又称称随随机机服服务务系系统统理理论论(Random(Random Service Service System System Theory),Theory),是是一一门

2、门研研究究拥拥挤挤现现象象(排排队队、等等待待)的的科科学学。具具体体地地说说，它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上，解解决决相相应应排排队队系系统统的的最最优优设设计计和和最优控制问题。最优控制问题。前前 言言3例：上、下班搭乘公共汽车；例：上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病员到医院看病；病员到医院看病；旅客到售票处购买车票；旅客到售票处购买车票；食堂、饭店就餐；食堂、饭店就餐；打电话；打电话；前前 言言4通讯卫星与地面传递信息；通讯卫星与地面传递信息；生生产产线线上上的的原原料料、半半成成品品等等待待加工；加工；因因

3、故故障障停停止止运运转转的的机机器器等等待待工工人修理；人修理；码头的船只等待装卸货物；码头的船只等待装卸货物；要要降降落落的的飞飞机机因因跑跑道道不不空空而而在在空中盘旋等等；空中盘旋等等；防空系统向敌机射击。防空系统向敌机射击。前前 言言5前前 言言一般的排队系统，都可由下图加以描述。61.1.基基 本本 概概 念念 一一 排队系统的描述排队系统的描述 （一）系统特征和基本排队过程（一）系统特征和基本排队过程 实际的排队系统有以下的共同特征：实际的排队系统有以下的共同特征：(1)(1)有请求服务的人或物有请求服务的人或物顾客顾客；(2)(2)有为顾客服务的人或物，即服务员有为顾客服务的人或

4、物，即服务员或或服务台服务台；(3)(3)顾客到达系统的时刻是随机的，为顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，每一位顾客提供服务的时间是随机的，因而整个因而整个排队系统的状态也是随机的排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员客排队较长，而另外一些时候服务员(台台)又空闲无事。又空闲无事。7（二）排队系统的基本组成部分（二）排队系统的基本组成部分 通通常常，排排队队系系统统都都有有输输入入过过程程、服服务务规则和服务台等规则和服务台等3 3个组成部分：个组成部分：1 1输输入入过过程程

5、一一般般可可以以从从3 3个个方方面面来来描述描述个输入过程。个输入过程。(1)(1)顾顾客客总总体体数数，又又称称顾顾客客源源、输输入入源源。这这是是指指顾顾客客的的来来源源。顾顾客客源源可可以以是是有有限限的的，也也可可以以是是无无限限的的。例例如如，到到售售票票处处购购票票的的顾顾客客总总数数可可以以认认为为是是无无限限的的，而而某个工厂因故障待修的机床则是有限的。某个工厂因故障待修的机床则是有限的。1.1.基基 本本 概概 念念8 (2)(2)顾客到达方式顾客到达方式。这是描述。这是描述顾客是怎样来到系统的，他们是顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人单个到达，还是成

6、批到达。病人到医院看病是顾客单个到达的例到医院看病是顾客单个到达的例子。在库存问题中如将生产器材子。在库存问题中如将生产器材进货或产品入库看作是顾客，那进货或产品入库看作是顾客，那么这种顾客则是成批到达的。么这种顾客则是成批到达的。9 (3)(3)顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时，首首先先需需要要确确定定的的指指标标。这这也也可可以以理理解解为为在在一一定定的的时时间间间间隔隔内内到到达达K K个个顾顾客客(K K=1=1、2 2、)的的概概率率是是多多大大。

7、顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流(最最简简单单流流)、爱爱尔尔朗朗分分布等若干种。布等若干种。1.1.基基 本本 概概 念念10 2.2.服服务务规规则则。一一般般可可以以分分为为损损失失制制、等待制和混合制等等待制和混合制等3 3大类。大类。(1)(1)损损失失制制。指指如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用，那那么么他他们们就就自自动动离离开开系系统统永永不不再再来来。例例如如,电电话话拔拔号号后后出出现现忙忙音音，顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电

8、话话，如如要要再再打打，就就需需重重新新拔拔号号，这这种种服服务务规规则则即即为损失制。为损失制。1.1.基基 本本 概概 念念11 (2)(2)等等待待制制。指指当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都都不不空空，顾顾客客加加入入排排队队行行列列等等待待服服务务。例例如如，排排队队等等待待售售票票，故故障障设设备备等等待待维维修修等等。服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如如下下四四种种规则：规则：先先到到先先服服务务。按按顾顾客客到到达达的的先先后后顺顺序序对对顾顾客客进进行行服服务务，是是最最普普遍遍的的情情形。形。后后到到先先服服务务。仓仓库库

9、中中迭迭放放的的钢钢材材，后后迭迭放放上上去去的的都都先先被被领领走走，就就属属于于这这种情况。种情况。1.1.基基 本本 概概 念念12 随随机机服服务务。即即当当服服务务台台空空闲闲时时，不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务，如如电电话话交交换换台台接接通通呼叫电话就是一例。呼叫电话就是一例。优优先先权权服服务务。如如老老人人、儿儿童童先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等，均均属属于于此此种种服服务务规则。规则。1.1.基基 本本

10、概概 念念13 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。1.1.基基 本本 概概 念念14 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库

11、存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。1.1.基基 本本 概概 念念15 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。1.1.基基 本本 概概 念念16 3服务台情况。服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构

12、成形式上看，服务台有：单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。见图1至图5所示。1.1.基基 本本 概概 念念17 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图1 单服务台排队系统服务台数量及构成形式服务台数量及构成形式18图2 单队列S个服务台并联的排队系统图3 S个队列S个服务台的并联排队系统服务台数量及构成形式服务台数量及构成形式19图4 单队多个服务台的串联排队系统图5

13、多队多服务台混联、网络系统服务台数量及构成形式服务台数量及构成形式20 (2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。1.1.基基 本本 概概 念念21（三）排队系统的描述符号与分类（三）排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型

14、的描述，肯道尔（DGKendall）提出了一种目 前 在 排 队 论 中 被 广 泛 采 用 的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F 各符号的意义为：1.1.基基 本本 概概 念念22A表表示示顾顾客客相相继继到到达达间间隔隔时时间间分分布布，常常用用下下列符号：列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。B表表示示服服务务时时间间分分布布，所所用用符符号号与与表表示示顾顾客客到达间隔时间分布相同。到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定

15、长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的随机分布。1.1.基基 本本 概概 念念23C表表示示服服务务台台(员员)个个数数：“1”“1”则则表表示示单单个个服服务务台台，“s s”。(s s1)1)表表示示多多个个服务台。服务台。D表表示示系系统统中中顾顾客客容容量量限限额额；如如系系统统包包括括接接受受服服务务和和等等待待共共有有 k 个个位位子子，则则 s k 00为为一一常常数数，表表示示单单位位时时间间内内到到达达顾顾客客的的平平均均数数，又又称称为为顾顾客的平均到达率。客的平均到达率。2.2.输入过程和服务时间分布输入过程和服务时间分布352.2.输入过程和服务时间分布

16、输入过程和服务时间分布 对对于于泊泊松松流流，不不难难证证明明其其相相继继顾顾客客到到达达时时间间间间隔隔 i i，i i=1,2,=1,2,是是相相互互独独立立同同分分布布的的，其其分分布布函函数数为为负指数分布负指数分布:36 3.爱尔朗输入.这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为 其中k为非负整数。可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：2.2.输入过程和服务时间分布输入过程和服务时间分布37 例某排队系统有并联的k个服务台，顾 客流为泊松流，规定第i,

17、K+i,2K+i个顾客排入第i号台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。此外，爱尔朗分布中，当K1时将化为负指数分布。2.2.输入过程和服务时间分布输入过程和服务时间分布38 4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为：到达时间间隔可能是上述几类输入中的一种。2.2.输入过程和服务时间分布输入过程和服务

18、时间分布39 二、服务时间分布 1定长分布。每一个顾客的服务时间 都是常数，此时服务时间t的分布函数 为：2负指数分布。即各个顾客的服务时间相互独立，具有相同的负指数分布：其中0为一常数，服务时间t的数学期望称为平均服务时间。显然，对于负指数分布2.2.输入过程和服务时间分布输入过程和服务时间分布40 3.爱尔朗分布.即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为 其中0为一常数，此种的平均服务时间为：K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。2.2.输入过程和服务时间分布输入过程和服务时间分布414.一般服务分布。所有顾客的服务时间都是相互独立具有

19、相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。5.多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类型不同6.服务时间依赖于队长的情况。指服务员排队的人愈多，服务的速度也就愈快。2.2.输入过程和服务时间分布输入过程和服务时间分布42 三、排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。(2)统计推断问题，建立适当的排队

20、模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。2.2.输入过程和服务时间分布输入过程和服务时间分布43 (3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的

21、运行指标:2.2.输入过程和服务时间分布输入过程和服务时间分布44 系统中顾客数(队长)的期望值L或Ls；排队等待的顾客数(排队长)的期望值Lq；顾客在系统中全部时间(逗留时间)的期望值W或Ws；顾客排队等待时间的期望值Wq。排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面拟分析几种常见排队系统模型。2.2.输入过程和服务时间分布输入过程和服务时间分布45 对于泊松输入负指数分布服务的排队系统的一般决策过程：根据已知条件绘制状态转移

22、速根据已知条件绘制状态转移速度图。度图。依据状态转移速度图写出各稳依据状态转移速度图写出各稳态概率之间的关系。态概率之间的关系。求出求出 P P0 0 及及 P Pn n。3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型46 计算各项数量运行指标。计算各项数量运行指标。用系统运行指标构造目标用系统运行指标构造目标 函数，对系统进行优化。典型分布 泊松分布及其 性质，负指数分布及其性质泊松 分布(平稳状态）0 为单位 时间平均到达的顾客数 P I=n=n e-/n!(n=0,1,2,)3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型47 负指数分布 为平均服务率，即 单位时间服务

23、的顾客数。P（服务时间 t)=1-e-t t 0 系统状态概率分布及状态转移速 度图 基本的概率分布推导 3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型48状态转移速度图由此图易得：转入率=转出率n=0时，0P0=1P1n一般，n-1Pn-1+n+1Pn+1=(n+n)Pn同样可得下列公式:n=1,2,n-1 nPn=(n-1/n)Pn-1=(i/j)p0 i=0 j=10n123021n-1n1n32n+13 3、泊松输入泊松输入指数服务排队模型指数服务排队模型49系统的运行指标：(稳态时）1.系统中顾客数的期望值：L=KPkk=02.排队等待的顾客数的期望值：Lq=(K-C)Pk

24、kc3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型503.有效到达率e:稳态情况下，单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值即：e=e当系统中有n个顾客时，每单位时间进入系统的顾客平均数为n，每单位时间离开系统的顾客平均数为ne=nPne=nPn3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型514.L,L q,e,W,Wq之间的关系：Little证明了：W=L/e,Wq=Lq/e几何解释：稳态时，一个顾客，进入系统后，每单位时间，平均到达e顾客。eeeee进入时刻离开时刻总时间Ws队长Ls由时间段内个e组成的Ls=eWs3 3、泊松输入泊松输

25、入指数服务排队模型指数服务排队模型52同理：Lq=eWq又W=Wq+（1/）-W与Wq只相差一段平均服务时间1/L=Lq+(e/)3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型53排队论解题要点排队论解题要点w判断排队问题：3方面；wKedall符号描述模型；w参数,(单位一致；顾客数/单位时间)；w绘状态转移速度图，找出pn与p0的关系；w求p0,pn,Ls,Lq,Ws,Wq,e等Little 公式54M/M/1 无限源系统无限源系统稳态概率方程：Pn=(/)Pn-1=(/)nP01n N0N-112N-2N1M/M/1/N/参数，系统状态转移速度：55N由Pn=1 n=0 M/M

26、/1 无限源系统无限源系统 N(/)nP0=1,=/n=0 Pn=1/(N+1)=(1-)n/(1-N+1）NP0=1/n=n=01/(N+1)=(1-)/(1-N+1）56 NL=nPn n=0 M/M/1 无限源系统无限源系统 各计算公式：e=n Pn=(1-PN)+0PN(只有只有 PN 不再进人，故不再进人，故 N=0，其余均为，其余均为)e=nPn=0P0+(1-P0)（同理）W=L/e,Wq=W-(1/),Lq=Wqe57其他指标：损=-e=PNP忙=1-P0,P闲=P0（只有一个服务台）平均服务台忙期的长度T忙，平均服务台闲期的长度T闲，T忙/T闲=P忙/P闲=(1-P0)/P0

27、 T闲=1/(是从一个顾客到下一个顾客到达的平均间隔时间)于是T忙=(1-P0)/P0M/M/1 无限源系统无限源系统58w2.M/M/1/:M/M/1 无限源系统无限源系统稳态概率方程：Pn=（/）Pn-1=(/)nP0令=/0n12n-1当 1时,n不收敛，故应1,n=0即59P0=1/(n)=1-或P0=1-/n=0M/M/1 无限源系统无限源系统Pn=n(1-)或Pn=(/)n(1-/)60M/M/1 无限源系统无限源系统进而：L=n(n-n+1)n=1 =nn-nn+1n=1n=1 =+nn-nn+1n=2n=1=+n+1n=1=+2/(1-)=/(1-)=/(-)(=/)取取出出第

28、第一一项项写成写成 （n+1）n+1 n=1 与后一项合并与后一项合并61这里:e=(1-P0)=W=L/e=1/（-）Wq=W-1/=/(-)Lq=Wq=2/(-)3.损失制M/M/1/1:顾客到达若服务台被占用立即离开。M/M/1 无限源系统无限源系统62P1=/（+）P损=P忙=P1=/（+）P闲=P0=/（+）M/M/1 无限源系统无限源系统直接可得：P0=(1-)/(1-)2=1/(1+)=/(+)P0+P1=1631.M/M/C/NM/M/C 无限源系统无限源系统0N-112N-2c2cNCC-1ccC+13(c-1)cc稳态概率应满足的关系：当nc时，Pn=/(n)Pn-1当nc

29、时，Pn=/(c)Pn-1令=/（c）系统负荷强度系数64c/nPn-1=cn/nnP0n的情形=/(c)1时，不收敛，设1,M/M/C 无限源系统无限源系统c-1 P0=c n/nn+c c/c(c/1-)-1 n=067(cn/n!)nP0nc(cc/c!)nP0n cM/M/C 无限源系统无限源系统Pn=Lq=ccc+1P0/c!(1-)2e=Wq=Lq/W=Wq+1/L=W=Lq+/683.M/M/C损失制系统（M/M/C/C/）此即M/M/C/N中N=C的情形 M/M/C 无限源系统无限源系统 cP0=cn/n!n-1n=0Pn=cn/n!nP0e=(1-Pc)Lq=0,Wq=0(不

30、等待)W=1/L=eW=e/=(/)(1-Pc)损=-e=Pc69例例6.1:某某车车站站售售票票处处有有三三个个窗窗口口，同同时时售售各各车车次次的的车车票票。顾顾客客到到达达服服从从泊泊松松分分布布，平平均均每每分分钟钟到到达达=0.9（人人），服服务务时时间间服服从从负负指指数数分分布布，平平均均服服务务率率=24（人（人/h），分两种情况：），分两种情况：1.顾客排成一队，依次购票；顾客排成一队，依次购票；2.顾客每个窗口排一队，不准串队。顾客每个窗口排一队，不准串队。求求:（1）售票处空闲的概率。）售票处空闲的概率。（2）平均等待时间和逗留时间。）平均等待时间和逗留时间。（3）队长和

31、队列长。）队长和队列长。例例 题题 解解 析析70例例 题题 解解 析析w稳态概率：w当当n n33时时 P Pn n=/（nn）P Pn n-1-1=(=(n n/n/n!)!)n nP P0 0w =3=3n n/n/n!n nP P0 0 w当当n n3 3时时 P Pn n=/（cc）P Pn n-1-1=(3=(33 3/3!)/3!)n nP P0 0w =4.5=4.5n nP P0 0 解：解：1.M/M/3/031232343单位应相同：单位应相同：=0.4（人/分钟）记记=/（3）=0.9/(0.4*3)=0.75=0.9/(0.4*3)=0.7571例例 题题 解解 析析

32、P0+3*0.75P0+4.5*0.752P0+4.5n P0=1n=3由Pn=1 n=0 P0=1/(1+2.25+2.53125+4.53/(1-)=1/13.375=0.0748P1=0.1683P2=0.1893Lq=(n-c)Pn=33/3!4P0(n-3)n-3-1 n=c+1 n=472例例 题题 解解 析析S=dF/d=(1-)+/(1-)2于是：Lq=4.54P0/(1-)2=1.704 e=Wq=Lq/e=1.704/0.9=1.893分钟F=Sd=(n-3)n-3-1d=n-3 n=4 n=4=/(1-)S=(n-3)n-3-1 n=4 73例例 题题 解解 析析Ws=W

33、q+1/=1.893+2.5=4.393分钟Ls=Ws=3.954故：售票处的空闲的概率为0.0748平均等待时间 Wq=1.893分钟，平均逗留时间 W=4.393分钟队长 Ls=3.954(人)Lq=1.704(人)74 2.M/M/1/三个系统并联：=0.3 =0.4 =/=0.75P0=1-=0.25 三 个 服 务 台 都 有 空 的 时 候，P03=0.0156Ls=/(1-)=3 e=0.3Lq=Ls-/=2.25Ws=Ls/=10Wq=Ws-1/=7.5例例 题题 解解 析析75故售票处空闲的概率为 0.0156例例 题题 解解 析析平均等待时间 Wq=7.5分钟 平均逗留时间

34、 Ws=10分钟队长 Ls=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75（人）相比之下，排一队共享三个服务台效率好。76顾客源有限的排队系统顾客源有限的排队系统 1.1.M/M/1/M/M/1/m/m系统系统 顾客源是顾客源是m个，那么系统容量实质上个，那么系统容量实质上 最多有最多有m个足够。个足够。0m-112m-2m(m-1)2m(m-2)3顾客源中剩余的顾客数乘以每个顾客到达的概率77顾客源有限的排队系统顾客源有限的排队系统Pn=m-(n-1)/Pn-1 1 n m反复推得：反复推得：Pn=m!/(m-n)!(/)nP0 1 n m m代入代入Pn=1 n=0mwm!

35、/(m-n)!(/)nP0=1w n=0mwP0=m!/(m-n)!(/)n-1w n=078顾客源有限的排队系统顾客源有限的排队系统mPn=m!/(m-n)!(/)nm!/(m-k)!(/)k-1k=0由(m-L)=(1-P0)得L=m-/(1-P0)W=L/eWq=W-1/Lq=Wqewe=(m-L)m mee=nPnnPn=(m-nm-n)P Pn n n n=0 =0 n n=0=0 m mm m =(m Pm Pn n-n Pn Pn n)n n=0 =0 n n=0=0e=(1-P0)79w2.M/M/c/m/m系统顾客源有限的排队系统顾客源有限的排队系统0m-112m-2m(m-

36、1)2c2cmCC-1(m(c-1)c顾客源还有m-(c-1)个顾客每个顾客可到达的概率稳态概率方程Pn=(m-n+1)/nPn-1nc(m-n+1)/cPn-1cn m80m代入Pn=1得(整理后)n=0顾客源有限的排队系统顾客源有限的排队系统反复代入得：Pn=m!/n!(m-n)!(/)nP0ncm!/c!(m-n)!cn-c(/)nP0cnmc mwP0=m!/(m-n)!(/)n+m!/(c!(m-n)!wn=0n=c+1wcn-c)(/)n-181于是可得：mLq=(n-c)Pnn=c+1e=(m-L)顾客源有限的排队系统顾客源有限的排队系统又L=Lq+e/=Lq+/(m-L)整理得

37、：L=(L+/m)/(1+/)Wq=Lq/e,W=L/e82应应 用用 举举 例例 例6.2:某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达18辆汽车。若加油站中已有K辆车，当K2时，有K/6的顾客将自动离去。加油时间服从负指数分布，平均每辆车需要5分钟。试求：非标准的M/M/2/N模型83应应 用用 举举 例例 （1）系统空闲的概率为多少？P0 （2）求系统满的概率是多少？P6 （3）求系统服务台不空的概率 P2+P3+P4+P5+P6=1-P0-P1 （4）若服务一个顾客,加油站可以获 得利润10元,问平均每小时可获 得

38、利润为多少元？10e （5）求每小时损失掉的顾客数？损=-e （6）加油站平均有多少辆车在等待加 油？Lq 平均有多少个车位被占用？L （7）进入加油站的顾客需要等多长的 时间才能开始加油？Wq 进入加油站的顾 客需要多长时间才能离去？W 84稳态概率关系：P1=/P0=1.5P0=(3/2)P0P2=/(2)P1=0.75*1.5P0=(9/8)P0应应 用用 举举 例例 解：状态转移速度图 以小时为单位=18 =60/5=12222205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)85应应 用用 举举 例例P3=(4/6)/(2)P2=(1/2)(9/8)P0=(9

39、/16)P0P4=(3/6)/(2)P3=(3/8)(9/16)P0=(27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0=(27/512)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0=(27/4096)P0由P0+P1+P2+P3+P4+P5+P6=1解得：P0=0.22433 P1 P2 P3 P4 P5 P60.33649 0.25237 0.12618 0.04732 0.01183 0.0014886运行指标：(1)P0=0.22433(2)P6=0.00148(3)P忙=1-P0-P1=0.43918(4)e=0P0+P1+2(P2+

40、P3+P4+P5+P6)=14.578（辆/h）10e=145.78(元/小时）应应 用用 举举 例例87(5)损=-e =18-14.5782 =3.4218（辆/h）应应 用用 举举 例例(6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 =0.26223 L=Lq+e/=0.26223+1.21485 =1.4770888应应 用用 举举 例例(7)Wq=Lq/e =0.018h =1.08分钟 W=Wq+1/=0.101h =6.08分钟89 例6.3:某车站候车室在某段时间旅客到达服从泊松流分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布

41、，平均停留时间为0.5h，问候车室内平均人数为多少？（L)应应 用用 举举 例例解解：把把旅旅客客停停留留在在候候车车室室看看做做服服务务，于是系统为于是系统为M/M/=50 =1/0.5=290稳态概率关系：Pn=/(n)Pn-1=.=1/n!(/)nP0 记记=/=50/2=25 应应 用用 举举 例例0n12n-1n2(n+1)n+13(n-1)(n+2)状态转移速度图:91应应 用用 举举 例例P0=(1/n!n)-1=e-n=0 L=nPn n=1 =e-1/(n-1)!n n=1 =e-1/n!n=25(人人)n=0 代入代入 Pn=1 n=092 4.4.排队系统的优化目标排队系

42、统的优化目标 与最优化问题与最优化问题 完完全全消消除除排排队队现现象象是是不不现现实实的的，那那会会造造成成服服务务人人员员和和设设施施的的严严重重浪浪费费，但但是是设设施施的的不不足足和和低低水水平平的的服服务务，又又将将引引起起太太多多的等待，从而导致生产和社会性损失。的等待，从而导致生产和社会性损失。从从经经济济角角度度考考虑虑，排排队队系系统统的的费费用用应应该该包包含含以以下下两两个个方方面面：一一个个是是服服务务费费用用，它它是是服服务务水水平平的的递递增增函函数数；另另一一个个是是顾顾客客等等待待的的机机会会损损失失(费费用用)，它它是是服服务务水水平平的的递减函数递减函数。两

43、者的总和呈一条。两者的总和呈一条U U形曲线形曲线。93 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系系统统最最优优化化的的目目标标是是寻寻求求U U曲曲线线的的最最小小点点。这这种种意意义义下下，排排队队系系统统的的最最优优化化问问题题通通常常分分为为两两类类：一一类类称称之之系系统统的的静静态态最最优优设设计计，目目的的在在于于使使设设备备达达到到最最大大效效益益，或或者者说说，在在保保证证一一定定服服务务质质量量指指标标的的前前题题下下，要要求求机机构构最最为为经经济济；另另一一类类叫叫作作系系统统动动态态最最优优运运营营，是是指指一一个个给给定定排排队队系

44、系统统，如如何何运运营营可可使使某某个个目目标标函函数数得得到到最最优优。归归纳纳起起来来，排排队队系系统统常常见见的优化问题在于：的优化问题在于：94 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题(1)(1)确定最优服务率确定最优服务率*；(2)(2)确定最佳服务台数量确定最佳服务台数量s s*；(3)(3)选择最为合适的服务规则；选择最为合适的服务规则；(4)(4)确定上述几个量的最优组合。确定上述几个量的最优组合。本本节节仅仅就就，s s这这两两个个决决策策变变量量的的分分别别单单独独优优化化，介介绍绍两两个个较较简简单单的的模模型型，以以便便读读者者了了解解排

45、排队队系系统统优优化化设设计计的的基基本本思想。思想。95 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题一一、MM1 系系统统的的最最优优平平均均服服务务率率*:设设C1当当 =1时时服服务务系系统统单单位位时时间间的的平平均均费用费用Cw平平均均每每个个顾顾客客在在系系统统逗逗留留单单位位时时间的损失；间的损失；y整个系统单位时间的平均总费用。整个系统单位时间的平均总费用。其中其中C1，Cw均为可知。则目标函数为均为可知。则目标函数为 (6-52)96 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题将将L=(-)，代入上式，得，代入上式，得易

46、见易见y是关于决策变量是关于决策变量 的一元非线性函数的一元非线性函数由一阶条件由一阶条件解得驻点解得驻点 (6-53)(6-53)97 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 根根号号前前取取正正号号是是为为了了保保证证 。这这样样，系系统统才才能能达达到到稳稳态态。又又由由二阶条件二阶条件(因因 ）可可知知(6-53)给给出出的的*为为(,)上上的的全全局局唯唯一一最最小小点点。将将*代代入入(6-52)中中，可可得得最最小小总总平均费用平均费用（6-54）98 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 另另外外，若若设设cw为

47、为平平均均每每个个顾顾客客在在队队列列中中等待单位时间的损失，则需用等待单位时间的损失，则需用取取代代式式(6-52)中中的的L，这这时时类类似似可可得得一一阶阶条件：条件：这这是是一一个个关关于于 的的四四次次方方程程，一一般般采采用数值法用数值法(如牛顿法如牛顿法)确定其根确定其根*。99 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题二、二、M/M/s/系统的最优服务台数系统的最优服务台数 s*设目标函数为设目标函数为 (6-55)其中：其中：s 并联服务台的个数并联服务台的个数(待定待定)；f(s)整整个个系系统统单单位位时时间间的的平平均均总总费费用，它是关于

48、服务台数用，它是关于服务台数 s 的函数；的函数；c2平均每个服务台的单位时间费用；平均每个服务台的单位时间费用；100cw平平均均每每个个顾顾客客在在系系统统中中逗逗留留(或或等等待待)单位时间的损失；单位时间的损失；L(s)平平均均队队长长(或或平平均均等等待待队队长长)，它它是关于服务台数是关于服务台数 s 的函数；的函数；要要确确定定最最优优服服务务台台数数 s*1，2，使使 由由于于s取取值值离离散散，不不能能采采用用微微分分法法或或非非线线性性规规划划的的方方法法，因因此此我我们们采采用用差差分分法法。显然有显然有 （6-56）101 4.4.排队系统的优化目标排队系统的优化目标

49、与最优化问题与最优化问题把式（把式（6-55）代人式）代人式(6-56)中，得中，得可得可得令令 (6-57)依依次次计计算算 s=1，2，时时的的L(s)值值及及每每一一差差值值 L(s)-L(s+1)，根根据据 落落在在哪哪两两个个差差值之间就可确定值之间就可确定 s*。102例例6.4:兴兴建建一一座座港港口口码码头头，只只有有一一个个装装卸卸船船只只的的泊泊位位。要要求求设设计计装装卸卸能能力力。装装卸卸能能力力单单位位为为（只只/日日）船船数数。已已知知：单单位位装装卸卸能能力力的的平平均均生生产产费费用用a=2千千元元，船船只只逗逗留留每每日日损损失失b=1.5千千元元。船船只只到

50、到达达服服从从泊泊松松分分布布，平平均均速速率率=3只只/日日。船船只只装装卸卸时时间间服服从从负负指指数分布。目标是每日总支出最少。数分布。目标是每日总支出最少。应应 用用 举举 例例103解：解：=3,待定待定 模型模型 M/M/1/队长队长 Ls=/(-)总费用总费用 C=a+bLs=a+b/(-)求极值（最小值）求极值（最小值）求导求导 d C/d=a+(-b)/(-)2=0应应 用用 举举 例例得得:-=(b/a)1/2（根据题意舍负）（根据题意舍负）所以所以=+(b/a)1/2=3+(2.25)1/2=4.5(只只/日日)104例例6.4:建建造造一一口口码码头头，要要求求设设计计