第九章 排队论

1、排队论课件,1,1909年 丹麦电话工程师A.K.埃尔朗：话务理论，导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。 20世纪30年代 苏联数学家.欣钦把处于统计平衡的电话呼叫流称为最简单流。 瑞典数学家巴尔姆又引入有限后效流等概念和定义。 20世纪50年代初 美国数学家关于生灭过程的研究 英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法。 L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。 20世纪70年代以来 人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势,排队论课件,2,第九章排队论

2、,第一节排队系统的基本概念 第二节 M/M/1排队模型 第三节 M/M/C排队模型 第四节 其它类型的排队模型 第五节 排队系统的优化应用,排队论课件,3,1、需求顾客 2、服务服务机构,第一节 基本概念,一、排队系统组成,排队可以是有形的，也可以是无形的。,排队系统,排队论课件,4,如果服务设施过少或服务效率太低，便会加剧拥挤，排队成龙。但增加服务设施便会增加服务成本或造成系统空闲，而有些服务设施如机场、港口泊位等一旦建成就不易改动。因此，有必要对排队系统的结构和运行规律加以研究，为排队系统的设计和调控提供依据。,现实世界中形形色色的排队系统,排队论课件,5,排队系统的三个基本组成部分. 输

3、入过程 arrival process(顾客按照怎样的规律到达); 排队规则 queuing discipline(顾客按照一定规则排队等待服务); 服务机构 Service agencies (服务机构的设置,服务台的数量,服务的方式,服务时间分布等),3.顾客是怎样接受服务,1.顾客是怎样到达的,排队论课件,6,1、输入过程,顾客来源的总体数或顾客源数 有限 m (如车间里待修理的机器) 无限 (如电话呼唤) 顾客到达的类型 单个 成批 顾客相继到达的时间间隔分布. 顾客到达间隔时间: 顾客相继到达的间隔时间分布是确定型的、还是随机型的，分布参数是什么，是否独立，是否平稳 服从某一概率分布

4、 (定长分布D，负指数分布),输入过程：描述顾客来源以及顾客到达排队系统的规律。包括：,排队论课件,7,2、排队规则（顾客接受服务的先后次序）,（1）损失制：指顾客到达时若所有服务设施均被占用，则顾客自动离去。（损失很多顾客） （2）等待制：顾客到达后，加入排队系统接受服务 先来先服务（FCFS，first come，first service）； 后来先服务（LCFS，last come， first service） ； 随机服务（SIRO，service in random order）； 有优先权的服务（PS，priority service）。,（3）混合制: 排队规则既允许排队又不

5、允许队列无限长 系统容量有限制 等待时间有限制,排队论课件,8,服务机构：描述服务台(员)的机构形式和工作情况。包括： 服务台个数 C= 服务时间分布：服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。 （指数, 常数,k级Erlang),3、服务机构（服务台）,1,1 并行多台,排队论课件,9,D.G.Kendall在1953年提出按照排队系统的三个最主要的、影响最大的特征要素进行分类：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。用符号（称为Kendall记号）表示为 X/Y/Z/A/B/C X：顾客相继到达的间隔时间分布， Y：服务时间的分布， Z：并列

6、的服务台个数。 A：系统容量限制， B：顾客源中的顾客数目; C：服务规则（如先到先服务FCFS，后到先服务LCFS）。 如略去后三项，即指X/Y/Z/FCFS的情形。 例如M/M/1，表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。,二、排队系统的符号表示,排队论课件,10,二、排队系统的符号表示,Server,Queue,Arrival,X/Y/Z/A/B/C 顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (Kendall 记号) M/M/1/FCFS （简记为M/M/1） M/M/C/N/ /FCFS，G

7、I/M/1/ M: 负指数分布 (兼指泊松输入) D: 定长分布 (常数时间) Er: Erlang 分布 GI: 一般相互独立的时间间隔的分布（general independent） G: 一般服务时间的概率分布 (任意概率分布),排队论课件,11,思考题,指出下面符号表示的含义 M/M/1/m G/D/C/N GI/Er/1/1 M/M/C/N/m,M: 负指数分布 (兼指泊松输入) D: 定长分布 (常数时间) Er: Erlang 分布 GI: 一般相互独立的时间间隔的分布（general independent） G: 一般服务时间的概率分布 (任意概率分布),排队论课件,12,三

8、、排队系统的主要数量指标及参数,一）主要指标 对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣，常用的指标：,1)队长：把系统中的顾客数称为队长，它的期望值记作L。而把系统中排队等待服务的顾客数称为排队长（队列长），它的期望值记作Lq。 队长排队长正被服务的顾客数。,排队论课件,13,2)逗留时间：一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间，它的期望值记作W。 一个顾客在系统中排队等待的时间称为等待时间，它的期望值记作

9、Wq。显然有 逗留时间等待时间服务时间。,3)瞬态和稳态 把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率，它是随时刻t而变化的，用Pn(t)表示，称为系统的瞬态。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限 lim Pn(t)Pn t 称为稳态或称统计平衡状态的解。,排队论课件,14,（二）主要参数,在处理实际排队系统时，需要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分布。 经验分布的主要指标如下： 总时间 平均间隔时间= 到达顾客总数 服务时间总和 平均服务时间= 顾客总数 到达顾客总数 平均到

10、达率= 总时间 顾客总数 平均服务率= 服务时间总和,排队论课件,15,（二）主要参数,顾客到达系统的平均速度， 1/ 顾客到达系统间隔时间的平均值. 系统中服务台的平均服务速度， 1/ 服务台对每一顾客的平均服务时间,排队论课件,16,例1：单人理发馆排队问题 有6个椅子接待人们排队，超过6人顾客就离开，平均每小时到达3人，理发需时平均15分钟。求系统中的最大顾客数、平均到达率、平均服务率。 解： 7为系统中的最大顾客数。 平均到达率3人/小时， 平均服务率4人/小时。,例2：某服务机构是单服务台，先到先服务，有41个顾客，第1个 顾客到达时刻为0，第41个顾客在第142分钟时到达，全部服务

11、时 间为127分钟。求平均间隔时间、平均到达率、平均服务时间、 平均服务率。,平均间隔时间=142/41=3.46(分钟/人) 平均到达率=41/142=0.288(人/分钟) 平均服务时间=127/41=3.12(分钟/人) 平均服务率=41/127=0.32(人/分钟),排队论课件,17,设N(t)表示在时间区间t0,t0+t)内到达的顾客数,是随机变量。当N(t)满足 (1)平稳性， (2)无后效性，(3)普通性 ，顾客的到达符合泊松分布。在t时间内有n个顾客到达的概率,1、泊松分布 Poisson distribution,(t)n Pn(t) e-t n=0,1,2, n! 其中表示

12、单位时间平均到达的顾客数，即到达率。 N(t)的数学期望和方差分别是： EN(t)t VarN(t)t,四 排队论中常见的几种概率分布,排队论课件,18,1)、平稳性 顾客到达是均匀的 在时间区间t0,t0+t)内到达的顾客数N(t)，即N个顾客到达的概率仅与区间长度t有关,而与这段时间的起始时刻无关。,2)、无后效性 任一时段的到达数不受前一时段的影响 在时间区间t0,t0+t)内到达的顾客数N(t)，与t0以前到达的顾客数独立，即与时刻t0以前时间所发生的概率无关。,3)、普通性（稀有性 瞬时内只可能有 1个顾客到达 在充分短的时间区间t内，即在某一瞬间同时到达两个或两个以上顾客的概率极小

13、， 即 Pn(t)o(t) n=2,例：餐厅就餐，柜台购物，急诊抢救。,排队论课件,19,2、负指数分布 negative exponential distribution,随机变量T 服从负指数分布，它的概率密度和分布函数若是 e-t t0 fT(t) 0 t0 1-e-t t0 FT(t) 0 t0 T的数学期望和方差分别为： ET1/， Var(T)1/2 1） 当顾客到达符合泊松分布时，顾客相继到达的间隔时间T必服从负指数分布。对于泊松分布，表示单位时间平均到达的顾客数（平均到达率），所以1/表示顾客相继到达的平均间隔时间，而这正和ET的意义相符。,2）服务时间常用的概率分布为负指数分

14、布时，设它的概率密度函数和分布函数分别为 fv(t)e-t； Fv(t)1-e-t (t0) 其中表示单位时间能够服务完的顾客数，为服务率；而1/表示一个顾客的平均服务时间，正是v的期望值。,排队论课件,20,3、 定长分布（deterministic distribution） 顾客相继到达时间间隔或每个顾客接受服务的时间是一个确定的常数 4、K 阶爱尔朗分布（Erlang distribution） k个串联服务台，每个服务台的服务时间相互独立，且服从平均服务时间均为1/k 的负指数分布，则该顾客走完这k个服务台所需时间t的概率密度。 K=1时，分布就是负指数分布，大于等于时，分布近似正态分布,排队论课件,21,5、指数分布与泊松分布的关系,指数分布,Poisson分布,到达间隔时间的概率 = t,在t时间内到达n个顾客的概率,1/: 平均服务时间,平均服务率= ,排队论课件,22,排队分布的检验,表9-1 患者在单位时间内到达数的频数分布,【例】某医院外科手术室任意抽查了100个工作小时，每小时患者到达数的出现次数如表9-1，问每小时患者的到达数是否服从泊松分布。,排队论课件,23,【例】求解,解：依题意，患者平均到达率 （人/小时）。现检验这个经验分布是否适合 =2.1的泊松分布，利用2检验法计算统计量，结果如表。,