第九章-排队论

1、 Part 4第四部分第四部分 排队论排队论 Chapter 9 第九章第九章排队论排队论9.1 基本概念基本概念 9.1.1 排队过程的一般表示排队过程的一般表示 9.1.2 排队系统的组成和特征排队系统的组成和特征 9.1.3 排队模型的分类排队模型的分类 9.1.4 排队系统的求解排队系统的求解主要内容主要内容9.2 几个主要概率分布几个主要概率分布 9.2.1 经验分布经验分布 9.2.2 Poisson分布分布 9.2.3 负指数分布负指数分布9.3 单服务台负指数分布排队系统分析单服务台负指数分布排队系统分析 9.3.1 标准标准M/M/1模型模型(M/M/1/) 9.3.2 系统

2、容量有限的情形系统容量有限的情形(M/M/1/N/) 9.3.3 顾客源为有限的情形顾客源为有限的情形(M/M/1/m)排队系统排队系统顾顾 客客服务台服务台服服 务务电话系统电话系统电话呼叫电话呼叫电话总机电话总机接通呼叫或取消呼叫接通呼叫或取消呼叫售票系统售票系统购票旅客购票旅客售票窗口售票窗口收款、售票收款、售票设备维修设备维修出故障的设备出故障的设备修理工修理工排除设备故障排除设备故障防空系统防空系统进入阵地的敌机进入阵地的敌机高射炮高射炮瞄准、射击直至敌机被击落或离开瞄准、射击直至敌机被击落或离开9.1 基本概念基本概念 9.1.1 排队过程的一般表示排队过程的一般表示举例：举例：

3、一般的排队过程为：顾客由顾客源出发，到达服务机一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的排队开。排队过程的一般过程可用下图表示。我们所说的排队系统就是指图中方框所包括的部分。系统就是指图中方框所包括的部分。 在现实生活中的排队现象是多种多样的，对上面所在现实生活中的排队现象是多种多样的，对上面所说的说的“顾客顾客”和和“服务员服务员”要作广泛的

4、理解。它们可以要作广泛的理解。它们可以是人，也可以是某种物质或设备。排队可以是有形的，是人，也可以是某种物质或设备。排队可以是有形的，也可以是无形的。也可以是无形的。9.1 基本概念基本概念 9.1.2 排队系统的组成和特征排队系统的组成和特征 尽管排队系统是多种多样的，但从决定排队系统进尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是输入程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构。过程、排队规则及服务机构。1)1)输入过程输入过程：描述顾客来源以及顾客到达排队系统的规：描述顾客来源以及顾客到达排队系统的规律。包括：律。包括

5、： 顾客源中顾客的数量是有限还是无限；顾客源中顾客的数量是有限还是无限； 顾客到达的方式是单个到达还是成批到达；顾客到达的方式是单个到达还是成批到达； 顾客相继到达的间隔时间分布是确定型的还是随机型顾客相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。的，分布参数是什么，是否独立，是否平稳。 2)2)排队规则排队规则：描述顾客排队等待的队列和接受服务的次序描述顾客排队等待的队列和接受服务的次序. .包括包括： 即时制还是等待制（即时制还是等待制（即时制又称损失制）即时制又称损失制） ； 等待制下队列的情况（是单列还是多列，顾客能不能中途等待制下队列的情况（是单列

6、还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移）；退出，多列时各列间的顾客能不能相互转移）； 等待制下顾客接受服务的次序（先到先服务，后到先服务，等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）。随机服务，有优先权的服务）。3)3)服务机构服务机构：描述服务台：描述服务台( (员员) )的机构形式和工作情况。的机构形式和工作情况。包括：包括： 服务台（员）的数目和排列情况；服务台（员）的数目和排列情况； 服务台（员）的服务方式；服务台（员）的服务方式； 服务时间是确定型的还是随机型的，分布参数是什么，是服务时间是确定型的还是随机型的，分布参数是什么

7、，是否独立，是否平稳。否独立，是否平稳。9.1 基本概念基本概念 9.1.3 排队模型的分类排队模型的分类 D.G.KendallD.G.Kendall在在19531953年提出了一个分类方法，按照系年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，统的三个最主要的、影响最大的三个特征要素进行分类，它们是：它们是：顾客相继到达的间隔时间分布、服务时间的分顾客相继到达的间隔时间分布、服务时间的分布、服务台数布、服务台数。按照这三个特征要素分类的排队系统，。按照这三个特征要素分类的排队系统，用符号（称为用符号（称为KendallKendall记号）表示为记号）表示为 X

8、/Y/ZX/Y/Z其中：其中：X X处填写顾客相继到达的间隔时间分布；处填写顾客相继到达的间隔时间分布； Y Y处填写服务时间的分布；处填写服务时间的分布； Z Z处填写并列的服务台个数。处填写并列的服务台个数。 常用的表示常用的表示相继到达间隔时间和服务时间的各相继到达间隔时间和服务时间的各种种分布如下：分布如下：M M 负指数分布（具有负指数分布（具有MarkovMarkov性）；性）；D D 定常分布；定常分布；E Ek k k k阶阶ErlangErlang分布分布 例如例如M/M/1M/M/1，表示顾客相继到达的间隔时间为表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、

9、单服务台的负指数分布、服务时间为负指数分布、单服务台的模型模型。 后来，在后来，在19711971年关于排队论符号标准化的会议上年关于排队论符号标准化的会议上决定，将决定，将KendallKendall符号扩充为：符号扩充为： X/Y/Z/A/B/CX/Y/Z/A/B/C 其中前三项意义不变其中前三项意义不变。 A A处填写系统容量限制；处填写系统容量限制； B B处填写顾客源中的顾客数目；处填写顾客源中的顾客数目； C C处填写服务规则（如先到先服务处填写服务规则（如先到先服务FCFSFCFS，后到先后到先服务服务LCFSLCFS）。）。 约定，如略去后三项，即指约定，如略去后三项，即指X/

10、Y/Z/FCFSX/Y/Z/FCFS的的情形。后面我们只讨论先到先服务情形。后面我们只讨论先到先服务FCFSFCFS的情形，所以的情形，所以略去第六项。略去第六项。9.1 基本概念基本概念9.1.4 排队系统的求解排队系统的求解 对于一个排队系统，运行状况的好坏既涉及到顾客的利对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的进措施，必须确

11、定一些基本指标，用以判断系统运行状况的优劣。下面介绍几种常用的指标。优劣。下面介绍几种常用的指标。 1)1)队长队长：把系统中的顾客数称为：把系统中的顾客数称为队长队长，它的期望值记作，它的期望值记作LsLs。而把系统中排队等待服务的顾客数称为而把系统中排队等待服务的顾客数称为排队长排队长（队列长）（队列长），它的期望值记作它的期望值记作LqLq。 队长排队长正被服务的顾客数队长排队长正被服务的顾客数 2)2)逗留时间逗留时间：一个顾客从到达排队系统到服务完毕离去的：一个顾客从到达排队系统到服务完毕离去的总停留时间称为总停留时间称为逗留时间逗留时间，它的期望值记作，它的期望值记作WsWs。 一

12、个一个顾客在系统中排队等待的时间称为顾客在系统中排队等待的时间称为等待时间等待时间，它的，它的期望值记作期望值记作WqWq。 3)3)瞬态和稳态瞬态和稳态 把系统中的顾客数称为系统的把系统中的顾客数称为系统的状态状态。考虑在考虑在t t时刻系统的时刻系统的状态为状态为n n的概率，它是随时刻的概率，它是随时刻t t而变化的，用而变化的，用P Pn n(t)(t)表示，称为表示，称为系统的系统的瞬态瞬态。求瞬态解是很不容易的，一般即使求出也很难。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限形式表示利用，因此我们常用它的极限形式表示 lim Plim Pn n(t)(t)P

13、Pn n t t称其称其为为稳态或称统计平衡状态的解稳态或称统计平衡状态的解。逗留时间等待时间服务时间逗留时间等待时间服务时间9.2 几个主要概率分布几个主要概率分布 9.2.1 经验分布经验分布 在处理实际排队系统时，需要把有关的原始资在处理实际排队系统时，需要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验料进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分分布，然后按照统计学的方法确定符合哪种理论分布。布。 经验分布的主要指标如下：经验分布的主要指标如下： 平均间隔时间平均间隔时间 平均服务时间平均服务时间 平均到达率平均到达率 平均服务率平

14、均服务率 主要指标计算如下：主要指标计算如下： 平均间隔时间平均间隔时间=总时间总时间/到达顾客总数到达顾客总数 平均服务时间平均服务时间=服务时间总和服务时间总和/顾客总数顾客总数 平均到达率平均到达率=到达顾客总数到达顾客总数/总时间总时间 平均服务率平均服务率=顾客总数顾客总数/服务时间总和服务时间总和9.2 几个主要概率分布几个主要概率分布 9.2.2 Poisson分布分布 在概率论中，我们已经知道随机变量的在概率论中，我们已经知道随机变量的PoissonPoisson分布分布。设随机变量。设随机变量X X服从服从PoissonPoisson分布，则：分布，则： 如果一个随机变量，概

15、率分布与时间如果一个随机变量，概率分布与时间t t有关，则称有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。数就是一个随机过程。), 2 , 1 , 0n, 0(! nenXPn 设设N(t)N(t)表示在时间区间表示在时间区间 t t0 0,t,t0 0+t)+t)内到达的顾客数，是随机变内到达的顾客数，是随机变量。当量。当N(t)N(t)满足下列四满足下列四个条件时个条件时，我们说顾客的到达符合，我们说顾客的到达符合PoissonPoisson分布。这四个条件是：分布。这四个条件是： (3)普通性普通性 在充分短

16、的时间区间在充分短的时间区间t内，到达多于内，到达多于1个顾客的概个顾客的概率极小，可以忽略不计，即率极小，可以忽略不计，即 Pn(t)o(t) n=2 (1)平稳性平稳性 在时间区间在时间区间 内到达的顾客数内到达的顾客数N(t)，只与区只与区间长度间长度t有关而与时间起点有关而与时间起点 无关。无关。 00 ,)t tt0t(2)无后效性无后效性 在在时间区间时间区间 内到达的顾客数内到达的顾客数N(t)，与与 以前到达的顾客数独立。以前到达的顾客数独立。 00 ,)t tt0t0()1kkPt(4)有限性有限性 任意有限个区间任意有限个区间内到达有限个内到达有限个顾客的概率等于顾客的概率

17、等于1，即即 在上述三个条件下可以推出，在在上述三个条件下可以推出，在0,t)0,t)内到达内到达n n个顾个顾客的概率为：客的概率为： ( (t)t)n n P Pn n(t)(t) e e-t-t n=0,1,2, n=0,1,2, n! n!不难算出，不难算出，N(t)N(t)的数学期望和方差分别是：的数学期望和方差分别是： EN(t)EN(t)t t VarN(t) VarN(t)tt那么，那么，EN(t)/t ，表示单位时间内到达的顾客数的期表示单位时间内到达的顾客数的期望值，即望值，即平均到达的顾客数平均到达的顾客数，称为平均到达率。，称为平均到达率。9.2 几个主要概率分布 9.

18、2.3 负指数分布 随机变量随机变量T T的概率密度若是的概率密度若是 ee-t-t t0 t0 f fT T(t)(t) 0 t 0 t 0 0则称则称T T服从负指数分布，它的分布函数是服从负指数分布，它的分布函数是 1- 1-e e-t-t t0 t0 F FT T(t)(t) 0 t 0 t 0 0 T T的数学期望和方差分别为：的数学期望和方差分别为： ETET1/1/， Var(T) Var(T)1/1/2 2 负指数分布具有下列性质：负指数分布具有下列性质： (1) (1)无记忆性或马尔柯夫性，即无记忆性或马尔柯夫性，即 PTt+s|TsPTt+s|TsPTtPTt (2) (2

19、)当顾客到达符合当顾客到达符合PoissonPoisson分布时，顾客相继到达的分布时，顾客相继到达的间隔时间间隔时间T T必服从负指数分布。必服从负指数分布。 对于对于 Poisson 分布，分布，表示单位时间平均到达的顾客数，表示单位时间平均到达的顾客数，所以所以1/1/表示顾客相继到达的平均间隔时间，而这正和表示顾客相继到达的平均间隔时间，而这正和ETET的的意义相符。因此，意义相符。因此，“到达的顾客数是一个以到达的顾客数是一个以为参数的为参数的Poisson流流”与与“顾客相继到达的时间间隔服从以顾客相继到达的时间间隔服从以为参数的负指数分布为参数的负指数分布”这这两个命题是等价的。

20、两个命题是等价的。 服务时间符合负指数分布时，设它的概率密度函数和分布服务时间符合负指数分布时，设它的概率密度函数和分布函数分别为函数分别为 f fv v(t)(t)ee-t-t； F Fv v(t)(t)1-e1-e-t-t (t0) (t0) 其中其中表示单位时间能够服务完的顾客数，称作平均服务表示单位时间能够服务完的顾客数，称作平均服务率；而率；而1/1/表示一个顾客的平均服务时间，正是表示一个顾客的平均服务时间，正是v v的期望值。的期望值。9.3 单服务台负指数分布排队系统分析单服务台负指数分布排队系统分析 9.3.1 标准标准M/M/1模型模型(M/M/1/) 排队系统的状态排队系

21、统的状态n随时间变化的过程称为生灭过随时间变化的过程称为生灭过程，设平均到达率为程，设平均到达率为,平均服务率为平均服务率为,负指数分布排负指数分布排队系统（队系统（M/M/1/）的生灭过程可用下面的状态）的生灭过程可用下面的状态转移图表示：转移图表示： 稳态概率方程如下：稳态概率方程如下： P0=P1 Pn-1+Pn+1=Pn+Pn01 n-1n n+1. PP10由第由第1个等式得：个等式得：PPP2011 ()由第由第2个等式，令个等式，令n2，得：，得：PPPP200201 ()代入解得：代入解得：用递推方法可以得到：用递推方法可以得到：01, 2,.nnPPn得得1P10n2 令令

22、，则，则 ，否则队列将排至无限远。，否则队列将排至无限远。 010kk1P由由 这里的这里的称为服务强度，它是平均到达率与平均服务率称为服务强度，它是平均到达率与平均服务率之比；即在相同时区内顾客到达的平均数与被服务的平均数之比；即在相同时区内顾客到达的平均数与被服务的平均数之比。它刻画了服务机构的繁忙程度，所以又称服务机构的之比。它刻画了服务机构的繁忙程度，所以又称服务机构的利用率。利用率。n2011P上式可表示为：上式可表示为：该级数收敛，有：该级数收敛，有：1111P0代入递推公式，有：代入递推公式，有：0(1),1nnnPPn 系统的各项运行指标计算如下：系统的各项运行指标计算如下：系

23、统中的平均顾客数（即对长期望值）系统中的平均顾客数（即对长期望值） 012323423(1)2323,011nsnnnLnPn1sL系统中的等待的平均顾客数（即排队长期望值）系统中的等待的平均顾客数（即排队长期望值） 1112(1),011qnnnnnnsLnPnPPL21qL顾客在系统中的逗留时间分布函数：顾客在系统中的逗留时间分布函数：()( )1xF xe1sW顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间 顾客在系统中的逗留时间顾客在系统中的逗留时间X服从参数为服从参数为 的的负指数分布，因此负指数分布，因此X的期望值即平均逗留时间为：的期望值即平均逗留时间为： 1()sWEXq

24、W顾客在系统中的平均等待时间顾客在系统中的平均等待时间 顾客在系统中的等待时间的期望值，等于顾客在系统顾客在系统中的等待时间的期望值，等于顾客在系统 中逗留时间的期望值减去接受服务的时间的期望值。中逗留时间的期望值减去接受服务的时间的期望值。111qsWW 对于（对于（M/M/1/）系统总结如下：）系统总结如下：(1)kkP系统中有系统中有k个顾客的概率为：个顾客的概率为： 系统中的平均顾客数为：系统中的平均顾客数为： ,011sL排队的平均长度为：排队的平均长度为：2, 011qsLL顾客逗留时间分布函数为：顾客逗留时间分布函数为：()()1wF weqsWW顾客在系统中的平均等待时间为：顾

25、客在系统中的平均等待时间为：顾客在系统中的平均逗留时间为：顾客在系统中的平均逗留时间为：1sW Little公式总结如下：公式总结如下：ssLWqqLW1sqWWsqLL 例例1：某修理店只有一名修理工，来修理：某修理店只有一名修理工，来修理的顾客到达过程为泊松流，平均每小时的顾客到达过程为泊松流，平均每小时4人。人。修理时间服从负指数分布，平均需要修理时间服从负指数分布，平均需要6min。试求：试求：修理店空闲的概率；修理店空闲的概率；店内有店内有3个个顾客的概率；顾客的概率；店内至少有店内至少有1个顾客的概率；个顾客的概率；在店内的平均顾客数；在店内的平均顾客数；等待服务的平均等待服务的平

26、均顾客数；顾客数；每位顾客在店内的平均逗留时间；每位顾客在店内的平均逗留时间；每位顾客平均等待修理的时间；每位顾客平均等待修理的时间；顾客在顾客在店内需消耗店内需消耗15min以上的概率。以上的概率。修理店空闲的概率：修理店空闲的概率：本例可以看作是一个标准的本例可以看作是一个标准的M/M/1模型，模型，4人人/h，1/6 人人/min=10人人/h， =/2/5。店内有店内有3个顾客的概率个顾客的概率:023110.655P 33322(1)10.03855P 店内至少有店内至少有1个顾客的概率个顾客的概率:0210.45P在店内的平均顾客数：在店内的平均顾客数：252520.67/113SLh人等待服务的平均顾客数等待服务的平均顾客数:2240.267/3515qSLLh人每位顾客在店内的平均逗留时间每位顾客在店内的平均逗留时间:211/346SSLWh人=10min 人每位顾客平均等待修理的时间每位顾客平均等待修理的时间:1111/61015qSWWh人=4min 人顾客在店内需消耗顾客在店内需消耗15min以上的概率以上的概率:11144P WP W 14()(10 4)1.511110.223weee 9.3 单服务台负指数分布排队系统分析单服务台负指数分布排队系统分析 9.3.2 系统容量有限制的情形系统容量有限制的情形(M/M/1/N/) 当系统的容