运筹学第三排队论PPT课件

1、1排队论第1节 基本概念第2节 到达间隔的分布和服务时间的分布第3节 单服务台负指数分布排队系统的分析第4节 多服务台负指数分布排队系统的分析第5节 一般服务时间M/G/1模型第6节 经济分析系统的最优化第7节 分析排队系统的随机模拟法第1页/共188页2第1节 基 本 概 念 1.1 排队过程的一般表示 1.2 排队系统的组织和特征 1.3 排队模型的分类 1.4 排队问题的求解第2页/共188页3 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的

2、顾客立即离开系统。1.1 排队过程的一般表示第3页/共188页41.1 排队过程的一般表示 各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。 排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队过程的一般模型排队过程的一般模型第4页/共188页51.1 排队过程的一般表示到达的顾客到达的顾客要求服务内容要求服务内容服务机构服务机构1.不能运转的机器2.修理技工3.病人4.电话呼唤5.文件稿6.提货单7.到达机场上空的飞机8.驶入港口的货船9.上游河水进入水库10.进入我方阵地的敌机修理领取修配

3、零件诊断或动手术通话打字提取存货降落装(卸)货装(卸)放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库管理员跑道货码头(泊位)水闸管理员我方高射炮形形色色的排队系统 第5页/共188页6 实际的排队系统虽然千差万别，但是它们有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。1.2 排队系统的组成和特征 第6页/共

4、188页71.2 排队系统的组成和特征 排队系统由三个基本部分组成： 输入过程 排队规则 服务机构第7页/共188页81.2 排队系统的组成和特征 输入过程 输入即指顾客到达排队系统。输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。 一般可以从以下几个方面来描述个输入过程(1) 顾客的总体数，又称顾客源、输入源。这是指顾客的来源。 顾客源可以是有限的，也可以是无限的。 例如，到售票处购票的顾客总数可以认为是无限的；上游河水流入 水库可以认为顾客总体是无限的 例如，某个工厂因故障待修的机床则是有限的。第8页/共188页91.2 排队系统的组成和特征 输入过程(2

5、) 顾客到来的方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。 病人到医院看病是顾客单个到达的例子。 在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。第9页/共188页101.2 排队系统的组成和特征 输入过程(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。 顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。例如：在流水线上装配的各部件必须按确定的时间间隔到达装配点，定点运行的列车、班机的到达也都是确定

6、的；例如：物流配送等待的顾客、办理出关手续的顾客、通过路口的车辆的到达都是随机的。第10页/共188页111.2 排队系统的组成和特征 输入过程 对于随机的情形，必须了解单位时间的顾客到达数或相继到达的时间间隔的概率分布。 顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。第11页/共188页121.2 排队系统的组成和特征 输入过程(4) 顾客的到达可以是相互独立的。(5) 输入过程可以是平稳的，或称对时间是齐次的，即描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的。第12页/共188页131.2 排队系统的组成和特征 排队规则 这是指

7、服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 例如：电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。 第13页/共188页141.2 排队系统的组成和特征 排队规则 (2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如：排队等待售票，故障设备等待维修等。 对于等待制，为顾客进行服务的次序可以采用下列各种规则： 先到先服务(FCFS) 后到先服务(LCFS) 随机服务

8、(RS) 有优先权的服务第14页/共188页151.2 排队系统的组成和特征 排队规则 (2)等待制（续）。 先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 后到先服务。 例如：仓库中迭放的钢材，后迭放上去的都先被领走。 随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务。 例如：电话交换台接通呼叫电话。 优先权服务。 例如：老人、儿童先进车站； 危重病员先就诊； 遇到重要数据需要处理计算机立即中断其他数据的处理等。第15页/共188页161.2 排队系统的组成和特征 排队规则 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不

9、允许队列无限长下去。具体说来，大致有三种： 队长有限。 等待时间有限。 逗留时间有限。第16页/共188页171.2 排队系统的组成和特征 排队规则 (3)混合制 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 具体地，最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。 例如：水库的库容是有限的，旅馆的床位是有限的。第17页/共188页181.2 排队系统的组成和特征 排队规则 (3)混合制 队长有限。 等待时间有限。即顾客在系统中的等待时间

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

11、=时，混合制即成为等待制。第19页/共188页201.2 排队系统的组成和特征 排队规则 （续） 从允许排队的空间看 队列可以排在具体的处所，也可以是抽象的。 排队空间可以有限，也可以无限。 从排队的队列数目看，可以是单列，也可以是多列。 在多列的情形，各列间的顾客有的可以互相转移，有的不能。 有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服务为止。第20页/共188页211.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。从数量上说，服务台

12、有单服务台和多服务台之分。在有多个服务台的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。第21页/共188页221.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 服务台的各服务台的各种排列方式种排列方式第22页/共188页231.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多

13、服务台并联式；如(b)图 服务台的各服务台的各种排列方式种排列方式第23页/共188页241.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 服务台的各服务台的各种排列方式种排列方式第24页/共188页251.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务

14、台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 服务台的各服务台的各种排列方式种排列方式第25页/共188页261.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 多队多服务台并串联混合式等等。服务台的各服务台的各种排列方式种排列方式第26页/共188页271.2 排队系统的组成和特征 服务

15、机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 多队多服务台并串联混合式等等。服务台的各服务台的各种排列方式种排列方式第27页/共188页281.2 排队系统的组成和特征 服务机构 (服务台情况)(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3) 服务时间的分布。服务时间可分为确定型和随机型。一般来说，在

16、多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。 服务时间的分布通常假定是平稳的。 指时间间隔分布及其特征参数（数学期望、方差等）不随时间的变化而变化。第28页/共188页291.3 排队模型的分类 排队模型分类方法，1953 构成排队模型的三个主要特征指标 (1) 相继顾客到达间隔时间的分布； (2) 服务时间的分布； (3) 服务台的个数。 根据这三个特征对排队模型进行分类的Kendall记号： X/Y/Z X：表示相继到达间隔时间的分布； Y：表示服务时间的分布； Z：并列的服务台的数目

17、。第29页/共188页301.3 排队模型的分类 M负指数分布(M是Markov的字头，因为负指数分布具有无记忆性，即Markov性) D确定型(deterministic) Ekk阶爱尔朗(erlang)分布 GI 一般相互独立(general independent)的时间间隔的分布 G 一般(general)服务时间的分布第30页/共188页311.3 排队模型的分类 Kendall符号的扩充 X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是： A：系统容量限制N，或称等待空间容量。如系统有N个等待位子，则 0 N 00是常数，则称是常数，则称X 服从参数为服从参数为 的泊

18、松分布。的泊松分布。其均值为其均值为 方差为方差为 ekkPPkk! )(E )(D第2节 到达间隔的分布和服务时间的分布第44页/共188页45其中其中 00为常数，则称为常数，则称t t服从参数为服从参数为 的指数分布，其分布函数的指数分布，其分布函数F F( (t t) )为为其均值为其均值为 方差为方差为 ttttedtedttftF 1)()( 000)(ttetft 0001)(ttetFt 1)( tE21)( tDv 负指数分布的定义负指数分布的定义第2节 到达间隔的分布和服务时间的分布第45页/共188页46 如果随机变量T的概率密度是则称T服从负指数分布。它的分布函数是 数

19、学期望为 方差为 标准差为 e, 0( )0, 0tTtftt1 e, 0( )0, 0tTtF tt 1E T 21VarT 1Tv 负指数分布的定义负指数分布的定义第2节 到达间隔的分布和服务时间的分布第46页/共188页47经验分布 例1 大连港大港区1979年载货500吨以上船舶到达(不包括定期到达的船舶)逐日记录见书上表12-2。 将表12-2整理成船舶到达数的分布表。 可以计算出：平均到达率=到达总数/总天数=1271/365=3.48(艘/天)船舶到达数n频数频率(%)0120.0331430.1182640.1753740.2034710.1955490.1346260.071

20、7190.052840.011920.00510以上以上10.003合计合计3651.000第47页/共188页482. 1.1 经验分布 以i表示第i号顾客到达的时刻，以si表示对它的服务时间，这样可算出相继到达的间隔时间ti (ti=i+1-i)和排队等待时间wi，它们的关系如下：iit1iw0, 00,iiiiiiiiitswtswtsw当当相继到达时间间隔相继到达时间间隔等待时间等待时间第48页/共188页492. 1.1 经验分布 通过一个例题来说明原始资料的整理。 例2 某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻和服务时间s(单位为分钟)如表12-4。在表中以第1号

21、顾客到达时刻为0，对所有顾客的全部服务时间为127分钟。将原始记录整理成下表。第49页/共188页50顾客编号i到达时刻i服务时间Si到达间隔ti等待时间wi顾客编号i到达时刻i服务时间Si到达间隔ti等待时间wi12345678910111213026111219222636384547495719243312541245173410272230362105650003522232425262728293031323334838688929510110510610911411611712136513221218423243264135214622675201000772. 1.1 经验分布第

22、50页/共188页51顾客编号i到达时刻i服务时间Si到达间隔ti等待时间wi顾客编号i到达时刻i服务时间Si到达间隔ti等待时间wi14151617181920215261626570728081212134329135281230000102353637383940411271291301331351391421635241213243327710892. 1.1 经验分布第51页/共188页522. 1.1 经验分布 例2 某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻和服务时间s(单位为分钟)如表12-4。在表中以第1号顾客到达时刻为0，对所有顾客的全部服务时间为127分钟

23、。将原始记录整理成下表。到达间隔到达间隔/ /分钟分钟次数次数162103846536272819110以上以上1合计合计40服务时间服务时间/ /分分钟钟次数次数1102103745546271819以上以上1合计合计41第52页/共188页532. 1.1 经验分布 例2 平均间隔时间=142/40=3.55(分钟/人) 平均到达率=41/142=0.28(人/分钟) 平均服务时间=127/41=3.12(分钟/人) 平均服务率=41/127=0.32(人/分钟) 第53页/共188页54 普阿松流，又称为泊松流、Poisson过程、最简单流，是排队论中一种常用来描述顾客到达规律的特殊的随

24、机过程。普阿松流（泊松流）第54页/共188页55普阿松流（泊松流）设 表示在时间区间 内到达的顾客数 令 表示在时间区间 内有 个顾客到达的概率，即当 满足下列三个条件时，我们说顾客的到达形成泊松流。 (1) 在不相重叠的时间区间内顾客到达数是相互独立的，即无后效性。 通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的。(2) 平稳性。又称作输入过程是平稳的，对充分小的 ，在时间区间内有1个顾客到达的 概率与t无关，而与区间长度 成正比，即 其中 ，当 时，是关于 的高阶无穷小。 进一步地，在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。即对

25、任意(0,)，在(,+t或(0,t)内恰好到达k个顾客的概率相等：(3) 单个性又称普通性。对于充分小的 ，在时间区间 内有2个或2个以上顾客到达的概率极小，以至于可以忽略，即 , t tt)()()0()()()(tVktPktPkataPk2( ,)()nnP t ttot0,t( )N t(0)t 12( , )nP t t1221,()t ttt( 0)n 122121( , )( )( ) (,0)nP t tP N tN tntt n12( , )nP t ttt1( ,)()P t tttot 0t ()ottt ()( ) ( )(0) ( )PatakPtkPtk第55页/共

26、188页56 当顾客到达为泊松流时，研究顾客到达数n的概率分布。 由条件(2)，总可以取时间由0算起，并简记 由条件(2)和(3)，容易推得在 区间内没有顾客到达的概率 将区间 分成两个互不重叠的区间 和 。 则到达总数n分别出现在这两个区间 和 上，有下列(A)(B)(C)三种情况：(0, )( )nnPtP t, t tt0( ,)1 ()P t tttot 0,tt0,t, t tt概率个数概率个数概率个数区间情况0,t, t tt0,tt( )( )( )ABC1230nnnn1230( )( )( )( )( )nnnnP tPtPtPtP t0123n1 ()()tottot nn

27、nnn1( )(1 ()( )()nnP ttotPttot 普阿松流（泊松流）0,t, t tt第56页/共188页57普阿松流（泊松流） 在 内到达n个顾客应是表中(A)(B)(C)三种互不相容的情况之一，所以概率 应是表中三个概率之和(各 合为一项) 令 ，得下列方程，并注意到初始条件，则有 当n=0 时，没有(B)，(C)两种情况， 所以得0,tt()nP tt()ot11 ()( )(1 )( )()()( )()( )( )nnnnnnnP ttP ttPttotP ttP totP tPttt 即 0t 1( )( )+( ), 1(125)( )0nnnndP tP tPtnd

28、tP o 000( )( )(126)( )1dP tP tdtP o ()( )(1)()()( )()( )nnnnnP ttP ttotP ttP totP ttt 即即 第57页/共188页58 解(12-5)式和(12-6)式，得 表示长为t的时间区间内到达n个顾客（即N (t)=n）的概率，由(12-7)式得随机变量 服从泊松分布。 结论：当顾客到达为泊松流时，在长度为t的时间内到达n个顾客的概率Pn(t)服从泊松分布! 它的数学期望和方差分别是(1)( )( )e(127)!0 0,1,2,ntntP tntn( )nP t( )()( )N tN stN s( ) , Var(

29、 )(128)E N ttN tt普阿松流（泊松流）相等！特别地，t=1时，EN(1)= ，因此表示单位时间平均到达的顾客数第58页/共188页59 我们再来研究两个顾客先后到达的时间间隔T的概率分布。第59页/共188页60当输入过程是泊松流时，由于在单位时间里到达的顾客数是随机变量，那么对应的，前后两个顾客到达的时间间隔也就是随机变量了，即有的时间间隔长一些，有的时间隔又短一些。 设T的分布函数为FT(t)，则这个概率也就是在0，t)区间内至少有一个顾客到达的概率。( )TF tP Tt普阿松流与负指数分布关系普阿松流与负指数分布关系第60页/共188页61泊松过程的顾客到达时间间隔分布

30、顾客到达的时间间隔小于顾客到达的时间间隔小于t t的概率，即的概率，即t t内有顾客的概率分布。内有顾客的概率分布。 两相邻顾客到达的时间间隔是一连续型随机变量，用两相邻顾客到达的时间间隔是一连续型随机变量，用T T表示。表示。在在t 时时间内间内没有没有顾客到达的概率为顾客到达的概率为 tteettP ! 0)()(00普阿松流与负指数分布关系第61页/共188页62 在区间 内至少有1个顾客到达的概率是 即顾客相继到达的间隔时间即顾客相继到达的间隔时间T必然服从负指数分布。必然服从负指数分布。0,t01( )1, 0tP tet 其概率密度函数：其概率密度函数： tTetPtTPtTPtF

31、 1)(1)(1)()(0tTTedttdFtf )()(数学期望为 1E T 表示单位时间内顾客平均到达数。 1/表示顾客到达的平均间隔时间。普阿松流与负指数分布关系第62页/共188页63 顾客相继到达的间隔时间独立且为同负指数分布(密度函数为 )，与输入过程为泊松流(参数为)是等价的。 对于泊松流，表示单位时间平均到达的顾客数，1/ 表示相继顾客到达平均间隔时间。0, tetv 相继到达时间间隔为负指数分布与到达为泊松相继到达时间间隔为负指数分布与到达为泊松流的等价性流的等价性上述内容还可以用如下表达！ 对于泊松流，其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，其分布函数为负

32、指数分布： 0, 00,1)(ttetFti), 2 , 1(i普阿松流与负指数分布关系第63页/共188页64 当输入过程是泊松流时，那么顾客相继到达的间隔时间T（注意T是随机变量）必然服从负指数分布。普阿松流与负指数分布关系第64页/共188页65 负指数分布的性质负指数分布的性质由条件概率公式容易证明 该性质称为无记忆性或马尔柯夫性。若T表示排队系统中顾客相继到达的间隔时间，该性质说明：一个顾客到来所需的时间与过去一个顾客到来所需时间s 无关，也就是说该顾客是随机地到达。(12 11)P Tts TsP Tt 普阿松流与负指数分布关系第65页/共188页66 例: :有易碎物品50050

33、0件, ,由甲地运往乙地, ,根据以往统计资料, ,在运输过程中易碎物品按普阿松流发生破碎, ,其破损率为0.002,0.002,现求:1.:1.破碎3 3件物品的概率;2.;2.破碎少于3 3件的概率和多于3 3件的概率;3.;3.至少有一件破损的概率. . 解: : =0.002500=1 1 1破碎3 3件物品的概率为: : P(k=3)=( P(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎3 3件的概率为6.136.13 2. 2.破碎物品少于3 3件的概率: :第66页/共188页67 破碎物品少于

34、3 3件的概率为91.9791.97 破碎物品多于3 3件的概率为: : 02. 098. 01!1330 kkekp 3.3.至少有一件破碎的概率为 PkPk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.632 9197. 021112120 eeknp第67页/共188页682.1 到达间隔的分布经验分布（定长输入）普阿松流（泊松流）普阿松流与负指数分布关系2.2 服务时间的分布经验分布（定长分布）负指数分布爱尔朗分布第2节 到达间隔的分布和服务时间的分布第68页/共188页69 每一个顾客的服务时间都是

35、常数，此时服务时间t的分布函数为： xxxtPxB01)()(服务时间的定长分布第69页/共188页70 服务时间服务时间v v 的分布的分布 对顾客的服务时间，也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从负指数分布。设它的分布函数和密度分别是其中, 表示对顾客的平均服务时间。表示单位时间能被服务完成的顾客数，称为平均服务率， ( )1 e, ( )e(12 12)ttvvF tf t 1()Ev服务时间的负指数分布第70页/共188页71 是指相继顾客到达时间间隔T相互独立，其分布密度为 其中，k为非负整数。 1()( )0(1)!Kttf tetK v爱尔朗分布爱尔朗分布服务时间

36、的爱尔朗分布第71页/共188页72 设 是k个相互独立的随机变量，服从相同参数 的负指数分布，那么 的概率密度是称T服从k阶爱尔朗分布，其均值和方差分别为12,kv vvk12kTvvv1()( )e, 0(12 13)(1)!kktkkktb ttk 211;Var(12 14)E TTk可以证明如下结论。服务时间的爱尔朗分布第72页/共188页73 爱尔朗分布的意义爱尔朗分布的意义 当k=1时，爱尔朗分布化为负指数分布，可看成是一种完全随机的分布； 当k增大时，爱尔朗分布的图形逐渐变为对称的； 当k30时爱尔朗分布近似于正态分布； k时，VarT0，这时爱尔朗分布化为确定型分布。一般k阶

37、爱尔朗分布可看成完全随机与完全确定的中间型，能对现实世界提供更为广泛的适应性。1()( )e, 0(12 13)(1)!kktkkktb ttk服务时间的爱尔朗分布第73页/共188页74可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：)(21kkkTT1()( )0(1)!Kttf tetK 1/ k1/ k表示一个顾客的一个服务台的平均服务时间。服务时间的爱尔朗分布第74页/共188页75 例如： 某排队系统有并联的k个服务台，顾客流为泊松流，规定第i, K+i, 2K+i个顾客排入第i号

38、台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。例如：串联的k k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k k ），那么一顾客走完k k个服务台总共所需要服务时间就服从k k阶ErlangErlang分布。服务时间的爱尔朗分布第75页/共188页76第1节 基本概念第2节 到达间隔的分布和服务时间的分布第3节 单服务台负指数分布排队系统的分析第4节 多服务台负指数分布排队系统的分析第5节 一般服务时间M/G/1模型第6节 经济分析系统的最优化第7节 分析排队系统的随机模拟法排队论第76页/共1

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

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

41、就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。 下面拟分析几种常见排队系统模型。排队论第79页/共188页80 3.1 标准的M/M/1模型(M/M/1/) 3.2 系统容量有限的情况(M/M/1/N/) 3.3 顾客源有限的情形(M/M/1/m)第3节 单服务台负指数分布排队系统的分析本节讨论输入过程服从普阿松分布过程、服务时间服从负指数分布单服务台的排队系统。第80页/共188页81 标准的M/M/1模型 (1) 输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间内的到达数服从泊松分布，到达过程是平稳的。 (2) 排队规则单队，且对队长没

42、有限制，先到先服务。 (3) 服务机构单服务台，各顾客的服务时间相互独立，服从相同的负指数分布。 此外，还假定到达间隔时间和服务时间是相互独立的。 3.1 标准的M/M/1模型(M/M/1/)即已知条件：v ：顾客进入系统的平均速度；单位时间到达的顾客数。v ：顾客离开系统的平均速度；单位时间能被服务完成的顾客数。第81页/共188页82 首先要求出：系统在任意时刻t的状态为n(即系统中有n个顾客)的概率 ，它决定了系统运行的特征。 现仍然通过研究区间t，t+t）的变化来求解。在时刻t+t，系统中有n个顾客不外乎有下列四种情况（ t，t+t）内到达或离开2个以上没列入）。( )nP t3.1

43、标准的M/M/1模型(M/M/1/)第82页/共188页83 因已知到达规律服从参数为 的泊松过程，服务时间服从参数为 的负指数分布，所以在 时间区间内分为： (1) 有1个顾客到达的概率为 没有顾客到达的概率就是 (2) 当有顾客在接受服务时，1个顾客被服务完了(离去)的概率是 ， 没 有 离 去 的 概 率 就是 。 (3) 多于一个顾客的到达或离去的概率是 ，可以忽略。, t tt()tot 1()tot ()tot 1()tot ()ot3.1 标准的M/M/1模型(M/M/1/)第83页/共188页843.1 标准的M/M/1模型(M/M/1/) 在时刻 ，系统中有n个顾客(n0)存

44、在下列四种情况(到达或离去是2个以上的没列入)：表示发生(1个)；表示没有发生。tttt , t ttnn(D)nn-1(C)nn+1(B)nn(A)离去到达在时刻 顾客数在区间在区间在时刻t顾客数情况第84页/共188页85第85页/共188页86 这四种情况是互不相容的，所以 应是这四项之和，即 即 令 ，得关于 的微分差分方程 ()nP tt1111()( )(1 )( )( )()()( )()( )( )()( )nnnnnnnnnP ttP tttPttPttotP ttP totPtPtP ttt 0t ( )nP t11( )( )( )()( ) 1,2,(12 15)nnn

45、ndP tPtPtP tndt3.1 标准的M/M/1模型(M/M/1/)( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt 所有的高阶无穷小和并tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1 ()(1tOtttPn第86页/共188页87v当 ，则只有上表中(A)(B)情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可。且式(A)中无离去的概率为1，即v同理求得 它们的概率分别是 情况(A) 情况(B) 情况(C) 情况(D) tt , t ttnn(D)nn-1(C)nn+1

46、(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 )P ttP ttP ttt 001( )( )( )(12 16)dP tP tP tdt 第87页/共188页88 研究稳态的情况。这时 与时间t无关，可写成 ，它的导数为0。由(12-15)式和(12-16)式可得 这是关于 的差分方程，它表明了各状态间的转移关系：状态0转移到状态1的转移率为 ，状态1转移到状态0的转移率为 。

47、 ( )nP tnP01110(12 17,12 18)()0 1nnnPPPPPn0P1PnP3.1 标准的M/M/1模型(M/M/1/)这种系统状态(n)随时间变化的过程就是生灭过程（Birth and Death Process）。 方程(12-15)、(12-16) 解是瞬态解，无法应用。 第88页/共188页893.1 标准的M/M/1模型(M/M/1/) 对状态0必须满足以下平衡方程 同样对任何 的状态，可得如(12-18)所示的平衡方程。 由(12-17)式可得 将它代入(12-18)式，令 ，得到 同理依次推得 今设 (否则队列将排至无限远)，又由概率的性质知 即 ，得到01P

48、P1n10(/)PP220020()(/) (/)PPPPP；所以 1n 0(/)nnPP101nnP01 1(12 19)(1), 1nnPPn 0000111nnnnppP01110(12 17,12 18)()0 1nnnPPPPPn 第89页/共188页90 对的实际意义的解释/，是平均到达率与平均服务率之比，即在相同时区内顾客到达的平均数与被服务的平均数之比。 若将表示为(1/)/(1/)，它是一个顾客的服务时间与到达间隔时间之比，称为服务强度(traffic intensity)，或话务强度。 由(12-19)式可知，=1-P0，它刻画了服务机构的繁忙程度，所以又称为服务机构的利用

49、率。3.1 标准的M/M/1模型(M/M/1/) 系统处于空闲状态的概率： 10P 系统处于繁忙状态的概率： 010P)N(P第90页/共188页913.1 标准的M/M/1模型(M/M/1/) 根据平稳分布，求排队系统的有关运行指标(1) 系统中的平均顾客数（平均队长） 或 (2) 在队列中等待的平均顾客数 012323423(1)(23)(23), 0 11nsnnnLnPn sL1112(1)1qnnnnnnsLnPnPPL 期望 10P第91页/共188页92顾客在系统中的逗留时间W(为一个随机变量)在M/M/1情形下，服从参数为 的负指数分布，即 分布函数 概率密度 ()( )1 e

50、 0(1220)wF ww ()( )()ewf w 于是，得到(3) 在系统中顾客逗留时间的期望值 (4) 在队列中顾客等待时间的期望值 1sWE W1qsWW3.1 标准的M/M/1模型(M/M/1/) 平均逗留时间减去平均服务时间。第92页/共188页93 将以上结果归纳如下： 它们的相互关系如下： 上式称为Little公式。(1) (2) (1221)1(3) (4) sqsqLLWW(1) (2) (1222)1(3) (4) ssqqsqsqLWLWWWLL3.1 标准的M/M/1模型(M/M/1/)第93页/共188页943.1 标准的M/M/1模型(M/M/1/)Ls ,L q

51、, ,Ws ,Wq之间的关系：几何解释： 稳态时，一个顾客，进入系统后，每单位时间，平均到达顾客。 逗留时间的期望值Ws 进入时刻离开时刻队长Ls由时间段内个组成的Ls=Ws(1) (2) (12 22)1(3) (4) ssqqsqsqLWLWWWLL同理：Lq=Wq Ws=Wq+（1/）-Ws与Wq只相差一段平均服务时间1/ 第94页/共188页95泊松输入负指数分布服务的排队系统的一般决策过程： 根据已知条件绘制状态转移速度图； 依据状态转移速度图写出各稳态概率之间的关系； 求出 P0 及 Pn ； 计算各项数量运行指标； 用系统运行指标构造目标函数，对系统进行优化。3.1 标准的M/M

52、/1模型(M/M/1/)第95页/共188页96 例3 某医院手术室根据病人来诊和完成手术时间的记录，任意抽查了100个工作小时，每小时来就诊的病人数n的出现次数如下表所示；又任意抽查了100个完成手术的病历，所用时间v(单位：小时)出现的次数如下表所示。nf到达的病人数n出现人数010128229316410566以上以上1合计合计100vf为病人完成手术时间v(小时)出现人数0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上以上0合计合计1003.1 标准的M/M/1模型(M/M/1/)第96页/共188页97 (1) 每小时病人平均到达率

53、 (人/小时) 每次手术平均时间 (小时/人) 每小时完成手术人数(平均服务率) (人/小时) (2) 取 ， ，可以通过统计检验的方法，认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。 (3) 说明服务机构(手术室)有84%的时间是繁忙的，有16%的时间是空闲的。 (4) 依次代入(12-21)式，算出各指标： 在病房中病人数(期望值) (人) 排队等待病人数(期望值) (人) 病人在病房中逗留时间(期望值) (小时) 病人排队等待时间(期望值) (小时)2.1100nnf0.4100vvf52.52.

54、1sL 0.84 5.254.41qL sW 0.8qW 3.1 标准的M/M/1模型(M/M/1/)第97页/共188页983.1 标准的标准的M/M/1模型模型(M/M/1/)第98页/共188页993.1 标准的标准的M/M/1模型模型(M/M/1/)第99页/共188页1003.1 标准的标准的M/M/1模型模型(M/M/1/)第100页/共188页1013.1 标准的标准的M/M/1模型模型(M/M/1/)第101页/共188页1023.1 标准的标准的M/M/1模型模型(M/M/1/)第102页/共188页1033.1 标准的标准的M/M/1

55、模型模型(M/M/1/)第103页/共188页104解：本例可看成一个解：本例可看成一个M/M/1/ 排队问题，其中排队问题，其中 =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 标准的标

56、准的M/M/1模型模型(M/M/1/)第104页/共188页1053.1 标准的标准的M/M/1模型模型(M/M/1/)第105页/共188页106 如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。 当N=1时为即时制的情形；当N时为容量无限制的情形。3.2 系统的容量有限制的情况(M/M/1/N/)第106页/共188页107泊松输入负指数分布服务的排队系统的一般决策过程： 根据已知条件绘制状态转移速度图； 依据状态转移速度图写出各稳态概率之间的关系； 求出 P0 及 Pn ； 计算各项数量运行

57、指标； 用系统运行指标构造目标函数，对系统进行优化。3.2 系统的容量有限制的情况(M/M/1/N/)第107页/共188页1083.2 系统的容量有限制的情况(M/M/1/N/) 稳态情形下各状态间概率强度的转换关系图 状态概率的稳态方程 10111 (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-

58、 -1 1 一一人人到到达达（无无离离去去） N N P Pn n- -1 1( (t t) )t t ttPttPttPNNN)()1 ()()(1 )()()(1tPtPdttdPNNN 第108页/共188页1093.2 系统的容量有限制的情况(M/M/1/N/) 稳态情形下各状态间概率强度的转换关系图 状态概率的稳态方程 其中(12-23b)也可写成 ，则有10111 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP0(/)nnPP1001 (), 1 nnNNPPPPnNPP第109页/共188页1103.2 系统的容量有限制的情况(M/M/

59、1/N/) 由 1001 (), 1 nnNNPPPPnNPP N则 (/)nP0=1 n=0 N即 P0=1/(/)n= n=0(1-(1-/)/(1-()/(1-(/) )N N+1+1 1/(1/(N N +1) +1) = =011NPPP第110页/共188页111 M/M/1/N/排队系统的各项指标： (1) 队长(期望值) (2) 队列长(期望值) (3) 顾客逗留时间(期望值) (4) 顾客等待时间(期望值) (5) 有效到达率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系统的容

60、量有限制的情况(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/第111页/共188页112 (1) 平均队长Ls：nPnLnNnNNnns 01011nNnNn 0111111) 1(1 NNN (1) 试证=1=1时,Ls=N/2,Ls=N/23.2 系统的容量有限制的情况系统的容量有限制的情况(M/M/1/N/)0111 111 (1224)1NnnNPPnN第112页/共188页113 M/M/1/N/排队系统的各项指标： (1) 队长(期望值) (2) 队列长(期望值) (3) 顾客逗留时间(期望值) (4) 顾客等待时间(期望值) (5) 有效到达率