排队论及其模型

1、1运筹学运筹学2排队论排队论也称随机服务系统理论(Random Service System Theory)，是为研究和解决具有拥挤现象的问题而发展起来的一门应用数学的分支。 具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。3排队论排队论 排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。4排队论排队论 研究内容包括三个部分：n (1) (1) 排队系统的性态问题排队系统的性态问题

2、n (2) (2) 排队系统的最优化问题排队系统的最优化问题n (3) (3) 排队系统的统计推断问题排队系统的统计推断问题性态问题，即研究各种排队系统的概率规性态问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和律性，主要研究队长分布、等待时间分布和忙期分布等。忙期分布等。最优化，又分静态最优和动态最优，前者最优化，又分静态最优和动态最优，前者指最优设计，后者指现有排队系统的最优运指最优设计，后者指现有排队系统的最优运营。营。统计推断，即判断一个给定的排队系统符统计推断，即判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。合哪种模型，以便根据排队理论进行研究。

3、解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理，研究设计改进措施等。5排队论排队论n第1节 基本概念n第2节 到达间隔的分布和服务时间的分布n第3节 单服务台负指数分布排队系统的分析n第4节 多服务台负指数分布排队系统的分析n第5节 一般服务时间M/G/1模型n第6节 经济分析系统的最优化n第7节 分析排队系统的随机模拟法6第第1节节 基基 本本 概概 念念 v1.1 排队过程的一般表示v1.2 排队系统的组织和特征v1.3 排队模型的分类v1.4 排队问题的求解7 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统

4、、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。1.1 排队过程的一般表示排队过程的一般表示81.1 排队过程的一般表示排队过程的一般表示v各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。v排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队过程的一般模型排队过程的一般模型91.1 排队过程的一般表示排队过程的一般表示到达的顾客到达的顾客要求服务内容要求服务内容服务机构服务机构1.不能运转的机器2.修理

5、技工3.病人4.电话呼唤5.文件稿6.提货单7.到达机场上空的飞机8.驶入港口的货船9.上游河水进入水库10.进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装(卸)货装(卸)放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库管理员跑道货码头(泊位)水闸管理员我方高射炮形形色色的排队系统 10 实际的排队系统虽然千差万别，但是它们 有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的

6、。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。1.2 排队系统的组成和特征排队系统的组成和特征 111.2 排队系统的组成和特征排队系统的组成和特征 v排队系统由三个基本部分组成： 输入过程输入过程 排队规则排队规则 服务机构服务机构121.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程v输入即指顾客到达排队系统。输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。v一般可以从以下几个方面来描述个输入过程(1) 顾客的总体数，又称顾客源、顾客的总体数，又称顾客源、输入源。这是指顾客的输入源。这是指顾客的来源。

7、来源。 顾客源可以是有限的，也可以是无限的。顾客源可以是有限的，也可以是无限的。 例如，到售票处购票的顾客总数可以认为是无限的，例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。而某个工厂因故障待修的机床则是有限的。131.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程(2) 顾客到来的方式。顾客到来的方式。这是描述顾客是怎样来到系统的，这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。他们是单个到达，还是成批到达。 病人到医院看病是顾客单个到达的例子。在库存问题病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入

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

9、，也可以是随机顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。型的。 顾客流的概率分布一般有定长分布、二项分布、泊松流顾客流的概率分布一般有定长分布、二项分布、泊松流( (最简单流最简单流) )、爱尔朗分布等若干种。、爱尔朗分布等若干种。151.2 排队系统的组成和特征排队系统的组成和特征 输入过程输入过程(4) 顾客的到达可以是相互独立的。顾客的到达可以是相互独立的。(5) 输入过程可以是平稳的，或称对时间是齐次的，即描输入过程可以是平稳的，或称对时间是齐次的，即描述相继到达的间隔时间分布和所含参数述相继到达的间隔时间分布和所含参数(如期望值、方如期望值、方差等差等)都是与时间无关的

10、。都是与时间无关的。161.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则 v这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。v(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。 171.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则 (2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。

11、对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务先到先服务(FCFS)后到先服务后到先服务(LCFS)随机服务随机服务(RS)有优先权的服务有优先权的服务181.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则 (2)等待制。 对于等待制，为顾客进行服务的次序可以采用下列各种规则： 先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。 随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 优先权服务。如老人、儿童先进车站；危重

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

13、特征排队系统的组成和特征 排队规则排队规则 (3)混合制 队长有限。 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。211.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则 (3)混合制 队长有限。 等待时间有限。 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失

14、制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。221.2 排队系统的组成和特征排队系统的组成和特征 排队规则排队规则 （续）v从允许排队的空间看队列可以排在具体的处所，也可以是抽象的。队列可以排在具体的处所，也可以是抽象的。排队空间可以有限，也可以无限。排队空间可以有限，也可以无限。v从排队的队列数目看，可以是单列单列，也可以是多列多列。在多列的情形，各列间的顾客有的可以互相转移，有的不能。在多列的情形，各列间的顾客有的可以互相转移，有的不能。有的排队顾客因等候时间过长而中途退出，有的不能退出，有的排队顾客因等候

15、时间过长而中途退出，有的不能退出，必须坚持到被服务为止。必须坚持到被服务为止。231.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。从数量上说，服务台有单服务台和多服务台之分。在有多个服务台的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。241.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服

16、务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 多队多服务台并串联混合式等等。服务台的各服务台的各种排列方式种排列方式25单队列S个服务台并联的排队系统S个队列S个服务台的并联排队系统1.2 排队系统的组成和特征排队系统的组成和特征 26单队多个服务台的串联排队系统 多队多服务台混联、网络系统1.2 排队系统的组成和特征排队系统的组成和特征 271.2 排队系统的组成和特征排队系统的组成和特征 服务机构服务机构 (服务台情况)(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务

17、两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3) 服务时间的分布。服务时间可分为确定型确定型和随机型随机型。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。v服务时间的分布通常假定是平稳的。281.3 排队模型的分类排队模型的分类 排队模型分类方法排队模型分类方法D.G.Kendall，1953构成排队模型的三个主要特征指标构成排队模型的三个主要特征指标o(1) 相继顾客到达间隔时间的分布；相继顾客到达间隔时间的分布；o(2) 服务时间的分布；服务时间的分布；o(3) 服

18、务台的个数。服务台的个数。根据这三个特征对排队模型进行分类的根据这三个特征对排队模型进行分类的Kendall记号：记号： X/Y/ZoX：表示相继到达间隔时间的分布；：表示相继到达间隔时间的分布；oY：表示服务时间的分布；：表示服务时间的分布；oZ：并列的服务台的数目。：并列的服务台的数目。291.3 排队模型的分类排队模型的分类 vM负指数分布负指数分布(M是是Markov的字头，因为负指数分的字头，因为负指数分布具有无记忆性，即布具有无记忆性，即Markov性性)vD确定型确定型(deterministic)vEkk阶爱尔朗阶爱尔朗(erlang)分布分布vGI 一般相互独立一般相互独立(

19、general independent)的时间间隔的时间间隔的分布的分布vG 一般一般(general)服务时间的分布服务时间的分布301.3 排队模型的分类排队模型的分类vKendall符号的扩充 X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是：其中前三项的意义不变，后三项的意义分别是：oA：系统容量限制：系统容量限制N，或称等待空间容量。如系统有，或称等待空间容量。如系统有N个等待位个等待位子，则子，则 0 N 0为一常数，此种的平均服务时间为： K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。0,)!1()()(1xekxkkxbxkk01)()(dx

20、xxbtE例子：例子：串列的串列的k个服务台，每台服务时间相互独立，服从相同个服务台，每台服务时间相互独立，服从相同的负指数分布的负指数分布(参数参数k)，那么一顾客走完这，那么一顾客走完这k个服务台总共所需个服务台总共所需要服务时间就服从要服务时间就服从k阶爱尔朗分布。阶爱尔朗分布。2.2.3 服务时间的爱尔朗分布服务时间的爱尔朗分布63n第1节 基本概念n第2节 到达间隔的分布和服务时间的分布n第3节 单服务台负指数分布排队系统的分析n第4节 多服务台负指数分布排队系统的分析n第5节 一般服务时间M/G/1模型n第6节 经济分析系统的最优化n第7节 分析排队系统的随机模拟法排队论排队论64

21、排队论排队论n 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。n (1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。n (2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。65n (3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。n 系统优化问题包括最优设计问题和最

22、优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。n 对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标： 排队论排队论66 系统中顾客数(队长)的期望值L或Ls； 排队等待的顾客数(排队长)的期望值Lq； 顾客在系统中全部时间(逗留时间)的期望值W或Ws； 顾客排队等待时间的期望值Wq。 排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模

23、型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。 下面拟分析几种常见排队系统模型。排队论排队论67v3.1 标准的M/M/1模型(M/M/1/)v3.2 系统容量有限的情况(M/M/1/N/)v3.3 顾客源有限的情形(M/M/1/m)第第3节节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析本节讨论输入过程服从普阿松分布过程、服务时间本节讨论输入过程服从普阿松分布过程、服务时间服从负指数分布单服务台的排队系统。服从负指数分布单服务台的排队系统。68v标准的M/M/1模型(1) 输入过程输入过程顾客源是无限的，顾客单个到来，相互独立，一顾客源是无限的，顾客单

24、个到来，相互独立，一定时间内的定时间内的到达数服从泊松分布到达数服从泊松分布，到达过程是平稳的。，到达过程是平稳的。(2) 排队规则排队规则单队，且对队长没有限制，先到先服务。单队，且对队长没有限制，先到先服务。(3) 服务机构服务机构单服务台，各顾客的单服务台，各顾客的服务时间相互独立，服从相服务时间相互独立，服从相同的负指数分布同的负指数分布。此外，还假定到达间隔时间和服务时间是相互独立的。此外，还假定到达间隔时间和服务时间是相互独立的。 3.1 标准的标准的M/M/1模型模型(M/M/1/)即已知条件：v ：顾客进入系统的平均速度，即单位时间到达的顾客数。v ：顾客离开系统的平均速度，即

25、单位时间能被服务完成的顾客数。69v首先要求出：系统在任意时刻t的状态为n(即系统中有n个顾客)的概率 ，它决定了系统运行的特征。因已知到达规律服从参数为因已知到达规律服从参数为 的泊松过程，服务时间服从参数为的泊松过程，服务时间服从参数为 的负指数分布，所以在的负指数分布，所以在 时间区间内分为：时间区间内分为：(1) 有有1个顾客到达的概率为个顾客到达的概率为 没有顾客到达的概率就是没有顾客到达的概率就是 (2) 当有顾客在接受服务时，当有顾客在接受服务时，1个顾客被服务完了个顾客被服务完了(离去离去)的概率的概率是是 ，没有离去的概率就是，没有离去的概率就是 。(3) 多于一个顾客的到达

26、或离去的概率是多于一个顾客的到达或离去的概率是 ，可以忽略。，可以忽略。( )nP t, t tt()tot 1()tot ()tot 1()tot ()ot3.1 标准的标准的M/M/1模型模型(M/M/1/)703.1 标准的标准的M/M/1模型模型(M/M/1/)v在时刻 ，系统中有n个顾客(n0)存在下列四种情况(到达或离去是2个以上的没列入)：表示发生表示发生(1个个)；表示没有发生。表示没有发生。tttt , t ttnn(D)nn-1(C)nn+1(B)nn(A)离去离去到达到达在时刻在时刻 顾客数顾客数在区间在区间在时刻在时刻t顾顾客数客数情况情况7172v这四种情况是互不相容

27、的，所以 应是这四项之和，即 即v令 ，得关于 的微分差分方程 ()nP tt1111()( )(1 )( )( )()()( )()( )( )()( )nnnnnnnnnP ttP tttPttPttotP ttP totPtPtP ttt 0t ( )nP t11( )( )( )()( ) 1,2,(12 15)nnnndP tPtPtP tndt3.1 标准的标准的M/M/1模型模型(M/M/1/)( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt 所有的高阶所有的高阶无穷小和并无穷小和并tttPtttPtttPttPnnnn

28、)1)()()1)(1)()(1)()1 ()(1tOtttPn73v当 ，则只有上表中(A)(B)情况，且方式(A)中无离去的概率为1，即v同理求得 v它们的概率分别是 o情况情况(A)o情况情况(B) o情况情况(C)o情况情况(D) tt , t ttnn(D)nn-1(C)nn+1(B)nn(A)离去离去到达到达在时刻在时刻 顾客数顾客数在区间在区间在时刻在时刻t 顾顾客数客数情况情况( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt3.1 标准的标准的M/M/1模型模型(M/M/1/)0n 001()( )(1 )( )(1

29、)P ttP ttP ttt 001( )( )( )(12 16)dP tP tP tdt 74v研究稳态的情况。这时 与时间t无关，可写成 ，它的导数为0。由(12-15)式和(12-16)式可得v这是关于 的差分方程，它表明了各状态间的转移关系：状态0转移到状态1的转移率为 ，状态1转移到状态0的转移率为 。 ( )nP tnP01110(12 17,12 18)()0 1nnnPPPPPn0P1PnP3.1 标准的标准的M/M/1模型模型(M/M/1/)这种系统状态这种系统状态(n)随时间变化的过程就是生灭过程（随时间变化的过程就是生灭过程（Birth and Death Proces

30、s）。）。 方程方程(12-15)、(12-16) 解是瞬态解，无法应用。解是瞬态解，无法应用。 753.1 标准的标准的M/M/1模型模型(M/M/1/)v对状态0必须满足以下平衡方程v同样对任何 的状态，可得如(12-18)所示的平衡方程。由(12-17)式可得v将它代入(12-18)式，令 ，得到v同理依次推得v今设 (否则队列将排至无限远)，又由概率的性质知 将 的关系代入 ，得到01PP1n10(/)PP220020()(/) (/)PPPPP；所以 1n 0(/)nnPP101nnPnP01 1(12 19)(1), 1nnPPn 000111nnPp01110(12 17,12

31、18)()0 1nnnPPPPPn 76v对的实际意义的解释/，是平均到达率与平均服务率之比，即在相同时区内，是平均到达率与平均服务率之比，即在相同时区内顾客到达的平均数与被服务的平均数之比。顾客到达的平均数与被服务的平均数之比。若将若将表示为表示为(1/)/(1/)，它是一个顾客的服务时间与到，它是一个顾客的服务时间与到达间隔时间之比，称达间隔时间之比，称为服务强度为服务强度(traffic intensity)，或话务，或话务强度。强度。由由(12-19)式可知，式可知，=1-P0，它刻画了服务机构的繁忙程度，它刻画了服务机构的繁忙程度，所以所以又称为服务机构的利用率。又称为服务机构的利用

32、率。3.1 标准的标准的M/M/1模型模型(M/M/1/) 系统处于空闲状态的概率：系统处于空闲状态的概率： 10P 系统处于繁忙状态的概率：系统处于繁忙状态的概率： 010P)N(P77v根据平稳分布，求排队系统的有关运行指标(1) 系统中的平均顾客数系统中的平均顾客数（平均队长）（平均队长） 或或 (2) 在队列中等待的平均顾客数在队列中等待的平均顾客数 012323423(1)(23)(23), 0 11nsnnnLnPn sL1112(1)1qnnnnnnsLnPnPPL3.1 标准的标准的M/M/1模型模型(M/M/1/) 期望期望78顾客在系统中的逗留时间W(为一个随机变量)在M/

33、M/1情形下，服从参数为 的负指数分布，即 分布函数 概率密度 ()( )1 e 0(1220)wF ww ()( )()ewf w 于是，得到于是，得到(3) 在系统中顾客逗留时间的期望值在系统中顾客逗留时间的期望值 (4) 在队列中顾客等待时间的期望值在队列中顾客等待时间的期望值 1sWE W1qsWW3.1 标准的标准的M/M/1模型模型(M/M/1/) 平均逗留时间减平均逗留时间减去平均服务时间。去平均服务时间。79v将以上结果归纳如下： v它们的相互关系如下： 上式称为Little公式。(1) (2) (1221)1(3) (4) sqsqLLWW(1) (2) (1222)1(3)

34、 (4) ssqqsqsqLWLWWWLL3.1 标准的标准的M/M/1模型模型(M/M/1/)803.1 标准的标准的M/M/1模型模型(M/M/1/)Ls ,L q, ,Ws ,Wq之间的关系：几何解释： 稳态时，一个顾客，进入系统后，每单位时间，平均到达顾客。 进入时刻离开时刻总时间Ws 队长Ls由时间段内个组成的Ls=Ws(1) (2) (12 22)1(3) (4) ssqqsqsqLWLWWWLL同理：Lq=Wq Ws=Wq+（1/）-Ws与Wq只相差一段平均服务时间1/ 813.1 标准的标准的M/M/1模型模型(M/M/1/)82 解：本例可看成一个解：本例可看成一个M/M/1

35、/ 排队问题，其中排队问题，其中 =2， =3， = / =2/31 系统中列车的平均数系统中列车的平均数 L= / (1- )=(2/3)/(1-2/3)=2（列）（列）列车在系统中的平均停留时间列车在系统中的平均停留时间W=L/ = 2/2=1（小时）（小时）系统中等待编组的列车平均数系统中等待编组的列车平均数Lq=L- = 2-2/3=4/3（列）（列）列车在系统中的平均等待编组时间列车在系统中的平均等待编组时间 Wq = Lq/ =(4/3)/(1/2)=2/3（小时）（小时）3.1 标准的标准的M/M/1模型模型(M/M/1/)833.1 标准的标准的M/M/1模型模型(M/M/1/

36、)843.1 标准的标准的M/M/1模型模型(M/M/1/)853.1 标准的标准的M/M/1模型模型(M/M/1/)863.1 标准的标准的M/M/1模型模型(M/M/1/)873.1 标准的标准的M/M/1模型模型(M/M/1/)883.1 标准的标准的M/M/1模型模型(M/M/1/)89v例3 某医院手术室根据病人来诊和完成手术时间的记录，任意抽查了100个工作小时，每小时来就诊的病人数n的出现次数如下表所示；又任意抽查了100个完成手术的病历，所用时间v(单位：小时)出现的次数如下表所示。nf到达的病人数n出现人数0101282316410566以上以上1合计合计100vf为病人完成

37、手术时间v(小时)出现人数0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上以上0合计合计1003.1 标准的标准的M/M/1模型模型(M/M/1/)90v(1) 每小时病人平均到达率 (人/小时) 每次手术平均时间 (小时/人) 每小时完成手术人数(平均服务率) (人/小时)v(2) 取 ， ，可以通过统计检验的方法，认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。v(3) 说明服务机构(手术室)有84%的时间是繁忙的，有16%的时间是空闲的。v(4) 依次代入(12-21)式，算出各指标：在病房中病人数在病房

38、中病人数(期望值期望值) (人人)排队等待病人数排队等待病人数(期望值期望值) (人人)病人在病房中逗留时间病人在病房中逗留时间(期望值期望值) (小时小时)病人排队等待时间病人排队等待时间(期望值期望值) (小时小时)2.1100nnf0.4100vvf52.52.1sL 0.84 5.254.41qL sW 0.8qW 3.1 标准的标准的M/M/1模型模型(M/M/1/)91v如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，

39、那么这个顾客就被拒绝进入系统。v当N=1时为即时制的情形；当N时为容量无限制的情形。3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)92泊松输入负指数分布服务的排队系统的一般决策过程： 根据已知条件绘制状态转移速度图； 依据状态转移速度图写出各稳态概率之间的关系； 求出 P0 及 Pn ； 计算各项数量运行指标； 用系统运行指标构造目标函数，对系统进行优化。3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)933.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v稳态情形下各状态间概率强度的转换关系图v状态概率的稳态方程 101

40、11 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP情情况况 时时刻刻 t 的的顾顾客客 区区间间 t, t+t t 时时刻刻 t+t t的的顾顾客客数数 概概率率 A A N N 无无离离去去 （肯肯定定不不到到达达） N N P Pn n( (t t) )( (1 1- -t t) ) B B N N- -1 1 一一人人到到达达（无无离离去去） N N P Pn n- -1 1( (t t) )t t ttPttPttPNNN)()1 ()()(1 )()()(1tPtPdttdPNNN 943.2 系统的容量有限制的情况系统的容量有限制的情况

41、(M/M/1/N/)v稳态情形下各状态间概率强度的转换关系图v状态概率的稳态方程 其中(12-23a)也可写成 ，则有10111 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP0(/)nnPP1001 (), 1 nnNNPPPPnNPP953.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/) 由 1001 (), 1 nnNNPPPPnNPP N(/)nP0=1n=0 NP0=1/(/)n= n=0(1- (1- /)/)/(1- (1- (/) )N N+1+1 1/(1/(N N +1) +1) = =Pn=1/(N +1)

42、 =(1- (1- /)()(/ ) )n n/(1- (/(1- (/) )N N+1+1 011NPPP96vM/M/1/N/排队系统的各项指标：v(1) 队长(期望值)v(2) 队列长(期望值)v(3) 顾客逗留时间(期望值)v (4) 顾客等待时间(期望值)v(5) 有效到达率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/971011 NPnNnP 111 (1,n

43、N(1,nN) ) (1) 平均平均队长队长Ls：nPnLnNnNNnns 01011nNnNn 0111111) 1(1 NNN (1) 试证试证=1=1时时,Ls=N/2,Ls=N/23.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)98 ? ? ?vM/M/1/N/排队系统的各项指标：v(1) 队长(期望值)v(2) 队列长(期望值)v(3) 顾客逗留时间(期望值)v (4) 顾客等待时间(期望值)v(5) 有效到达率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系统的

44、容量有限制的情况系统的容量有限制的情况(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/返回返回P9899 (2) 有效到达率有效到达率e 系统容量有限，当满员（系统容量有限，当满员（n=N）时时，顾客将被拒绝，实际的顾客到达率，顾客将被拒绝，实际的顾客到达率与与不一样，不一样，)1(NeP 还可验证：还可验证：esesqLLL esSLW eqqLW 此种情况的公式与前类似此种情况的公式与前类似,只只有有Ls不同不同,e与与 不同。求不同。求e必必须先求得须先求得P0或或PN才行。才行。有效到达率为有效到达率为e 可以证明：可以证明：)1(0Pe 111)1(

45、1 NNN LsLs3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)100vM/M/1/N/排队系统各项指标的归纳(当 时)：11100(1)11(1)(12-25)(1)1/NsNqsssqsNLLLPLWPWW3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)101例例2某单人理发馆共有六把椅子接待顾客排队，无座时将离某单人理发馆共有六把椅子接待顾客排队，无座时将离去，顾客平均到达率为去，顾客平均到达率为3人人/h，理发时间平均为，理发时间平均为15分钟，求：分钟，求：(1) 求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2) 求

46、需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3) 求有效到达率求有效到达率;(4) 求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值;(5) 在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)10211. 275. 0175. 0825. 075. 01) 1(18811 NNsNL02.11 (1)2.11 (1 0.2778) 1.39qsLLP2778. 075. 0175. 0111810 NP(1) 求某一顾客到达就能理发的概率求

47、某一顾客到达就能理发的概率:(2) 求需要等待的顾客数的期望值求需要等待的顾客数的期望值:(3) 求有效到达率求有效到达率:89. 2)2778. 01(4)1(0 Pe(4) 求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值:3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)103min8 .4373. 089. 211. 2 hLWessmin86.2848. 089. 239. 1 hLWeqq%71. 375. 075. 0175. 01117817 NNPP0=0.27780P1=0.20836P2=0.15627P3=0.1

48、1720 = 0.9629=96.29% 1- 0.9629=3.71% P4=0.08790P5=0.06593P6=0.04944(5) 在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？ 顾客为何不顾客为何不等待就离去？等待就离去？ 因为系统因为系统已经满员已经满员037. 0389. 23 e3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)故拒绝的概率为故拒绝的概率为3.71%104v例例4 某单人理发馆为等待的顾客准备了6把椅子，当6把椅子都坐满时，再来的顾客将不进店而离开。顾客的平均到达率为3人/小时，理发平均需要15分

49、钟。则系统的容量为N=6+1=7， 人/小时， 人/小时。(1) 某顾客一到达就能理发的概率某顾客一到达就能理发的概率(2) 需要等待的顾客数的期望值需要等待的顾客数的期望值(3) 有效到达率有效到达率 (人人/小时小时)(4) 一顾客在理发馆内逗留的期望时间一顾客在理发馆内逗留的期望时间 (小时小时) (分钟分钟)34081 3/40.27781 (3/4)P8803/48(3/4)2.111 3/41 (3/4)(1)2.11 (1 0.2778)1.39sqsLLLP0(1)4(1 0.2778)2.89ePe/2.11/2.890.73ssWL3.2 系统的容量有限制的情况系统的容量有

50、限制的情况(M/M/1/N/)105v(5) 在可能到来的顾客中不等待就离开的概率 这也是理发馆的损失率。(7)nP 77788311/343.7%1 (/)4314P人/小时人/小时有限队长2.111.390.730.480.2783.7无限队长32.251.00.750.25034sL7N qLsWqW0P7P以本例为例，比较队长为有限和无限的情形：以本例为例，比较队长为有限和无限的情形：3.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)106v背景设有设有m台机器台机器(顾客总体顾客总体)，机器因故障停机表示，机器因故障停机表示“到达到达”，待修的机器形成，待修的机

51、器形成队列，修理工人是服务员，本节讨论单服务员的情形。队列，修理工人是服务员，本节讨论单服务员的情形。顾客总体虽只有顾客总体虽只有m个，但每个顾客到来并经过服务后，仍回到原来总体，所个，但每个顾客到来并经过服务后，仍回到原来总体，所以仍然可以再到来。以仍然可以再到来。如在机器故障问题中，同一台机器出了故障如在机器故障问题中，同一台机器出了故障(到来到来)并经修好并经修好(服务完了服务完了)仍可仍可再出故障，形成循环。再出故障，形成循环。模型符号中的模型符号中的表示对系统的容量没有限制，但实际上它不会超过表示对系统的容量没有限制，但实际上它不会超过m，所以，所以可写成可写成(M/M/1/m/m)

52、。3.3 顾客源为有限的情形顾客源为有限的情形(M/M/1/m)107v设每个顾客的到达率相同，均为 (这里这里的含义是单台机器在单位时的含义是单台机器在单位时间里发生故障的概率或平均次数间里发生故障的概率或平均次数)；设系统内顾客数为Ls，则系统外的顾客平均数为mLs，所以系统的有效到达率为 e=(m Ls) (12-26) v考虑稳态情况下状态间的转移率由状态由状态0转移到状态转移到状态1：每台设备由正常状态转移为故障状态的转：每台设备由正常状态转移为故障状态的转移率为移率为P0，m台设备由无故障状态转移为有一台设备台设备由无故障状态转移为有一台设备(不论哪一台不论哪一台)发生故障的转移率

53、为发生故障的转移率为mP0。由状态由状态1转移到状态转移到状态0：其状态转移率为：其状态转移率为P1。所以，状态所以，状态0时有平衡方程为：时有平衡方程为： mP0=P13.3 顾客源为有限的情形顾客源为有限的情形(M/M/1/m)108v各状态间的转移差分方程解得(注意到 因而不要求 ） v系统的各项指标为10111(1)(), 11nnnmmPm PPmnPmnPnmPP01miiP/10001!()!(1227)! (1)()!iminnPmmimPPnmmn0000(1)()(1)(1)(1228)1(1)1/sqssqsLmPPLmLPmWPWW3.3 顾客源为有限的情形顾客源为有限

54、的情形(M/M/1/m)109v例例5 某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求：(1) 修理工空闲的概率；修理工空闲的概率；(2) 五台机器都出故障的概率；五台机器都出故障的概率；(3) 出故障的平均台数；出故障的平均台数；(4) 等待修理的平均台数；等待修理的平均台数；(5) 平均停工时间；平均停工时间；(6) 平均等待修理时间；平均等待修理时间；(7) 评价这些结果。评价这些结果。3.3 顾客源为有限的情形顾客源为有限的情形(M/M/1/m)110解：解： (1)(2) 五台机器都出现

55、故障的概率五台机器都出现故障的概率(3) 出故障的平均台数出故障的平均台数 (台)(4) 等待修理的平均台数等待修理的平均台数 (台)(5)平均停工时间平均停工时间 (分钟)(6)平均等待修理时间平均等待修理时间 (分钟)(7) 机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。5, 1/15, 1/12, /0.8m101234505!5!5!5!5!5!(0.8)(0.8)(0.8)(0.8)(0.8)(0.8)5!4!3!2!1!0!1/136.80.0073P5505! (0.8)0.2870!PP1 5(1 0.0073)3.760.8sL 3.76

56、0.9932.77qL 6515461(1 0.007)12W 461234qW 3.3 顾客源为有限的情形顾客源为有限的情形(M/M/1/m)111n第1节 基本概念n第2节 到达间隔的分布和服务时间的分布n第3节 单服务台负指数分布排队系统的分析n第4节 多服务台负指数分布排队系统的分析n第5节 一般服务时间M/G/1模型n第6节 经济分析系统的最优化n第7节 分析排队系统的随机模拟法排队论排队论112本节讨论单队、并列的多服务台（服务台数为本节讨论单队、并列的多服务台（服务台数为c）的情形。）的情形。v4.1 标准的M/M/c模型v4.2 M/M/c型系统和c个M/M/1型系统的比较v4

57、.3 系统容量有限的情形（M/M/c/N/）v4.4 顾客源有限的情形（M/M/c/ /m）第第4节节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析1134.1 标准的标准的M/M/c模型模型v标准的M/M/c模型各种特征的规定与标准的M/M/1模型的规定相同。v各服务台工作是相互独立的(不搞协作)，且平均服务率相同。v整个服务机构的平均服务率为 (当 )；为 (当 )。v令 ，只有当 时才不会排成无限的队列称 为系统的服务强度服务强度或服务机构的平均利用率。平均利用率。12ccncnncc1cc1144.1 标准的标准的M/M/c模型模型vM/M/c排队系统的状态概率分布

58、状态状态1转移到状态转移到状态0：即系统中有一名顾客被服务完了：即系统中有一名顾客被服务完了(离去离去)的转移率的转移率为为 。状态状态2转移到状态转移到状态1：两个服务台上被服务的顾客中有一个被服务完成：两个服务台上被服务的顾客中有一个被服务完成而离去。因为不限哪一个，于是状态的转移率为而离去。因为不限哪一个，于是状态的转移率为 。状态状态n转移到转移到n-1：o当当 时，状态转移率为时，状态转移率为 ；o当当 时，因为只有时，因为只有c个服务台，最多有个服务台，最多有c个顾客在被服务，个顾客在被服务， 个顾客在等候，因此这时状态转移率应为个顾客在等候，因此这时状态转移率应为 。1P22 P

59、ncncnn Pncnc P1154.1 标准的标准的M/M/c模型模型v由图12-13可得 这里 ，且 v用递推法解上述差分方程，可求得状态概率。101111(1)() (1)() ()nnnnnnPPnPPnPncc PPcPnc01iiP1)(!1)(!111!1!1001100cnPcccnPnPckPncnnnckc1164.1 标准的标准的M/M/c模型模型v系统的运行指标为：v 平均队长v平均等待时间和逗留时间可由Little公式求得，sqcqn02n c 1LL(1230)(c )L(nc)PPc!(1) 0111()()!n cnn cn cnnnnc PnPcPc cn 因

60、为 右边, qsqsLLWW1174.1 标准的标准的M/M/c模型模型v例6 某售票处有三个窗口，顾客的到达服从泊松过程，平均到达率每分钟 (人)，服务(售票)时间服从负指数分布，平均服务率每分钟 人。现设顾客到达后排成一队，依次向空闲的窗口购票如图12-14(a)，这就是一个M/M/c型的系统，其中 ， ， 符合要求的条件，代入公式得：0.90.43c 2.252.253( 1)c0312323431184.1 标准的标准的M/M/c模型模型v(1) 整个售票处空闲概率v(2) 平均队长v(3) 平均等待时间和逗留时间 (分钟) (分钟)v顾客到达后必须等待(即系统中顾客数已有3人即各服务