第六章排队论模型

1、12 排队论简介： 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是运筹学的一个主要分支，是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。主要包含以下三个方面的研究内容： (1)性态问题，即研究各种排队系统的概率规律性，如队长、等待时间、忙期等要素满足的分布。有瞬态和稳态两种情况。 (2)最优化问题，包括最优设计下的静态最优和现有排队系统的最优运营下的动态最优。 (3)排队系统的统计推断，即判断一个给定的排队系统符合何种模型，以便进一

2、步根据排队理论进行分析研究。 前前 言言3 起源于起源于19091909年在丹麦哥本哈根电子公司工作的电话工程年在丹麦哥本哈根电子公司工作的电话工程师师A. K. Erlang(A.K.A. K. Erlang(A.K.爱尔朗爱尔朗) )对电话通话拥挤问题的研究工作，对电话通话拥挤问题的研究工作，其开创性论文其开创性论文-概率论和电话通讯理论则标志此理论的诞生。概率论和电话通讯理论则标志此理论的诞生。表明了排队论的发展最早是与电话，通信中的问题相联系的，表明了排队论的发展最早是与电话，通信中的问题相联系的，并到现在也还是排队论的传统的应用领域。近年来在计算机通并到现在也还是排队论的传统的应用领

3、域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存管理等等各领域中均得到广泛的应用。管理等等各领域中均得到广泛的应用。 排队论历史： 排队是我们在日常生活和生产中经常遇到的现象。例如：搭乘公共排队是我们在日常生活和生产中经常遇到的现象。例如：搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队有形的排队之外，之外，还有大量的所

4、谓还有大量的所谓“无形无形”排队排队现象，如几个顾客打电话到出租汽车站要求现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：例如：通讯卫星与地面若干待传递的信息；生产线上是人，也可以是物：例如：通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的的原料、半成品等待加工；因故障停止运

5、转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。 排队论具体事例： 4 上述事例中的各种问题虽互不相同，但却都上述事例中的各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为机构。排队论里把要求服务的对象统称为“顾顾客客”, ,而把提供服务的人或机构称为而把提供服务的人或机构称为“服务台服务台”或或“服务员服务员”。不同的顾客与服务组成了各式各样。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服

6、务而到达系统、的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。等待队伍，待获得服务后离开系统。5模型模型1 1 单服务台排队模型单服务台排队模型排队模型及类型排队模型及类型 根据顾客到达和服务台数，排队过程可用下列模型表示：模型模型2 2 单队列多服务台并联的排队模型单队列多服务台并联的排队模型6模型模型3 3 多队列多服务台的并联排队模型多队列多服务台的并联排队模型模型模型4 4 单队多个服务台的串联排队模型单队多个服务台的串联排队模型7 模型模型5 5 多队列多服务台混联网络模型

7、多队列多服务台混联网络模型纵观上述排队模型，实际上都可由下面模型加以统一描述：纵观上述排队模型，实际上都可由下面模型加以统一描述： 称该统一模型为随机聚散服务系统。称该统一模型为随机聚散服务系统。由于顾客到来的时刻和服务台提由于顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此供服务的时间长短都是随机的，因此任一排队系统都是一个随机聚散任一排队系统都是一个随机聚散服务系统。服务系统。 “聚聚”表示顾客的到达表示顾客的到达,“,“散散”表示顾客的离去。表示顾客的离去。8 面对拥挤现象，人们总是希望尽量设法减少排队，面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施，但是增

8、加的数量越多，通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。样对顾客会带来不良影响。 顾客排队时间的长短与服务设施规模的大小，就顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。构成了设计随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用经济合理，

9、恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论设施费用大小这对矛盾。这就是随机服务系统理论排队论所要研究解决的问题。排队论所要研究解决的问题。9 一、排队系统的组成与特征一、排队系统的组成与特征 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。如下图所服务机构。如下图所示：示： 排队系统的基本概念排队系统的基本概念10 1、输入过程 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况： 1 1）顾客源可能是有限的，也可能是无限的。）顾客源可能是有限的，也可能是无限

10、的。 2 2）顾客是成批到达或是单个到达。）顾客是成批到达或是单个到达。 3 3）顾客到达间隔时间可能是随机的或确定的。）顾客到达间隔时间可能是随机的或确定的。 4 4）顾客到达可能是相互独立或关联的。所谓独）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。立就是以前顾客的到达对以后顾客的到达无影响。 5 5）输入过程可以是平稳的，也可以是非平稳的。）输入过程可以是平稳的，也可以是非平稳的。输入过程平稳的是指顾客相继到达的间隔时间分布和输入过程平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时参数（均值、方差）与时间无关；非平

11、稳的则是与时间相关，非平稳的处理比较困难。间相关，非平稳的处理比较困难。11 这是指服务台从队列中选取顾客进行服务的顺这是指服务台从队列中选取顾客进行服务的顺序。可以分为序。可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类。大类。 (1)(1)损失制。损失制。这是指如果顾客到达排队系统时，这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔愿等待而自动挂

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

13、客进行服务，这是最普遍的情形。 后到先服务（后到先服务（LCFSLCFS）。仓库中迭放的钢材，。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。后迭放上去的都先被领走，就属于这种情况。13 随机服务随机服务(RAND) 。即当服务台空闲。即当服务台空闲时，不按照排队序列而随意指定某个顾客去时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是接受服务，如电话交换台接通呼叫电话就是一例。一例。 优先权服务优先权服务(PR)。如老人、儿童先进。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理

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

15、过某一给定的长度等待时间不超过某一给定的长度T T，当等待，当等待时间超过时间超过T T时，顾客自动离去，不再回来。时，顾客自动离去，不再回来。 如易损坏的电子元器件的库存问题，如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。超过一定存储时间被自动认为失效。 又如顾客到饭馆就餐，等了一定时间后又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。不愿再等而自动离去另找饭店用餐。16 逗留时间逗留时间( (等待时间与服务时间之和等待时间与服务时间之和) )有有限。限。 例如用高射炮射击敌机，当敌机飞越高射例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为炮射击

16、有效区域的时间为t t时，若在这个时间时，若在这个时间内未被击落，也就不可能再被击落了。内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混不难注意到，损失制和等待制可看成是混合制的特殊情形，如记合制的特殊情形，如记c c为系统中服务台的个为系统中服务台的个数，则当数，则当K=cK=c 时，混合制即成为损失制；当时，混合制即成为损失制；当K=K=时，混合制即成为等待制。时，混合制即成为等待制。173 3、服务台、服务台 服务台可以从以下3方面来描述： (1) 服务台数量及构成形式服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队

17、单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及多队列多服务台并串联混合式等等。 如之前的分类模型图所示。如之前的分类模型图所示。18 (2) 服务方式服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。 (3) 服务时间的分布服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。19排队系统的描述符号与模型分类排队系统的描述符号与模型分类 为了

18、区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型(见前面分析与图示)。为了方便对众多模型的描述,DG肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：X X/Y/Z/A/B/C/Y/Z/A/B/C 各符号的意义如下：X X-表示顾客相继到达间隔时间分布，表示顾客相继到达间隔时间分布，常用下列符号：常用下列符号： MM表示到达过程为泊松过程或表示到达过程为泊松过程或( (负指数分布负指数分布Markov)Markov)； DD表示定长输入表示定长输入( (确定

19、型分布确定型分布Deterministic)Deterministic)； E EK K表示表示k k阶爱尔朗分布；阶爱尔朗分布； GI GI 一般相互独立的随机分布一般相互独立的随机分布( (General Independent)General Independent) G G表示一般的随机分布。表示一般的随机分布。20 Y Y-表示服务时间分布，表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。所用符号与表示顾客到达间隔时间分布相同。 Z-Z-表示服务台表示服务台( (员员) )个数：个数：“1”1”则表示单个服务台，则表示单个服务台，“s”s”。(s(s1)1)表表示多个服务台

20、。示多个服务台。 A-A-表示系统中顾客容量限额，表示系统中顾客容量限额，或称等待空间容量；或称等待空间容量； 如系统有如系统有K K个等待位子，则个等待位子，则 0K0K0),P(t0),Pn n(t1,t2)(t1,t2)表示在时间区间表示在时间区间t1,t2)(t2t1)t1,t2)(t2t1)内有内有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：)()(,1221ntNtNPttPn （t2t1，n0） 当当P Pn n(t1,t2)(t1,t2)同时符合下述三个条件时，顾客到达过程就是同时符合下述三个条件时，顾客到达过程就是泊松过程泊松过程( (顾客到达形成顾客到达形成

21、泊松泊松流流) )。 1 1、泊松分布、泊松分布27 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立, ,即即MarkovMarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状以前所处的状态无关。态无关。 平稳性：平稳性：即对于足够小的即对于足够小的tt，有：，有：)()(tttttP ，1泊松流具有如下特性：泊松流具有如下特性： 在在t,t+tt,t+t内有一个顾客到

22、达的概率与内有一个顾客到达的概率与t t无关无关, ,而与而与tt成正比。成正比。28 普通性：普通性：对充分小的对充分小的t,t,在时间区间（在时间区间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小. . 由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客到达的概率为：)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,则则P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t) 0 0 是常数，它是常数，它表示单位时间到达的顾客数，

23、称表示单位时间到达的顾客数，称为概率强度。为概率强度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 下面将讨论求关键的下面将讨论求关键的P Pn n(t)(t)。 29情情 形形 0 0， t t) ) 概概 率率 t t， t t+ + t t) ) 概概 率率 0 0， t t+ + t t ） A A n n P Pn n( (t t) ) 0 0 1 1- - t t + + O O( ( t t) ) P Pn n( (t t) )( (1 1- - t t + + O O( ( t t) ) ) B B n n- -1 1 P Pn n- -1

24、 1( (t t) ) 1 1 t t P Pn n- -1 1( (t t) ) t t n n- -2 2 P Pn n- -2 2( (t t) ) 2 2 n n- -3 3 P Pn n- -3 3( (t t) ) 3 3 . . . . . . . . . . . . C C 0 0 P P0 0( (t t) ) n O O( ( t t) ) O O( ( t t) ) 在在00，t+tt+t内到达内到达n n个顾客应是上面三种互不相个顾客应是上面三种互不相容的情况之一，所以有：容的情况之一，所以有： 为了求为了求Pn(t),即即Pn(0,t)，需要研究它在（，需要研究它在（

25、t，t+tt）上的改变）上的改变量量, ,建立建立P Pn n(t)(t)的微分方程。对于区间的微分方程。对于区间0,0,t+t)+t)可以分成可以分成00，t)t)和和tt，t+t),t+t),其到达总数是其到达总数是n n，不外有下列三种情况：，不外有下列三种情况：00,()0,nnnn kkkPttP ttPt P t tt30 令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条件）得：)()()(1tPtPdttdPnnn (3)(3) 当当n=0时，没有时，没有B，C两种情况，则：两种情况，则：)()(00tPdttdP1)0(0P (4)(4)()()1)()(1tOtt

26、PttPttPnnn)()()()()(1tOttPttPtPttPnnnnttOtPtPttPttPnnnn)()()()()(1 凑微分凑微分 区间长度（区间长度（0 0，0 0）有有n n个顾客到达个顾客到达 (0,t)(0,t)有有n-1,n-2n-1,n-2个个顾客到达顾客到达(0)0nP 即：即：31ln10tCC C C = 0 = 00ln( )Ptt （3 3）式两端乘）式两端乘e e t t并移项得：并移项得： te)t(P 0 (5)(5) （没有顾客到达的概率）（没有顾客到达的概率）dtPtdP )()(0000ln( )P ttC 两边积分得：两边积分得： 代入初始条

27、件代入初始条件( (t=0)t=0)有：有： P P0 0(0)=1(0)=1)t(P)t(Pdt)t(dPnnn1 )()(00tPdttdP(0)0nP32 将将n=1,2,3代入（代入（6）得：）得：tntnetPetPdtd )()(1 11101)()(dtetPetPtnttn (6)(6)110011)()(dtetPetPttt (注意利用注意利用(5)式式)tdteettt 1011tntntne )t (Pe )t (Pedt)t (dP 1tntnnte )t(Pe )t(Pdt)t(dPe 1 凑成凑成P Pn n(t)e(t)e t t两两项乘积的微分项乘积的微分 两

28、边积分两边积分te)t(P 033 如此继续递推下去得：如此继续递推下去得：tettP !2)()(22 （2 2个顾客到达的概率）个顾客到达的概率） （n n个顾客到达的概率）个顾客到达的概率）tnnenttP !)()( 即随机变量即随机变量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：和方差为：ttetP )(1 （1 1个顾客到达的概率）个顾客到达的概率）11011102111)()(dteetdtetPetPtttttt 2221t 34 引入级数引入级数.!nx.!xxenx 212 tkke!k)t( 0!)()()(11ntnetnPtNEnntnn

29、 )!1()(11 nttennt 令令k=n-1，则：，则：!)()(0kttetNEkkt tetetNEtt )(352121)()!1()()!2()(tntntttennnt tttttettett 22)()1()1(ttar )(N(V 即即：21221)(!)()()(tntnnettPnnntnn 22E(N(t)EN(t)( tNVar 同理方差为：同理方差为：211121)()!1()()!1()() 1()()!1()(tntntntetntnnennntnnt 说明顾客到达过程确实是一个说明顾客到达过程确实是一个泊松过程泊松过程( (泊松泊松流流) )，这也是泊松分布

30、的数学推导。这也是泊松分布的数学推导。36 其概率密度函数为：其概率密度函数为：tTTedtdF)t(f t0t02 2、负指数分布、负指数分布 当输入过程是泊松流时，我们研究两顾客相继到当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。达的时间间隔的概率分布。 设设T T为时间间隔，分布函数为为时间间隔，分布函数为F FT T（t t），则：），则：F FT T（t t）=PTt=PTt 此概率等价于在此概率等价于在0,t)0,t)区间内至少有区间内至少有1 1个顾客到达个顾客到达的概率。的概率。tTetPtF 1)(1)(0 t0t0tetP)(0 没有顾客到达的概率为：没

31、有顾客到达的概率为： (由（由（5）式而来）式而来) 间隔：间隔： 间隔：间隔： 间隔间隔 对分布函对分布函数微分数微分37 表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。 1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。 可以证明，间隔时间可以证明，间隔时间T T独立且服从负指数分布与独立且服从负指数分布与顾客到达形成泊松流是等价的。负指数分布是一种无顾客到达形成泊松流是等价的。负指数分布是一种无记忆性的分布。记忆性的分布。对顾客的服务时间对顾客的服务时间 ：系统处于忙期时系统处于忙期时两顾客相继离两顾客相继离开系统的时间间隔开系统的时间间隔，一般地也服从负指数分布

32、。，一般地也服从负指数分布。 即即T服从负指数分布，它的期望及方差为：服从负指数分布，它的期望及方差为： 1TE21 TVar 接受服务，然后离开接受服务，然后离开服务时间的分布：服务时间的分布：即：即：P(Xt+s|Xt)=P(Xs)P(Xt+s|Xt)=P(Xs)38其中：其中：表示单位时间内能被服务的顾客数，即平均表示单位时间内能被服务的顾客数，即平均 服务率。服务率。 1/1/表示一个顾客的平均服务时间。表示一个顾客的平均服务时间。3 3、爱尔朗、爱尔朗(Erlang)(Erlang)分布分布 设设v v1 1, v, v2 2，, v, vk k是是k k个独立的随机变量，服从相同个

33、独立的随机变量，服从相同参数参数 k k 的负指数分布，那么：的负指数分布，那么：tetF 1)(tetf )( ，则，则 令令 ，则，则称为服务强度称为服务强度。kT 21 令令39 串列串列k k个服务台个服务台，每台服务时间相互独立，服从，每台服务时间相互独立，服从相同负指数分布（参数相同负指数分布（参数k k ），那么一顾客走完），那么一顾客走完k k个服个服务台总共所需要服务时间服从上述务台总共所需要服务时间服从上述k k阶阶ErlangErlang分布。分布。011 te)!k()kt(k)t (ftkkk 则称则称T服从服从k阶阶爱尔朗分布。其特征值为：爱尔朗分布。其特征值为：

34、1TE21 kTVar ,其概率密度是其概率密度是1/ k1/ k表示一个顾客一个服务台的平均服务时间。表示一个顾客一个服务台的平均服务时间。 其他常用的分布参见教材其他常用的分布参见教材P122-123P122-123，也可参见概，也可参见概率论与数理统计相关教程。率论与数理统计相关教程。40生灭过程生灭过程1、生灭过程简介、生灭过程简介 一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。 2 2、生灭过程的定义、生灭过程的定义 设N(t),t0 为一个随机过程。 如N(t)的概率分布具有以下性质： (1)假设N(t)=

35、n，则从时刻t起到下一个顾客到达时刻止的时间服从参数为n的负指数分布，n=0，1，2，。间隔时间分布间隔时间分布 (2)假设N(t)=n，则从时刻t起到下一个顾客离去时刻止的时间服从参数为n的负指数分布，n=0，1，2，。服务时间分布服务时间分布 (3)同一时刻只有一个顾客到达或离去。 则称设N(t),t0 为一个生灭过程。41 顾客到达“生”； 顾客离开“灭” n ， n ，生灭过程示意图：顾客到达顾客到达顾客离去顾客离去42 一般说来，得到 是比较困难的或非理论作用不太大，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2, 为求平稳分布 ，考虑系统在 t+t 时刻可能处

36、的任一状态n的概率。可给出状态转移图如下：np( )( ) ( )nN tp tP N tn的分布np状态转移图状态转移图 说明：说明：n n状态下，排队系统中的人数稳定为状态下，排队系统中的人数稳定为n,n=0,1,2,.,n,n=0,1,2,.,即进了多少个就要出去多少个。即进了多少个就要出去多少个。43方式方式 t t时刻状态时刻状态t t状态的状态的概率概率（t,t+tt,t+t）内发生）内发生的事件的事件发生的概率发生的概率1n nP Pn n(t)(t)0 0人到达，人到达，0 0人离去人离去 （1-n nt） (1-n nt) 2n -1n -1P Pn-1n-1(t)(t)1

37、1人到达，人到达，0 0人离去人离去 n-1n-1t (1-n-1n-1t) 3n +1n +1P Pn+1n+1(t)(t)0 0人到达，人到达，1 1人离去人离去(1-n+1n+1t) n+1n+1t 4n nP Pn n(t)(t)1 1人到达，同时人到达，同时1 1人离人离去去(n nt) (n nt) 各种方式下发生概率表（保证各种方式下发生概率表（保证n状态状态:t+tt时刻时刻稳定有稳定有n个人）个人） 说明：状态说明：状态n n下，下，1 1人到达的概率约为人到达的概率约为 n ntt，1 1人离去的概人离去的概率约为率约为 n ntt，0 0人到达的概率约为人到达的概率约为1

38、-1-n ntt，0 0人离去的概率约为人离去的概率约为1-1-n ntt。( (根据根据泊松流的特征得到泊松流的特征得到) )44又因为前述方式1，2，3，4是互不相容且完备互不相容且完备的，因此有：111111()( ) (1)(1)( ) ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt 0()( )limnntP ttP tt1111( )( )()( )nnnnnnnPtP tPt对上式展开并构造如下极限式： ，则有：，则有： 这刚好就是这刚好就是P Pn n(t)(t)对对t t的导数。的导数。 事件事件(0,t+(

39、0,t+t)t)发生可发生可看作事件看作事件(0,t(0,t）和事件）和事件(t,t+(t,t+t)t)同时发生。因同时发生。因此：此：P(0,t+P(0,t+t)= t)= P(0,t)P(t,t+P(0,t)P(t,t+t)t)45当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则:00011( )( )( )dP tP tP tdt 设系统是稳态的，即与时刻t无关，于是可得：( )0ndPtdt0011111100()0,1,2,nnnnnnnPPnPPPn令P0已知，可用递推方法求得：4600110PP0101()PP0011122()0PPP1111122()0PPP

40、012011122()PPP 120011.nnnnnPP记12011.nnnnnC则平稳状态的分布为：0nnPC P 下面求下面求P P0 0。47由概率分布的要求：01nnP0111nnCP有：0111nnPC即综上述，得到各状态平衡时的概率分布递推计算式如下：12001101.11nnnnnnnPPPC 所以关键是得到各状态下单位时间单位时间到达和离开的人数：,0 ,1,nnn48例：某小型超市有一个收款台。付款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收

41、款时间将缩短至平均1min的负指数分布。求收款台前有n名顾客的概率Pn01.30/nh人16040/1.5h人260.60/1nh人解：这里的单位时间是1小时，所以491011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.=011111231511.( )42nnnnPC则有由0nnPC P可知：131231()()42552nnnP50 一般地，对排队模型，在给定输入和服务条件下，一般地，对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：主要研究系统的下述运行指标： (1)(1)系统的系统的平均队长平均队长L Ls s( (期望值期望值) )和和平

42、均队列长平均队列长L Lq q( (期望值期望值) )； (2)(2)系统中系统中顾客平均逗留时间顾客平均逗留时间W Ws s与队列中与队列中平均等待平均等待时间时间W Wq q；M/M/sM/M/s等待制排队模型等待制排队模型单服务台模型：单服务台模型： M/M/1/ M/M/1/ 是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。511、队长的分布、队长的分布(参数、就是单位时间进入或被服务的人数)所以n =( n=0，1，2，)，n =( n=0，1，2，)记 = / ，并设 1 (否则队列将排至无限远)， 则()n

43、nC0nnppn= 1,2,.，n= 1,2,而1100111()()111nnnnpC 因此(1)nnP n=0,1,2是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称为服务强度为服务强度，它反映了系统繁忙的程度。即为平衡条件下系统中顾客数为n的概率。522. 系统的运行指标计算系统的运行指标计算 (1) 系统中的队长系统中的队长Ls（平均队长：排队（平均队长：排队+被服务）被服务） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n (01) 1 期望期望53(2) 队列中等待的平均顾客数队列中等待的平均

44、顾客数Lq ：仅排队：仅排队 nnnnqnPnL 111) 1() 1( nnnn)(n 1111221sL (3) 顾客在顾客在系统中的平均逗留时间系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量，可以证顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为明，它服从参数为-的负指数分布，分布函数的负指数分布，分布函数 11nn54 和密度函数为：和密度函数为：w)(e)w(F 1w)(e )()w( f （w00）()ssLW 1sWE w (4) (4)顾客在顾客在队列中的平均逗留时间队列中的平均逗留时间W Wq q 111qsWW ()qqLW 等待时等待时间间 顾客在队列

45、中的平均逗留时间应为顾客在队列中的平均逗留时间应为W Ws s减去平均服减去平均服务时间。务时间。 考虑考虑L LS S与与W WS S的关的关系系55 LsLsLLqs 12WsLs WqLq 四个指标的关系为四个指标的关系为(Little Little 公式公式)： 3. 系统的忙期与闲期系统的忙期与闲期 系统处于空闲状态的概率：系统处于空闲状态的概率： 10P 系统处于繁忙状态的概率：系统处于繁忙状态的概率： 010P)N(P服服务务强强度度56 在繁忙状态下，队列中的平均顾客数在繁忙状态下，队列中的平均顾客数L Lb b：(0)qbsLLLP N 顾客平均等待时间顾客平均等待时间:1(

46、0)qbsWWWP N 忙期的平均长度忙期的平均长度: 1B 1IB ( (由由 来来) ) 一个忙期平均服务顾客数为：一个忙期平均服务顾客数为： 111 L Lb bP P(N0)(N0)=L=Lq q57例：某修理店只有一个修理工，来修理的顾客到达过程为Poisson流，平均4人/h; 修理时间服从负指数分布，平均需要6min。试求：（1）修理店空闲的概率（2）店内恰有3个顾客的概率（3）店内至少有1个顾客的概率（4）在店内的平均顾客数（5）每位顾客在店内的平均逗留时间（6）等待服务的平均顾客数（7）每位顾客平均等待服务时间（8）顾客在店内等待时间超过10min的概率58解 本例可看成一个

47、M/M/1/排队问题，其中124100.15（1）修理店空闲的概率02110.65p（2）店内恰有3个顾客的概率33322(1)() (1)0.03855p（3）店内至少有1个顾客的概率02110.45P Np 59（4）在店内的平均顾客数25250.6711L（5）每位顾客在店内的平均逗留时间0.67( )10(min)4LWh（人）（6）等待服务的平均顾客数2 22()5250.26711qLL（人）60（7）每位顾客平均等待服务的时间0.267( ) 4(min)4qqLWh（8）顾客在店内逗留时间超过10min的概率由于逗留时间服从参数 的负指数分布，即分布函数为()0tP Ttet

48、则10(1/6 1/15)1100.3679P Tee注：对于： 1小时 10 人 则 1分钟 10/60=1/6(人)。同理61多服务台模型：多服务台模型： M/M/s/M/M/s/ M/M/s/ 是指：设顾客单个到达，相继到达时间服从参数为的负指数分布，服务台数为s，每个服务台的服务时间相互独立，且服从参数为的负指数分布，系统空间无限，允许无限排队。当考虑系统处于平稳状态后队长N的概率分布,有(1,2. )(,1,2.)nnnnssss ss1、队长的分布62记ssc且1s有( /)!( /)( /)()!nnsn sn snCsss s n=1,2,sns故00,1,2,!,!nnnn spnsnPpnss s其中1100)!(1nssnspns63上面两个式子给出了平衡条件下系统中顾客数为n的概率，当ns时，即系统中顾客数大于服务台个数，这时再来的顾客必须等待，因此记：0( ,)!(1)snn ssc sPPsErlang等待公式它给出了顾客到达系统时需要等待的概率。由平稳状态下队长N的概率分布，可得到平均排队长Lq:021()!(1)ssqnnssPLns Ps 2、几个主要数量指标640( ,)!(