第12章排队论(清华教材)ppt课件.ppt

排 队 论,Queueing theory,一、排队系统的特征及排队论,第一节引言,排队论（queueing theory）是研究排队系统的数学理论和方法,排队论又叫随机服务系统理论。,在日常生活中，人们会遇到各种各样的排队问题。如进餐馆就餐，到图书馆借书，在车站等车，去医院看病，去售票处购票，上工具房领物品等等。在这些问题中，餐馆的服务员与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医生与病人、售票员与买票人、管理员与工人等，均分别构成一个排队系统或服务系统。,是运筹学的一个重要分支。,排队问题的表现形式往往是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥挤现象会愈来愈普遍。,一、排队系统的特征（2）,第一节引言（2）,排队除了是有形的队列外，还可以是无形的队列。,排队的可以是人，也可以是物。,如生产线上的原材料或半成品在等待加工；,因故障而停止运转的机器在等待修理；,码头上的船只等待装货或卸货；,要降落的飞机因跑道被占用而在空中盘旋等等。,当然，提供服务的也可以是人，也可以是跑道、自动售货机、公共汽车等。,为了一致起见，我们约定一些术语：,顾客,将要求得到服务的对象统称为“顾客”,服务员或服务机构,将提供服务的服务者称为“服务员或“服务机构”,排队系统的一般描述（1）,实际的排队系统可以千差万别，但都可以一般地描述如下：,顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统,排队系统的一般描述（2）,但不管具体的排队系统何种形式，都可描述成下列形式,多服务台串联排队系统,排队系统的一般描述（3）,上图通常称为一个随机聚散服务系统,任一排队系统都是一个随机聚散服务系统。,“聚”表示顾客的到达，“散”表示顾客的离去。,随机性则是排队系统的一个普通特点：,是指顾客的到达情况（如相继到达时间间隔）与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。,一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的.,因此，排队论又称为随机服务系统理论。,二、排队系统的描述,排队系统概括起来可看成由3个基本部分组成：,1.输入过程,输入过程说明顾客接怎样的规律到达系统，需要从三个方面来刻划一个输入过程,(1)顾客总体（顾客源）数,可以是有限的，也可以是无限的,河流上游流入水库的水量可认为是无限的,车间内停机待修的机器是有限的,输入过程,排队及排队规则,服务机制,(2)到达方式,是单个到达还是成批到达。,库存问题中，若把进来的货看成顾客，则为成批到达,(3)顾客（单个或成批）相继到达时间间隔的分布,这是刻划输入过程的最重要的内容,令T00，Tn表示第n个顾客到达的时刻,则有T0 T1 T2 Tn,输入过程(2),(3)顾客（单个或成批）相继到达时间间隔的分布,这是刻划输入过程的最重要的内容,令T00，Tn表示第n个顾客到达的时刻,则有T0 T1 T2 Tn,记Xn=Tn-Tn-1,(n1，2，),则Xn是第n个顾客与第n一1个顾客到达的时间间隔,一般，假定Xn是独立同分布的,记分布函数为A(t),输入过程(3),1)定长分布(D),顾客相继到达时间间隔为一常数a,如产品通过传送带进入包装箱就是定长分布的例子。,用随机变量表示所在顾客到达间隔时间，则,P(a)=1，用分布函数表示有：,其数学期望,关于Xn的分布，排队论中经常用到的有以下几种：,输入过程(4),称服从负指数分布，其分布函数为,负指数分布常作各种“寿命”分布的近似，例如无线电器元件的寿命、动物寿命、电话问题中的通话时间等,负指数分布的一个重要性质是无记忆性或无后效性,即,2)负指数分布（记为M）,一个随机变量，它的分布密度函数为,其数学期望,方差,输入过程(5）,3)最简流,或称 Poisson流(M),顾客相继到达时间间隔Xn为独立的,服从同参数的负指数分布,其密度函数为,（4）输入过程是平稳的或称对时间是齐次的,是指相继到达的间隔时间和所含参数（如期望值、方差等）都与时间无关的，否则称为非平稳的,2、排队及排队规则,排队分为有限排队和无限排队两类：,有限排队,是指排队系统中的顾客数是有限的,即系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统；,无限排队,是指系统中顾客数可以是无限的,队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务。,这类系统又称为等待制排队系统,对有限排队系统，可进一步分为两种：,(a)损失制排队系统,(b)混合制排队系统,2、排队及排队规则(2),(a)损失制排队系统,这种系统是指排队空间为零的系统,实际上是不允许排队。,当顾客到达系统时，如果所有服务台均被占用，则自动离去，并不再回来，称这部分顾客被损失掉了。,例如某些电话系统即可看作损失制排队系统。,(b)混合制排队系统,该系统是等待制和损失制系统的结合,一般是指允许排队，但又不允许队列无限长下去,具体说来，大致有三种：,队长有限：,即系统的等待空间是有限的。,例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。,如水库的库容是有限的，旅馆的床位是有限的。,等待时间有限：,即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。,如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。,2、排队及排队规则(3),2、排队及排队规则(4),逗留时间有限：,不难注意到，损失制和等待制可看成是混合制的特殊情形,等待时间与服务时间之和有限,例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。,如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，即成为等待制。,2、排队及排队规则(5),(2)排队规则,服务台对顾客进行服务所遵循的规则通常有：,当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。,先来先服务(FCFS)规则,即按顾客到达的先后对顾客进行服务，这是最普遍的情况,后来先服务(LCFS)规则,在许多库存系统中会出现这种情形，如钢板存入仓库后，需要时总是从最上面的权出；又如情报系统中，后来到达的信息往往更加重要，应首先加以分析和利用。,具有优先权的服务(PS)规则,服务台根据顾客的优先权进行服务，优先权高的先接受服务。如病危的患者应优先治疗，加急的电报电话应优先处理等。,3、服务机制的描述(1),排队系统的服务机制主要包括：,3服务机制,服务员的数量及其连接形式（串联或并联）,顾客是单个还是成批接受服务,服务时间的分布,在这些因素中，服务时间的分布更为重要一些,记某服务台的服务时间为V,其分布函数为B(t)，密度函数为b(t),则常见的分布有：,(1)定长分布(D),每个顾客接受服务的时间是一个确定的常数,(2)负指数分布(M),每个顾客接受服务的时间相互独立，具有相同的负指数分布：,其中0为一常数,3、服务机制的描述(2),(3)K阶爱尔朗分布(EK),每个顾客接受服务的时间服从 k阶爱尔朗分布，其密度函数为,其中0，为一常数,爱尔朗分布比负指数分布具有更多的适应性,当k=1时，爱尔朗分布即为负指数分布；,当k增加时，爱尔朗分布逐渐变为对称的,事实上，当k30以后，爱尔朗分布近似于正态分布。,当k时，由方差为1/k2可知，方差将趋于零，即为完全非随机的。,所以，K阶爱尔朗分布可看成完全随机（K=1）与完全非随机之间的分布，能更广泛地适应于现实世界。,三、排队系统的符号表示和模型分类,可根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类：,D.G.Kendall提出一种目前在排队论中被广泛采用的“Kendall记号”,A表示系统的容量，即可容纳的最多顾客数,其一般形式为：,XYZABC,其中X表示顾客相继到达时间间隔的分布；,Y表示服务时间的分布；,B表示顾客源的数目,Z表示服务台的个数；,C表示服务规则,例如，MM1FCFS,表示了一个顾客的到达时间间隔服从相同的负指数分布、服务时间为负指数分布、单个服务台、系统容量为无限（等待制）、顾客源无限、排队规则为先来先服务的排队模型。,三、排队系统的符号表示(2),在排队论中，一般约定如下：,如果 Kendall记号中略去后 3项时,例如：MM1 FCFS,表示为MM1的排队模型,MMsK,则表示了一个顾客相继到时间间隔服从相同的负指数分布、服务时间为负指数分布、s个服务台、系统容量为K、顾客源无限、先来先服务的排队模型。,是指XYZ FCFS的情形,GIM1,则表示一个单服务台、服务时间为负指数分布、顾客相继到达时间间隔为独立同分布的等待制排队模型，,四.排队系统的主要数量指标和记号,1队长和排队长,队长,是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和），它的期望值记为LS,排队长：,是指系统中正在排队等待服务的顾客数。它的期望值记为Lq,队长和排队长一般都是随机变量,对这两个指标进行研究时，当然是希望能确定它们的分布，或至少能确定它们的平均值（即平均队长和平均排队长）及有关的矩（如方差等）。,队长的分布是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而确定合理的等待空间。,四.排队系统的主要数量指标和记号(2),2等待时间和逗留时间,等待时间：,是从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，,它的期望值记为Wq,也是顾客最关心的指标，因为顾客通常是希望等待时间越短越好。,逗留时间：,是从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间,它的期望值记为WS,对这两个指标的研究当然是希望能确定它们的分布,或至少能知道顾客的平均等待时间和平均逗留时间,逗留时间等待时间服务时间,四.排队系统的主要数量指标和记号(3),3忙期和闲期,忙期：,这是个随机变量,是服务员最为关心的指标，因为它关系到服务员的服务强度。,是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间,即服务机构连续忙的时间,闲期：,服务机构连续保持空闲的时间,在排队系统中，忙期和闲期总是交替出现的。,除了上述几个基本数量指标外，还会用到其它一些重要的指标,如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。,四.排队系统的主要数量指标和记号(4),下面给出上述一些主要数量指标的常用记号：,当部分排队系统在运行了一定时间后，都会趋于一个平衡状态（或称平稳状态）。,在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。,因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,系统的状态即指系统中顾客数，如果系统中有n个顾客就说系统的状态是n。,四.排队系统的主要数量指标和记号(5),记Pn(t)为时刻t时系统处于状态n的概率，即系统的瞬时分布,N：系统处于平稳状态时的队长,其均值为LS,称为平均队长,n：当系统处于状态n时，新来顾客的平均到达率,T：系统处于平稳状态时顾客的逗留时间，其均值记为WS，称为平均逗留时间；,Tq：系统处于平稳状态时顾客的等待时间，其均值记为Wq，称为平均等待时间；,Nq:系统处于平稳状态时的排队长，其均值为Lq,称为平均排队长,根据前面的约定，我们将主要分析系统的平稳分布，,当系统达到统计平衡时处于状态n的概率，记为Pn,单位时间内来到系统的平均顾客数,四.排队系统的主要数量指标和记号(6),n：当系统处于状态n时，整个系统平均服务率,单位时间内可以服务完的顾客数,当每个服务台的平均服务率为常数时，记每个服务台的服务率为,因此，顾客相继到达的平均时间间隔为 1/,平均服务时间为 1/,例2（p308),某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻T和服务时间S，第1号顾客到达时刻为0，全部服务时间为127分钟,(1)顾客编号i,(2)到达时刻Ti,(3)服务时间Si,(4)到达间隔ti,(5)排队等待时间Wi,ti=Ti+1-Ti,Wi+1=Wi+Si-ti,五、排队论研究的基本问题,排队论研究的首要问题是排队系统主要数量指标的概率规律,即研究系统的整体性质，然后进一步研究系统的优化问题,与这两个问题相关的还包括排队系统的统计推断,(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及 其数字特征，了解系统运行的基本特征。,（2）统计推断问题，建立适当的排队模型是排队论研究的 第一步，建立模型过程中经常会碰到如下问题：检验 系统是否达到平稳状态；检验顾客相继到达时间间隔的 相互独立性；确定服务时间的分布及有关参数等。,（3）系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。,系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客（或服务）根据优先权的最优排序等方面的问题,第二节 生灭过程和Poisson过程,一、生灭过程简介,如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，N(t)，t0 也是一类特殊的 随机过程生灭过程。,在排队论中，如果N(t)表示时刻t系统中的顾客数，,则N(t)，t0就构成了一个随机过程,定义1 设N(t)，t0 是一个随机过程。若N(t)的概率分布具 有以下性质：,(1)设N(t)=n,则从时刻t起到下一个顾客到达时刻止的时间 服从参数为n的负指数分布，n=0,1,2,(2)假设 N(t)=n，则从时刻 t起下一个顾客离去时刻止的 时间服从参数为n的负指数分布，n=0,1,2,(3)同一时刻只有一个顾客到达或离去。,则称N（t），t0为一个生灭过程。,一、生灭过程定义(2),一般说来，得到N(t)的分布Pn(t)=PN(t)=n（n=0,1,2,)是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为 pn，n=0,1,2,为求平稳分布，考虑系统可能处的任一状态n,假设记录了一段时间内系统进入状态n和离开状态n的次数，则因为“进入”和“离开”是交替发生的，所以这两个数要么相等，要么相差为1。,但就这两种事件的平均发生率来说，可以认为是相等的,即当系统运行相当时间而达到平稳状态后，对任一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应该相等,这就是系统在统计平衡下的“流入=流出”原理。,根据这一原理，可得到任一状态下的平衡方程如下：,一、生灭过程简介(3),根据在统计平衡下的“流入=流出”原理，得,n=0,1,2,由上述平衡方程得：,记,由概率分布,二、Poisson 过程和指数分布,Poisson 过程,又称为Poisson流，最简流,是排队论中经常用到的一种用来描述顾客到达规律的特殊随机过程,与概率论中的Poisson分布和负指数分布有密切的联系,定义：设N(t)为时间0，t内到达系统的顾客数，如果满足下面三个条件：,(2)独立性：任意两个不相交的区间内顾客到达情况 相互独立(无后效性）,(1)平稳性：在t,t+t内有一个顾客到达的 概率为 t+(t),(3)普通性：在t,t+t内多于一个顾客到达的 概率为(t),则称N(t)，t0为Poisson过程,二、Poisson 过程和指数分布（2）,Poisson过程与Poisson分布的关系：,定理1：设N(t)为时间0，t内到达系统的顾客数,即表明到达的顾客数的分布恰为Poisson分布,n=1,2,3,.,则N(t)，t0为Poisson过程的充要条件是：,定理2：设N(t)为时间0，t内到达系统的顾客数,则N(t)，t0为Poisson过程的充要条件是：,相继到达时间间隔服从相互独立的参数为的负指数分布,第三节 单服务台负指数分布排队系统,一、标准的M/M/1模型,(1)顾客的相继到达时间间隔服从参数为的负指数分布，顾客单个到达，相互独立；(2)服务台数为1；(3)服务时间V服从参数为的负指数分布，服务时间相互独立；(4)系统空间无限；(5)单队，队长无限制，即允许永远排队；(6)先到先服务；,M/M/1/是指:,为了分析此模型，先求出系统在任意时刻的状态n（系统中有n个顾客）的概率Pn(t)，,Pn(t)决定了系统运行的特征,一、单服务台M/M/1/模型(2),因为顾客的到达间隔时间服从参数为的负指数分布服务时间V服从参数为的负指数分布，故t，t+t)时间内分为：,(1)有一个顾客到达的概率为t(t);没有顾客到达的概率就是1 t(t);,在时刻t+t 有n个顾客存在下列四种情况（到达或离去是2个以上忽略掉）：,(2)当有顾客在接受服务时，1个顾客被服务完离去的概率为t(t);没有顾客离去的概率就是1 t(t);,(3)多于1个顾客到达或离去的概率是(t),可以忽略,一、单服务台M/M/1/模型(3),t，t+t)时间的四种情况：,情况(A)发生的概率：,Pn(t)(1-t)(1-t)(t);,情况(B)：,Pn+1(t)(1-t)t(t);,情况(C)：,Pn-1(t)t(1-t)(t);,情况(D)：,Pn(t)t t(t);,这四种情况是互不相容的，则Pn(t+t)是这四种情况之和,一、单服务台M/M/1/模型(4),Pn(t+t)=Pn(t)(1-t)(1-t)Pn+1(t)(1-t)t+Pn-1(t)t(1-t)+Pn(t)t t+(t);,忽略 t的高阶无穷小,并整理得,令 t0，得微分方程：,Pn(t+t)=Pn(t)(1-t-t)Pn+1(t)t+Pn-1(t)t+(t);,n=1,2.,当n=0时，只有（A）、（B）两种情况发生，即,一、单服务台M/M/1/模型(5),当n=0时有,P0(t+t)=P0(t)(1-t)P1(t)(1-t)t+(t);,则有,Pn(t)随时间变化而变化，求出Pn(t)是很困难的，下面我们考虑稳态的情况：,由于Pn(t)与时间t无关（记Pn)，则,n=0,1,2.,从而Pn满足下列关系：,是一个关于Pn的差分方程,一、单服务台M/M/1/模型(6),它表明了各状态间的转移关系：,差分方程的解为：,一、单服务台M/M/1/模型(7),平稳状态下的系统状态概率：,记,（否则队列排至无限长）,由概率分布,得,这是系统达到平稳状态后队长为n的概率,一、单服务台M/M/1/模型(8),的实际意义：,又顾客相继到达的平均时间间隔为 1/,平均服务时间为 1/,因此，称为系统的服务强度,是顾客的平均到达率,是平均服务率,故(1)是在相同时间内顾客到达的平均数与被服务的平均顾客数之比,(2)也是一个顾客的服务时间与到达间隔时间之比,它刻画了服务机构的繁忙程度,一、单服务台M/M/1/模型（9）,M/M/1/模型的几个主要数量指标：,(1)平均队长LS,在队列中等待的平均顾客数(队列长期望值),即在系统中的平均顾客数(队长期望值),(2)平均排队长Lq,一、单服务台M/M/1/模型(10),(3)在系统中顾客逗留时间的期望值WS,可证明它服从参数为-的负指数分布，即,W的分布函数：,设顾客在系统中的逗留时间为W,则在系统中顾客逗留时间的期望值WS,WS=E(W),W的概率密度函数：,一、单服务台M/M/1/模型(11),(4)在队列中顾客等待时间的期望值Wq,逗留时间W=等待时间Tq+接受服务时间V,则WS=E(W)=E(Tq)+E(V),Wq=E(Tq)WSE(V),故平均队长、平均排队长、平均逗留时间、平均等待时间有如下关系：,一、单服务台M/M/1/模型(12),平均队长LS,因此，平均队长LS与平均逗留时间WS具有关系,LS=WS.(1),平均逗留时间WS,平均排队长Lq,平均排队长Lq与平均逗留时间Wq具有关系:,Lq=Wq.(2),平均等待逗留时间Wq,这(1)、(2)、(3)、(4)式通常称为Little公式,WSWq1/.(3),平均逗留时间与平均等待时间的关系：,平均队长与平均排队长的关系：,LSLq/.(4),一、忙期与闲期(1),求它们的分布是比较麻烦的,在平衡状态下，忙期B和闲期I一般均为随机变量,3忙期和闲期,因此，我们来求出平均忙期E(B)和平均闲期E(I),由于忙期和闲期出现的概率分别为和1-，,所以在一段时间内可以认为忙期和闲期的 总长度之比为：1-,又因为忙期和闲期是交替出现的,所以在充分长的时间里，它们出现的平均次数应是相同的。,于是，忙期的平均长度E(B)和闲期的平均长度E(I)的之比也应是：1-,因为在到达情况服从 Poisson流时，根据负指数分布的无记忆性和到达与服务相独立的假设,一、忙期与闲期(2),易证明：从系统空闲时刻起到下一个顾客到达时刻止(即闲期)的时间仍服从参数为的负指数分布，且与到达时间间隔相互独立,平均逗留时间W=平均忙期E(B),因此，平均闲期应为1/,则平均忙期E(B),这一结果也是直观的,顾客在系统中逗留的时间越长，服务员连续忙的时间也就越长,因此，一个顾客在系统内的平均逗留时间应等于服务员平均连续工作的时间,一、单服务台模型(例1),例1 某修理店只有一个修理工，来修理的顾客到达过程为Poisson流，平均4人/小时；修理时间服从负指数分布，平均需要6分钟。试求：（1）修理店空闲的概率；（2）店内恰有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）在店内的平均顾客数；（5）每位顾客在店内的平均逗留时间；（6）等待服务的平均顾客数（7）每位顾客平均等待服务时间；（8）顾客在店内逗留时间超过10分钟的概率。,解：,这是一个M/M/1/排队模型问题,平均到达率4,平均服务率1/0.110人/小时,0.4,一、单服务台模型(例12),（1）修理店空闲的概率,（2）店内恰有3个顾客的概率,P0110.40.6,（3）店内至少有1个顾客的概率,（4）在店内的平均顾客数,0.67人,P3 3（1）0.038,Pn01P0 0.4,（5）每位顾客在店内的平均逗留时间,（小时）10分钟,一、单服务台模型(例13),（6）等待服务的平均顾客数Lq,（7）每位顾客平均等待服务时间,（8）顾客在店内逗留时间超过10分钟的概率,e-1=0.3679,因为LSLq/,LqLS 0.27人,0.27/44分钟,一、单服务台模型(例2),例2 考虑一个铁路列车编组站，设待编列车到达时间间隔服从负指数分布，平均到达2列/小时；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平稳状态下系统中列车的平均数；每一列车的平均停留时间；等待编组的列车的平均数。如果列车因站中的2股道均被占用而停在站外或前方站时，每列车的费用为a元/小时，求每天由于列车在站外等待而造成的损失。,解：,这是一个M/M/1/排队模型问题,2,3,一、单服务台模型(例22),解：,(1)系统中列车的平均数,2,3,2/3,2列,(2)列车在系统中平均停留时间,（小时）,(3)系统内等待编组的列车平均数,LqLS 22/3=4/3列,(4)记列车平均延误（由于站内2股道均占用而不能进站）时间为W0,一、单服务台模型(例23),(4)记列车平均延误（由于站内2股道均占用而不能进站）时间为W0,故每天列车由于等待而支出的平均费用E：,E24 W0a=14.2a(元）,二、系统容量有限制的情况(M/M/1/N/),一、单服务台模型混合制模型,(1)顾客的相继到达时间服从参数为的负指数分布,M/M/1/N/是指:,(2)服务台数为1个,(3)服务时间V服从参数为的负指数分布,(4)服务系统空间为N：当系统中有N个顾客时，达到的顾客不进入系统等待；当系统中少于N个 顾客时，到达的顾客可进入系统等待服务。,(5)顾客源为无限,(6)服务规则为先到先服务。,该模型 可用下列图来描述：,二、M/M/1/N/(2),当N=1时为即时制情形，也是损失制情形,M/M/1/N/:,当N=时为容量无限制的情形，也即等待制的,下面我们讨论在平稳状态下数量指标,因系统空间无限时的系统状态转移关系图为：,二、M/M/1/N/(3),则系统空间为N时的系统状态转移关系图为：,系统各状态概率的稳态方程：,因为,记,当n=1,2,K,二、M/M/1/N/(4),和,当1时的平均队长L,现已求出系统达到平稳状态后队长N的概率分布,所以,当 1,当=1,因,当n=1,2,K,当=1时的平均队长L,二、M/M/1/N/(5),当系统空间被占满时，顾客再来就会被拒绝,所以,当 1,当=1,类似地可求出排队长Lq,从而可进入系统的概率为,则拒绝概率为,单位时间内可进入系统的顾客平均数为,二、M/M/1/N/(6),平均逗留时间WS,平均等待时间 Wq,根据Little公式，可得,这是因为,且两者具有关系：,而,二、M/M/1/N/(7),特别，当N=1时，M/M/1/1为单服务台损失制系统,平均队长L,平均逗留时间W,二、M/M/1/N/例题1,例单人理发馆有6张椅子接待人们排队等待理发。当6张椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。试求：（1）求某一顾客一到达就能理发的概率；（2）求需要等待的顾客数的期望值；（3）求有效到达率；（4）求一顾客在理发馆内逗留的期望时间（5）求在可能到来的顾客中不等待就离开的概率,解：N7,3人/小时,4人/小时,（1）求某一顾客一到达就能理发的概率,0.2778,（2）求需要等待的顾客数的期望值；,二、M/M/1/N/例题12,（2）求需要等待的顾客数的期望值；,2.11人,（3）求有效到达率,1.39人,2.89人/小时,（4）求一顾客在理发馆内逗留的期望时间,0.73小时,（5）求在可能到来的顾客中不等待就离开的概率,0.037,二、M/M/1/N/例题13,针对上述的理发馆的问题，下面我们来比较下队长为有限和无限的情况：,从上表可知，无限队长的情况要比有限队长的情形忙,三、顾客源为有限的情形 M/M/1/m,机器故障停机待修问题：,有m台机器（顾客总体），机器因故障停机表示“到达”，待修的机器形成队列，修理工人是服务员。因每台机器修理后仍然会发生故障，因此，每台机器仍回到顾客总体中。,这样的问题可用下图来表示：,三、M/M/1/m（2）,i)在无限源情况下，顾客的平均到达率是按全体顾客来考虑的,ii)在有限源情况下，顾客的平均到达率应是按每个顾客来考虑的,设各个顾客的到达率都是相同的（其含义是每台机器单位运转时间内发生故障的概率或平均次数）,三、M/M/1/m（3）,设各个顾客的到达率都是相同的（其含义是每台机器单位运转时间内发生故障的概率或平均次数）,则在系统外的顾客平均数(即没进入排队的顾客),mLS,或者在正常运行的机器数：,对系统的有效到达率为,三、M/M/1/m（4）,下面考虑在稳态的情况时的状态转移率：,(1)当由状态0转移到状态1，每台设备由正常状态转移为故障状态，其转移率为P0,其关系可表示成如下图：,现有m台设备由无故障转移为有一台设备（不论哪一台）发生故障，其转移率为mP0,则在状态0时有平衡方程：,(2)当由状态1转移到状态0，其转移率为P1,三、M/M/1/m（5）,其关系可表示成如下图：,则可得系统各状态概率的稳态方程：,因为,则解之得,三、M/M/1/m（6）,求得系统各状态概率：,求得系统的各项指标：,三、M/M/1/m（7）,系统各项指标：,LS是平均发生故障的台数,则mLS是正常运转的平均台数,二、M/M/1/m例题1,例某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次服务时间服从负指数分布，平均每次12分钟。试求：（1）修理工空闲的概率；（2）5台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的平均台数；（5）平均停工时间；（6）平均等待修理时间（7）评价这些结果,解：m5,1/15(台/分),1/12(台/分),第4节多服务台排队系统的分析,一、M/M/C/,(1)顾客的相继到达时间服从参数为的负指数分布,(2)服务台数为C个,(3)每个服务台的服务时间相互独立，且服务时间V 服从参数为的负指数分布,(4)当顾客到达时，若有空闲的服务台，则可马上接 受服务。否则便排成一个队列等待。,(5)系统等待空间无限，允许永远排队。,(6)顾客源为无限,(7)服务规则为先到先服务。,下面我们讨论在平稳状态下数量指标,一、M/M/C/(2),M/M/C/:,称它为该系统的服务强度或服务机构的平均利用率,系统顾客到达率为,系统的服务率,当nC时,当nC时,记,一、M/M/C/(3),M/M/C/中的状态间转移可以由下图描述：,当nC时,当nC时,当nC时,状态n转移到n1的概率为nPn,当n C时,状态n转移到n1的概率为CPn,一、M/M/C/(4),则得系统各状态间转移的差分方程：,这同样有,和,用递推法解上述差分方程，得状态概率：,当nC时,当nC,一、M/M/C/(5),其中,M/M/C/系统中各状态概率：,顾客进入系统必须等待的概率,称为Erlang等待公式,一、M/M/C/(6),下面求系统达到平稳状态各个指标值,平均排队长,这就是多服务台排队系统的平均排队长,一、M/M/C/(7),而系统中正在接受服务的顾客平均数,平均在忙的服务台个数不依赖于服务台个数S,平均队长LS=,平均排队长Lq,+正在接受服务的顾客平均数,因此,再由Little公式得,平均逗留时间WS,平均等待时间 Wq,一、M/M/C/(8),例 某售票处有三个窗口，顾客的到达为Poisson流，平均到 达率为0.9人/分钟，服务(售票)时间服从负指数分布，平 均服务率为0.4人/分钟。现设顾客到达后排成一个队列，依次向空闲的窗口购票。分析该系统的情况。,购票如图所示,解：,该问题可看作一个M/M/C/排队问题,根据公式 计算结果如下,C=3,一、M/M/C/(9),根据公式 计算结果如下,(1)售票处空闲概率,(2)平均排队长,(3)平均队长,(4)平均逗留时间,(5)平均等待时间,(6)顾客到达必须等待的概率,=0.0748,=1.70人,=3.95人,=4.39分,=1.89分,=0.57,一、M/M/C/(10),如果顾客的排队方式变为到达售票处后可到任一窗口排队，且入队后不再换队，即形成3 个队列，情况会如何？如下图：,这样，原来系统就变成3个M/M/1的子系统,下面我们来比较下单队和多队不同排队方式的各种指标,一、M/M/C/(11),模型,服务台空闲概率,0.0748,M/M/3,M/M/1,0.25(每个子系统）,顾客必须等待的概率,0.57,0.75,平均排队长Lq,1.70,2.25(每个子系统）,平均队长LS,3.95,9(整个系统),平均逗留时间WS,4.39(分钟),10(分钟),平均等待时间Wq,从表中各指标的对比可知，单队比多队有显著优越性，则我们在实际中安排排队方式时应该注意这问题。,1.89(分钟),7.5(分钟),M/M/C的例21,例3 考虑一个医院急诊室的管理问题。根据统计资料，急诊病人相继到达时间服从负指数分布，平均 每半小时来一个；医生处理病人的时间也服从负指数分布，平均需要20分钟。该急诊室已有一个医生，管理人员现考虑是否增加一个医生,解：,该问题可看作一个M/M/s/排队问题,根据公式 计算结果如下,C=1，2,M/M/C的例22,计算结果,空闲概率,0.333,C=1,C=2,0.5,有1个病人的概率P1,0.222,0.333,有2个病人的概率P2,0.148,0.111,平均病人数L,2,0.75,平均等待病人数Lq,1.333,0.083,病人平均逗留时间W,1,0.375,病人平均等待时间Wq,0.667,0.042,病人需等待的概率,0.667,0.167,病人等待超过0.5小时的概率,0.404,0.022,病人等待超过1小时的概率,0.245,0.003,二、多服务台模型混合制模型M/M/C/N/(1),(1)顾客的相继到达时间服从参数为的负指数分布,M/M/C/N/是指:(系统空间有限制的情形）,(2)服务台数为C个,(4)服务系统空间为N：当系统中有N个顾客时，达 到的顾客不进入系统等待；当系统中少于N个顾 客时，到达的顾客可进入系统等待服务。,(5)顾客源为无限,(6)服务规则为先到先服务。,下面我们讨论在平稳状态下数量指标,(3)每个服务台服务时间相互独立，且服务时间V服 从参数为的负指数分布,二、M/M/C/N/(2),由于系统中最多容纳N个顾客，则有,记 pn=PN=n(n=0,1,2,),为系统达到平稳状态后队长N的概率分布,当0nc,服务率,到达率,当 n=1,2,N-1,当nN,由生灭过程可知,当cnN,二、多服务台模型混合制模型(3),记 pn=PN=n(n=0,1,2,),为系统达到平稳状态后队长N的概率分布,当0nS,其中,当SnK,二、多服务台模型混合制模型(4),则可求出平均排队长Lq,平均队长L,有效到达率,平均逗留时间W,平均等待时间 Wq,平均被占用的服务台数,二、多服务台模型混合制模型(5),例7 某汽车加油站设有两个加油机，汽车按Poisson流到达，平均每分钟到达2辆；汽车加油时间服从负指数分布，平 均加油时间为2分钟。又知加油站最多只能停放3辆等待加 油的汽车，汽车到达时，若已满员，则必须开到别的加油 站去，试对该系统进行分析。,解：,可将系统看作一个M/M/2/5的排队系统,S=2,K=5,二、多服务台混合制排队模型(6),即变为多服务台损失制系统,在M/M/S/K中的s=K时,对损失制系统，有,顾客的损失率,该公式称为Erlang损失公式,此时，平均被占用的服务台数为,n=1,2,s,其中,平均队长L,平均逗留时间W,第五节 一般服务时间M/G/1模型,前面讨论了泊松输入、负指数的服务时间的模型,并且有如下关系：,E系统中顾客数E队列中顾客数E服务中顾客数,符号表示：,V表示服务时间,只不过在有限源和队长有限制情况下，到达率应换成有效到达率。,E逗留时间E等待时间E服务时间,另有关系：,上述关系对服务时间是其它情形的也是成立的,下面讨论下其它分布的情形：,一、PK公式,1、M/G/1排队模型,(1)顾客的相继到达时间服从参数为的负指数分布,(2)服务台数为1个,(3)服务时间V服从一般分布,V的期望值EV和方差DV2都存在,可证明:当=ET1时,M/G/1排队系统可以达到平稳状态.,称为PollaczekKhintchine公式,从此公式可知，只要知道、V的期望EV、方差 DV，不管T的分布如何，都可求出各指标。,一、PK公式（2）,称为PollaczekKhintchine公式,从中也可看，各指标都与期望值、方差有关，而且方差越小，各指标值也越小，因此在改变系统的效率时，可以从改变系统的方差角度考虑。,一、PK公式（3）,例1有一售票窗口，已知顾客按平均为2分30秒的时间间隔的负指数分布到达。顾客在售票窗口前服务时间平均为2分钟。（1）若服务时间出服从负指数分布，求顾客为购票所需要的平均逗留时间和等待时间；（2）若经调查，顾客要售票窗口前至少要占用1分钟，且认为服务时间服从负指数分布是不恰当的，而应服从以下概率密度分布，再求顾客的逗留时间和等待时间。,第六节 排队系统的优化,在一个排队服务系统中，往往存在这样的问题：,提高服务水平（数量、质量）自然就降低顾客的等待费用，但增加了服务机构的成本。我们的目标希望这二者费用之和为最小。,第六节 排队系统的优化(2),一、M/M/1模型中的最优服务率,设CS为当=1时单位时间内的服务费用,则目标函数Z,单位时间服务成本与顾客在系统中逗留费用之和,因为,得,设CW为每个顾客在系统中逗留单位时间的费用,所