排队论(脱产).ppt课件.ppt

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

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

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

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

5、台等规则和服务台等3 3个组成部分：个组成部分：1 1输入过程输入过程一般可以从一般可以从3 3个方面来个方面来描述描述个输入过程。个输入过程。(1)(1)顾客总体数顾客总体数，又称顾客源、输入源。，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。某个工厂因故障待修的机床则是有限的。1.1.基基 本本 概概 念念9 (2)(2)顾客到达方式顾客到达方式。这是描述。这是描述顾客是怎样来到

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

7、定的时间间隔内到达K K个顾客个顾客(K K=1=1、2 2、)的概率是多大。顾客的概率是多大。顾客流的概率分布一般有定长分布、二项流的概率分布一般有定长分布、二项分布、泊松流分布、泊松流(最简单流最简单流)、爱尔朗分、爱尔朗分布等若干种。布等若干种。1.1.基基 本本 概概 念念11 2.2.服务规则服务规则。一般可以分为损失制、。一般可以分为损失制、等待制和混合制等等待制和混合制等3 3大类。大类。(1)(1)损失制损失制。指如果顾客到达排队系。指如果顾客到达排队系统时，所有服务台都已被先来的顾客统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不占用，那么他们就自动离开系统永

8、不再来。例如再来。例如,电话拔号后出现忙音，顾电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即打，就需重新拔号，这种服务规则即为损失制。为损失制。1.1.基基 本本 概概 念念12 (2)(2)等待制等待制。指当顾客来到系统。指当顾客来到系统时，所有服务台都不空，顾客加入排时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售队行列等待服务。例如，排队等待售票，故障设备等待维修等。服务台在票，故障设备等待维修等。服务台在选择顾客进行服务时，常有如下四种选择顾客进行服务时，常有如下四种规则：规则：先到先服务先到先服务

9、。按顾客到达的先后。按顾客到达的先后顺序对顾客进行服务，是最普遍的情顺序对顾客进行服务，是最普遍的情形。形。后到先服务后到先服务。仓库中迭放的钢材，。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这后迭放上去的都先被领走，就属于这种情况。种情况。1.1.基基 本本 概概 念念13 随机服务随机服务。即当服务台空闲时，。即当服务台空闲时，不按照排队序列而随意指定某个顾不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通客去接受服务，如电话交换台接通呼叫电话就是一例。呼叫电话就是一例。优先权服务优先权服务。如老人、儿童先。如老人、儿童先进车站；危重病员先就诊；遇到重进车站；危重病员先就诊

10、；遇到重要数据需要处理计算机立即中断其要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务他数据的处理等，均属于此种服务规则。规则。1.1.基基 本本 概概 念念14 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。1.1.基

11、基 本本 概概 念念15 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。1.1.基基 本本 概概 念念16 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待

12、制。1.1.基基 本本 概概 念念17 3服务台情况。服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。见图1至图5所示。1.1.基基 本本 概概 念念18 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图1 单服务台排队系统服务台数量及构成形式服务台数量及构成形式1

13、9图2 单队列S个服务台并联的排队系统图3 S个队列S个服务台的并联排队系统服务台数量及构成形式服务台数量及构成形式20图4 单队多个服务台的串联排队系统 图5 多队多服务台混联、网络系统服务台数量及构成形式服务台数量及构成形式21 (2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。1.1.基基 本本 概概 念念（三）排队系统的描述符号与分

14、类（三）排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目 前 在 排 队 论 中 被 广 泛 采 用 的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F 各符号的意义为：1.1.基基 本本 概概 念念A表示顾客相继到达间隔时间分布，常用下表示顾客相继到达间隔时间分布，常用下列符号：列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。B表示

15、服务时间分布，所用符号与表示顾客表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的随机分布。1.1.基基 本本 概概 念念C表示服务台表示服务台(员员)个数：个数：“1”1”则表则表示单个服务台，示单个服务台，“s s”。(s s1)1)表示表示多个服务台。多个服务台。D表示系统中顾客容量限额；如系统表示系统中顾客容量限额；如系统包括接受服务和等待共有包括接受服务和等待共有 k 个位子，个位子，则则 s k 00为一常数，表示单位为一常数，表示单位时间内到达顾客的平

16、均数，又称为顾时间内到达顾客的平均数，又称为顾客的平均到达率。客的平均到达率。!)()(KtetVKtk,2,1,0K 2.2.输入过程和服务时间分布输入过程和服务时间分布362.2.输入过程和服务时间分布输入过程和服务时间分布 对于泊松流，不难证明其相继对于泊松流，不难证明其相继顾客到达时间间隔顾客到达时间间隔 i i，i i=1,2,=1,2,是是相互独立同分布的，其分布函数为相互独立同分布的，其分布函数为负指数分布负指数分布:0,00,1)(ttetFti),2,1(i37 3.爱尔朗输入.这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为 其中k为非负整数。可以证明，在参

17、数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：0)!1()()(1teKttatK)(21kkkTT2.2.输入过程和服务时间分布输入过程和服务时间分布38 例某排队系统有并联的k个服务台，顾 客流为泊松流，规定第i,K+i,2K+i个顾客排入第i号台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。此外，爱尔朗分布中，当K1时将化为负指数分布。0)!1()()(1teKttatK2.2.输入过程和服务时间分布输入过程和服务时间

18、分布39 4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为：到达时间间隔可能是上述几类输入中的一种。2.2.输入过程和服务时间分布输入过程和服务时间分布kaknP,2,1,0K40 二、服务时间分布 1定长分布。每一个顾客的服务时间 都是常数，此时服务时间t的分布函数 为：2负指数分布。即各个顾客的服务时间相互独立，具有相同的负指数分布：其中0为一常数，服务时间t的数学期望称为平均服务时间。显然，

19、对于负指数分布2.2.输入过程和服务时间分布输入过程和服务时间分布xxxtPxB01)()(0,00,1)(xxexBx41 3.爱尔朗分布.即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为 其中0为一常数，此种的平均服务时间为：K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。2.2.输入过程和服务时间分布输入过程和服务时间分布001)()(dxxexxdBtEmx0,)!1()()(1xekxkkxbxkk01)()(dxxxbtE424.一般服务分布。所有顾客的服务时间都是相互独立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一

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

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

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

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

24、态转移速 度图 基本的概率分布推导 3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型49状态转移速度图由此图易得：转入率=转出率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、泊松输入泊松输入指数服务排队模型指数服务排队模型50系统的运行指标：(稳态时）1.系统中顾客数的期望值：L=KPk k=0 2.排队等待的顾客数的期望值：Lq=(K-C)Pk kc3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型51

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

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

27、(/)nP0=1,=/n=0 Pn=1/(N+1)=(1-)n/(1-N+1）NP0=1/n=n=01/(N+1)=(1-)/(1-N+1）57 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=Wqe58 其他指标：损=-e=PN P忙=1-P0,P闲=P0 （只有一个服务台）平均服务台忙期的长度 T忙，平均服务台闲期的长度 T闲，T忙/T闲=P忙/P闲=(1-P0)/P0 T闲=1/(是从一

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

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

30、n)Pn-1当nc时，Pn=/(c)Pn-1 令=/（c）系统负荷强度系数65 c/nPn-1=cn/nnP0 n的情形=/(c)1时，不收敛，设1,M/M/C 无限源系统无限源系统 c-1 P0=c n/nn+c c/c(c/1-)-1 n=068 (cn/n!)nP0 nc (cc/c!)nP0 n c M/M/C 无限源系统无限源系统Pn=Lq=ccc+1P0/c!(1-)2e=Wq=Lq/W=Wq+1/L=W=Lq+/69 3.M/M/C 损失制系统（M/M/C/C/）此即M/M/C/N中 N=C 的情形 M/M/C 无限源系统无限源系统 c P0=cn/n!n-1 n=0 Pn=cn

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

32、均等待时间和逗留时间。）平均等待时间和逗留时间。（3）队长和队列长。）队长和队列长。例例 题题 解解 析析71例例 题题 解解 析析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=0.9/(0.

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

34、4 =/(1-)S=(n-3)n-3-1 n=4 74例例 题题 解解 析析Ws=Wq+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(人)75 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例例 题题 解解 析析76故售票处空闲的概

35、率为 0.0156例例 题题 解解 析析平均等待时间 Wq=7.5分钟 平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75（人）相比之下，排一队共享三个服务台效率好。77顾客源有限的排队系统顾客源有限的排队系统 1.1.M/M/1/M/M/1/m/m系统系统 顾客源是顾客源是m个，那么系统容量实质上个，那么系统容量实质上 最多有最多有m个足够。个足够。0m-112m-2m(m-1)2m(m-2)3顾客源中剩余的顾客数乘以每个顾客到达的概率78顾客源有限的排队系统顾客源有限的排队系统Pn=m-(n-1)/Pn-1 1 n m反复推得：反复推得：

36、Pn=m!/(m-n)!(/)nP0 1 n m m 代入代入Pn=1 n=0 mw m!/(m-n)!(/)nP0=1w n=0 mw P0=m!/(m-n)!(/)n-1w n=079顾客源有限的排队系统顾客源有限的排队系统 mPn=m!/(m-n)!(/)nm!/(m-k)!(/)k-1 k=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

37、)80w 2.M/M/c/m/m系统顾客源有限的排队系统顾客源有限的排队系统0m-112m-2m(m-1)2c2cmCC-1(m(c-1)c顾客源还有m-(c-1)个顾客每个顾客可到达的概率稳态概率方程Pn=(m-n+1)/nPn-1 nc(m-n+1)/cPn-1 cn m81 m代入 Pn=1 得(整理后)n=0顾客源有限的排队系统顾客源有限的排队系统反复代入得：Pn=m!/n!(m-n)!(/)nP0 ncm!/c!(m-n)!cn-c(/)nP0 cnm c mw P0=m!/(m-n)!(/)n+m!/(c!(m-n)!w n=0 n=c+1w cn-c)(/)n-182于是可得：m

38、Lq=(n-c)Pn n=c+1e=(m-L)顾客源有限的排队系统顾客源有限的排队系统又 L=Lq+e/=Lq+/(m-L)整理得：L=(L+/m)/(1+/)Wq=Lq/e,W=L/e83应应 用用 举举 例例 例6.2:某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达18辆汽车。若加油站中已有K辆车，当K2时，有K/6的顾客将自动离去。加油时间服从负指数分布，平均每辆车需要5分钟。试求：非标准的M/M/2/N模型84应应 用用 举举 例例 （1）系统空闲的概率为多少？P0 （2）求系统满的概率是多少？P6 （3）求系统服务

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

40、6)(1-3/6)(1-4/6)(1-5/6)应应 用用 举举 例例P3=(4/6)/(2)P2=(1/2)(9/8)P0=(9/16)P0 P4=(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.0014887运行指

41、标：(1)P0=0.22433(2)P6=0.00148(3)P忙=1-P0-P1=0.43918(4)e=0P0+P1+2(P2+P3+P4+P5+P6)=14.578（辆/h）10e=145.78(元/小时）应应 用用 举举 例例88(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.4770889应应 用用 举举 例例(7)Wq=Lq/e =0.018h =1.08分钟 W=Wq+1/=0.101h =6.0

42、8分钟90 例6.3:某车站候车室在某段时间旅客到达服从泊松流分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5h，问候车室内平均人数为多少？（L)应应 用用 举举 例例解：把旅客停留在候车室看做服务，解：把旅客停留在候车室看做服务，于是系统为于是系统为M/M/=50 =1/0.5=291稳态概率关系：Pn=/(n)Pn-1=.=1/n!(/)nP0 记记=/=50/2=25 应应 用用 举举 例例0n12n-1n2(n+1)n+13(n-1)(n+2)状态转移速度图:92应应 用用 举举 例例 P0=(1/n!n)-1=e-n=0 L=nPn n=1

43、 =e-1/(n-1)!n n=1 =e-1/n!n=25(人人)n=0 代入代入 Pn=1 n=0 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 完全消除排队现象是不现实的，那会完全消除排队现象是不现实的，那会造成服务人员和设施的严重浪费，但是设造成服务人员和设施的严重浪费，但是设施的不足和低水平的服务，又将引起太多施的不足和低水平的服务，又将引起太多的等待，从而导致生产和社会性损失。的等待，从而导致生产和社会性损失。从经济角度考虑，排队系统的费用应从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是该包含以下两个方面：一个是服务费用服务费用，它是服务水平的它

44、是服务水平的递增函数递增函数；另一个是顾客；另一个是顾客等待的等待的机会损失机会损失(费用费用)，它是服务水平的，它是服务水平的递减函数递减函数。两者的总和呈一条。两者的总和呈一条U U形曲线形曲线。4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系统最优化的目标是寻求系统最优化的目标是寻求U U曲线的最曲线的最小点。这种意义下，排队系统的最优化小点。这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备达到最大态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服务质量指效益，或者说，在保证一定

45、服务质量指标的前题下，要求机构最为经济；另一标的前题下，要求机构最为经济；另一类叫作系统动态最优运营，是指一个给类叫作系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函定排队系统，如何运营可使某个目标函数得到最优。归纳起来，排队系统常见数得到最优。归纳起来，排队系统常见的优化问题在于：的优化问题在于：4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题(1)(1)确定最优服务率确定最优服务率*；(2)(2)确定最佳服务台数量确定最佳服务台数量s s*；(3)(3)选择最为合适的服务规则；选择最为合适的服务规则；(4)(4)确定上述几个量的最优组合。确定上述几个量的

46、最优组合。本节仅就本节仅就，s s这两个决策变量的分这两个决策变量的分别单独优化，介绍两个较简单的模型，别单独优化，介绍两个较简单的模型，以便读者了解排队系统优化设计的基本以便读者了解排队系统优化设计的基本思想。思想。4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题一、一、MM1 系统的最优平均服务系统的最优平均服务率率*:设设C1当当 =1时服务系统单位时间的平时服务系统单位时间的平均费用均费用Cw平均每个顾客在系统逗留单位时平均每个顾客在系统逗留单位时间的损失；间的损失；y整个系统单位时间的平均总费用。整个系统单位时间的平均总费用。其中其中C1，Cw均为可知。则目标函

47、数为均为可知。则目标函数为 (6-52)Lccyw1 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题将将L=(-)，代入上式，得，代入上式，得易见易见y是关于决策变量是关于决策变量 的一元非线性函数的一元非线性函数由一阶条件由一阶条件解得驻点解得驻点 (6-53)(6-53)11wccy0)(121wccddy1*/ccw 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 根号前取正号是为了保证根号前取正号是为了保证 。这样，系统才能达到稳态。又。这样，系统才能达到稳态。又由二阶条件由二阶条件(因因 ）可知可知(6-53)给出的给出的*为为(,)上

48、的全局唯一上的全局唯一最小点。将最小点。将*代入代入(6-52)中，可得最小总中，可得最小总平均费用平均费用0)(2322wcdydwcccy11*2（6-54）4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 另外，若设另外，若设cw为平均每个顾客在队列中为平均每个顾客在队列中等待单位时间的损失，则需用等待单位时间的损失，则需用取代式取代式(6-52)中的中的L，这时类似可得一阶，这时类似可得一阶条件：条件：这是一个关于这是一个关于 的四次方程，一般采的四次方程，一般采用数值法用数值法(如牛顿法如牛顿法)确定其根确定其根*。)(2qL022322213141wwcccc

49、c 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题二、二、M/M/s/系统的最优服务台数系统的最优服务台数 s*设目标函数为设目标函数为 (6-55)其中：其中：s 并联服务台的个数并联服务台的个数(待定待定)；f(s)整个系统单位时间的平均总费整个系统单位时间的平均总费用，它是关于服务台数用，它是关于服务台数 s 的函数；的函数；c2平均每个服务台的单位时间费用；平均每个服务台的单位时间费用；)()(2sLcscsfwcw平均每个顾客在系统中逗留平均每个顾客在系统中逗留(或等或等待待)单位时间的损失；单位时间的损失；L(s)平均队长平均队长(或平均等待队长或平均等待队

50、长)，它，它是关于服务台数是关于服务台数 s 的函数；的函数；要确定最优服务台数要确定最优服务台数 s*1，2，使使 由于由于s取值离散，不能采用微分法或非取值离散，不能采用微分法或非线性规划的方法，因此我们采用差分法。线性规划的方法，因此我们采用差分法。显然有显然有 （6-56）)()(min)(2*sLcscsfsfw)1()()1()(*sfsfsfsf 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题把式（把式（6-55）代人式）代人式(6-56)中，得中，得可得可得令令 (6-57)依次计算依次计算 s=1，2，时的时的L(s)值及每值及每一差值一差值 L(s)