运筹学第三版排队论课件.ppt

1,排队论,排队论(queuingtheory)研究内容包括三个部分：(1)排队系统的性态问题(2)排队系统的最优化问题(3)排队系统的统计推断问题,解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理，研究设计改进措施等。,统计推断，即判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。,最优化，又分静态最优和动态最优，前者指最优设计，后者指现有排队系统的最优运营。,性态问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等。,2,排队论,第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M/G/1模型第6节经济分析系统的最优化第7节分析排队系统的随机模拟法,3,第1节基本概念,1.1排队过程的一般表示1.2排队系统的组织和特征1.3排队模型的分类1.4排队问题的求解,4,不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。,1.1排队过程的一般表示,5,1.1排队过程的一般表示,各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。,排队过程的一般模型,6,1.1排队过程的一般表示,形形色色的排队系统,7,实际的排队系统虽然千差万别，但是它们有以下的共同特征：(1)有请求服务的人或物顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。,1.2排队系统的组成和特征,8,1.2排队系统的组成和特征,排队系统由三个基本部分组成：输入过程排队规则服务机构,9,1.2排队系统的组成和特征,输入过程输入即指顾客到达排队系统。输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从以下几个方面来描述个输入过程(1)顾客的总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的；上游河水流入水库可以认为顾客总体是无限的例如，某个工厂因故障待修的机床则是有限的。,10,1.2排队系统的组成和特征,输入过程(2)顾客到来的方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,11,1.2排队系统的组成和特征,输入过程(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。例如：在流水线上装配的各部件必须按确定的时间间隔到达装配点，定点运行的列车、班机的到达也都是确定的；例如：物流配送等待的顾客、办理出关手续的顾客、通过路口的车辆的到达都是随机的。,12,1.2排队系统的组成和特征,输入过程对于随机的情形，必须了解单位时间的顾客到达数或相继到达的时间间隔的概率分布。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,13,1.2排队系统的组成和特征,输入过程(4)顾客的到达可以是相互独立的。(5)输入过程可以是平稳的，或称对时间是齐次的，即描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的。,14,1.2排队系统的组成和特征,排队规则这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。例如：电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。,15,1.2排队系统的组成和特征,排队规则(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如：排队等待售票，故障设备等待维修等。对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务(FCFS)后到先服务(LCFS)随机服务(RS)有优先权的服务,16,1.2排队系统的组成和特征,排队规则(2)等待制（续）。先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。后到先服务。例如：仓库中迭放的钢材，后迭放上去的都先被领走。随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务。例如：电话交换台接通呼叫电话。优先权服务。例如：老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等。,17,1.2排队系统的组成和特征,排队规则(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。等待时间有限。逗留时间有限。,18,1.2排队系统的组成和特征,排队规则(3)混合制队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。具体地，最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。例如：水库的库容是有限的，旅馆的床位是有限的。,19,1.2排队系统的组成和特征,排队规则(3)混合制队长有限。等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。例如：易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。例如：顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,20,1.2排队系统的组成和特征,排队规则(3)混合制队长有限。等待时间有限。逗留时间(等待时间与服务时间之和)有限。例如：用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。,21,1.2排队系统的组成和特征,排队规则（续）从允许排队的空间看队列可以排在具体的处所，也可以是抽象的。排队空间可以有限，也可以无限。从排队的队列数目看，可以是单列，也可以是多列。在多列的情形，各列间的顾客有的可以互相转移，有的不能。有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服务为止。,22,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。从数量上说，服务台有单服务台和多服务台之分。在有多个服务台的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。,23,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图,服务台的各种排列方式,24,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图多队多服务台并联式；如(b)图,服务台的各种排列方式,25,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图多队多服务台并联式；如(b)图单队多服务台串联式；如(d)图,服务台的各种排列方式,26,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图多队多服务台并联式；如(b)图单队多服务台串联式；如(d)图单队多服务台并串联混合式；,服务台的各种排列方式,27,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图多队多服务台并联式；如(b)图单队多服务台串联式；如(d)图单队多服务台并串联混合式；多队多服务台并串联混合式等等。,服务台的各种排列方式,28,1.2排队系统的组成和特征,服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：单队单服务台式；如(a)图单队多服务台并联式；如(c)图多队多服务台并联式；如(b)图单队多服务台串联式；如(d)图单队多服务台并串联混合式；多队多服务台并串联混合式等等。,服务台的各种排列方式,29,1.2排队系统的组成和特征,服务机构(服务台情况)(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。服务时间可分为确定型和随机型。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。服务时间的分布通常假定是平稳的。指时间间隔分布及其特征参数（数学期望、方差等）不随时间的变化而变化。,30,1.3排队模型的分类,排队模型分类方法D.G.Kendall，1953构成排队模型的三个主要特征指标(1)相继顾客到达间隔时间的分布；(2)服务时间的分布；(3)服务台的个数。根据这三个特征对排队模型进行分类的Kendall记号：X/Y/ZX：表示相继到达间隔时间的分布；Y：表示服务时间的分布；Z：并列的服务台的数目。,31,1.3排队模型的分类,表示相继到达间隔时间和服务时间的各种分布符号M负指数分布(M是Markov的字头，因为负指数分布具有无记忆性，即Markov性)D确定型(deterministic)Ekk阶爱尔朗(erlang)分布GI一般相互独立(generalindependent)的时间间隔的分布G一般(general)服务时间的分布,32,1.3排队模型的分类,Kendall符号的扩充X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是：A：系统容量限制N，或称等待空间容量。如系统有N个等待位子，则00为常数，则称t服从参数为的指数分布，其分布函数F(t)为,其均值为,方差为,负指数分布的定义,第2节到达间隔的分布和服务时间的分布,47,如果随机变量T的概率密度是则称T服从负指数分布。它的分布函数是数学期望为方差为标准差为,负指数分布的定义,第2节到达间隔的分布和服务时间的分布,48,2.1.1经验分布,例1大连港大港区1979年载货500吨以上船舶到达(不包括定期到达的船舶)逐日记录见书上表12-2。将表12-2整理成船舶到达数的分布表。可以计算出：平均到达率=到达总数/总天数=1271/365=3.48(艘/天),49,2.1.1经验分布,以i表示第i号顾客到达的时刻，以si表示对它的服务时间，这样可算出相继到达的间隔时间ti(ti=i+1-i)和排队等待时间wi，它们的关系如下：,实际中测定相继到达时间间隔的方法,相继到达时间间隔等待时间,50,2.1.1经验分布,通过一个例题来说明原始资料的整理。例2某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻和服务时间s(单位为分钟)如表12-4。在表中以第1号顾客到达时刻为0，对所有顾客的全部服务时间为127分钟。将原始记录整理成下表。,51,2.1.1经验分布,52,2.1.1经验分布,53,2.1.1经验分布,例2某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻和服务时间s(单位为分钟)如表12-4。在表中以第1号顾客到达时刻为0，对所有顾客的全部服务时间为127分钟。将原始记录整理成下表。,54,2.1.1经验分布,例2平均间隔时间=142/40=3.55(分钟/人)平均到达率=41/142=0.28(人/分钟)平均服务时间=127/41=3.12(分钟/人)平均服务率=41/127=0.32(人/分钟),55,普阿松流，又称为泊松流、Poisson过程、最简单流，是排队论中一种常用来描述顾客到达规律的特殊的随机过程。,2.1.2普阿松流（泊松流）,56,2.1.2普阿松流（泊松流）,设表示在时间区间内到达的顾客数令表示在时间区间内有个顾客到达的概率，即当满足下列三个条件时，我们说顾客的到达形成泊松流。(1)在不相重叠的时间区间内顾客到达数是相互独立的，即无后效性。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的。(2)平稳性。又称作输入过程是平稳的，对充分小的，在时间区间内有1个顾客到达的概率与t无关，而与区间长度成正比，即其中，当时，是关于的高阶无穷小。进一步地，在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。即对任意(0,)，在(,+t或(0,t)内恰好到达k个顾客的概率相等：(3)单个性又称普通性。对于充分小的，在时间区间内有2个或2个以上顾客到达的概率极小，以至于可以忽略，即,57,当顾客到达为泊松流时，研究顾客到达数n的概率分布。由条件(2)，总可以取时间由0算起，并简记由条件(2)和(3)，容易推得在区间内没有顾客到达的概率将区间分成两个互不重叠的区间和。则到达总数n分别出现在这两个区间和上，有下列(A)(B)(C)三种情况：,2.1.2普阿松流（泊松流）,58,2.1.2普阿松流（泊松流）,在内到达n个顾客应是表中(A)(B)(C)三种互不相容的情况之一，所以概率应是表中三个概率之和(各合为一项)令，得下列方程，并注意到初始条件，则有当n=0时，没有(B)，(C)两种情况，所以得,59,解(12-5)式和(12-6)式，得表示长为t的时间区间内到达n个顾客（即N(t)=n）的概率，由(12-7)式得随机变量服从泊松分布。结论：当顾客到达为泊松流时，在长度为t的时间内到达n个顾客的概率Pn(t)服从泊松分布!它的数学期望和方差分别是,2.1.2普阿松流（泊松流）,相等！,特别地，t=1时，EN(1)=，因此表示单位时间平均到达的顾客数,60,我们再来研究两个顾客先后到达的时间间隔T的概率分布。,61,当输入过程是泊松流时，由于在单位时间里到达的顾客数是随机变量，那么对应的，前后两个顾客到达的时间间隔也就是随机变量了，即有的时间间隔长一些，有的时间隔又短一些。设T的分布函数为FT(t)，则这个概率也就是在0，t)区间内至少有一个顾客到达的概率。,2.1.3普阿松流与负指数分布关系,62,泊松过程的顾客到达时间间隔分布顾客到达的时间间隔小于t的概率，即t内有顾客的概率分布。两相邻顾客到达的时间间隔是一连续型随机变量，用T表示。在t时间内没有顾客到达的概率为,2.1.3普阿松流与负指数分布关系,63,在区间内至少有1个顾客到达的概率是即顾客相继到达的间隔时间T必然服从负指数分布。,其概率密度函数：,则T的分布函数为,数学期望为,表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。,2.1.3普阿松流与负指数分布关系,64,顾客相继到达的间隔时间独立且为同负指数分布(密度函数为)，与输入过程为泊松流(参数为)是等价的。对于泊松流，表示单位时间平均到达的顾客数，1/表示相继顾客到达平均间隔时间。,相继到达时间间隔为负指数分布与到达为泊松流的等价性,上述内容还可以用如下表达！,对于泊松流，其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，其分布函数为负指数分布：,2.1.3普阿松流与负指数分布关系,65,当输入过程是泊松流时，那么顾客相继到达的间隔时间T（注意T是随机变量）必然服从负指数分布。,2.1.3普阿松流与负指数分布关系,66,负指数分布的性质由条件概率公式容易证明该性质称为无记忆性或马尔柯夫性。若T表示排队系统中顾客相继到达的间隔时间，该性质说明：一个顾客到来所需的时间与过去一个顾客到来所需时间s无关，也就是说该顾客是随机地到达。,2.1.3普阿松流与负指数分布关系,67,例:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎,其破损率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率.解:=0.002500=11破碎3件物品的概率为:P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613即物品破碎3件的概率为6.132.破碎物品少于3件的概率:,68,破碎物品少于3件的概率为91.97破碎物品多于3件的概率为:,3.至少有一件破碎的概率为Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.632,69,2.1到达间隔的分布2.1.1经验分布（定长输入）2.1.2普阿松流（泊松流）2.1.3普阿松流与负指数分布关系2.2服务时间的分布2.2.1经验分布（定长分布）2.2.2负指数分布2.2.3爱尔朗分布,第2节到达间隔的分布和服务时间的分布,70,每一个顾客的服务时间都是常数，此时服务时间t的分布函数为：,2.2.1服务时间的定长分布,71,服务时间v的分布对顾客的服务时间，也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从负指数分布。设它的分布函数和密度分别是其中,表示对顾客的平均服务时间。表示单位时间能被服务完成的顾客数，称为平均服务率，,2.2.2服务时间的负指数分布,72,是指相继顾客到达时间间隔T相互独立，其分布密度为其中，k为非负整数。,爱尔朗分布,2.2.3服务时间的爱尔朗分布,73,设是k个相互独立的随机变量，服从相同参数的负指数分布，那么的概率密度是称T服从k阶爱尔朗分布，其均值和方差分别为,可以证明如下结论。,2.2.3服务时间的爱尔朗分布,74,爱尔朗分布的意义当k=1时，爱尔朗分布化为负指数分布，可看成是一种完全随机的分布；当k增大时，爱尔朗分布的图形逐渐变为对称的；当k30时爱尔朗分布近似于正态分布；k时，VarT0，这时爱尔朗分布化为确定型分布。一般k阶爱尔朗分布可看成完全随机与完全确定的中间型，能对现实世界提供更为广泛的适应性。,2.2.3服务时间的爱尔朗分布,75,可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：,1/k表示一个顾客的一个服务台的平均服务时间。,2.2.3服务时间的爱尔朗分布,76,例如：某排队系统有并联的k个服务台，顾客流为泊松流，规定第i,K+i,2K+i个顾客排入第i号台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。,例如：串联的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间就服从k阶Erlang分布。,2.2.3服务时间的爱尔朗分布,77,第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M/G/1模型第6节经济分析系统的最优化第7节分析排队系统的随机模拟法,排队论,78,排队论,排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。,79,(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标：,排队论,80,系统中顾客数(队长)的期望值L或Ls；排队等待的顾客数(排队长)的期望值Lq；顾客在系统中全部时间(逗留时间)的期望值W或Ws；顾客排队等待时间的期望值Wq。排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面拟分析几种常见排队系统模型。,排队论,81,3.1标准的M/M/1模型(M/M/1/)3.2系统容量有限的情况(M/M/1/N/)3.3顾客源有限的情形(M/M/1/m),第3节单服务台负指数分布排队系统的分析,本节讨论输入过程服从普阿松分布过程、服务时间服从负指数分布单服务台的排队系统。,82,标准的M/M/1模型(1)输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间内的到达数服从泊松分布，到达过程是平稳的。(2)排队规则单队，且对队长没有限制，先到先服务。(3)服务机构单服务台，各顾客的服务时间相互独立，服从相同的负指数分布。此外，还假定到达间隔时间和服务时间是相互独立的。,3.1标准的M/M/1模型(M/M/1/),即已知条件：顾客进入系统的平均速度；单位时间到达的顾客数。：顾客离开系统的平均速度；单位时间能被服务完成的顾客数。,83,首先要求出：系统在任意时刻t的状态为n(即系统中有n个顾客)的概率，它决定了系统运行的特征。现仍然通过研究区间t，t+t）的变化来求解。在时刻t+t，系统中有n个顾客不外乎有下列四种情况（t，t+t）内到达或离开2个以上没列入）。,3.1标准的M/M/1模型(M/M/1/),84,因已知到达规律服从参数为的泊松过程，服务时间服从参数为的负指数分布，所以在时间区间内分为：(1)有1个顾客到达的概率为没有顾客到达的概率就是(2)当有顾客在接受服务时，1个顾客被服务完了(离去)的概率是，没有离去的概率就是。(3)多于一个顾客的到达或离去的概率是，可以忽略。,3.1标准的M/M/1模型(M/M/1/),85,3.1标准的M/M/1模型(M/M/1/),在时刻，系统中有n个顾客(n0)存在下列四种情况(到达或离去是2个以上的没列入)：表示发生(1个)；表示没有发生。,86,87,这四种情况是互不相容的，所以应是这四项之和，即即令，得关于的微分差分方程,3.1标准的M/M/1模型(M/M/1/),所有的高阶无穷小和并,88,当，则只有上表中(A)(B)情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可。且式(A)中无离去的概率为1，即同理求得,它们的概率分别是情况(A)情况(B)情况(C)情况(D),3.1标准的M/M/1模型(M/M/1/),89,研究稳态的情况。这时与时间t无关，可写成，它的导数为0。由(12-15)式和(12-16)式可得这是关于的差分方程，它表明了各状态间的转移关系：状态0转移到状态1的转移率为，状态1转移到状态0的转移率为。,3.1标准的M/M/1模型(M/M/1/),这种系统状态(n)随时间变化的过程就是生灭过程（BirthandDeathProcess）。方程(12-15)、(12-16)解是瞬态解，无法应用。,90,3.1标准的M/M/1模型(M/M/1/),对状态0必须满足以下平衡方程同样对任何的状态，可得如(12-18)所示的平衡方程。由(12-17)式可得将它代入(12-18)式，令，得到同理依次推得今设(否则队列将排至无限远)，又由概率的性质知即，得到,91,对的实际意义的解释/，是平均到达率与平均服务率之比，即在相同时区内顾客到达的平均数与被服务的平均数之比。若将表示为(1/)/(1/)，它是一个顾客的服务时间与到达间隔时间之比，称为服务强度(trafficintensity)，或话务强度。由(12-19)式可知，=1-P0，它刻画了服务机构的繁忙程度，所以又称为服务机构的利用率。,3.1标准的M/M/1模型(M/M/1/),系统处于空闲状态的概率：,系统处于繁忙状态的概率：,92,3.1标准的M/M/1模型(M/M/1/),根据平稳分布，求排队系统的有关运行指标(1)系统中的平均顾客数（平均队长）或(2)在队列中等待的平均顾客数,期望,93,顾客在系统中的逗留时间W(为一个随机变量)在M/M/1情形下，服从参数为的负指数分布，即分布函数概率密度,于是，得到(3)在系统中顾客逗留时间的期望值(4)在队列中顾客等待时间的期望值,3.1标准的M/M/1模型(M/M/1/),平均逗留时间减去平均服务时间。,94,将以上结果归纳如下：它们的相互关系如下：上式称为Little公式。,3.1标准的M/M/1模型(M/M/1/),95,3.1标准的M/M/1模型(M/M/1/),Ls,Lq,Ws,Wq之间的关系：几何解释：稳态时，一个顾客，进入系统后，每单位时间，平均到达顾客。,逗留时间的期望值Ws,队长Ls由时间段内个组成的,Ls=Ws,同理：Lq=WqWs=Wq+（1/）-Ws与Wq只相差一段平均服务时间1/,96,泊松输入负指数分布服务的排队系统的一般决策过程：根据已知条件绘制状态转移速度图；依据状态转移速度图写出各稳态概率之间的关系；求出P0及Pn；计算各项数量运行指标；用系统运行指标构造目标函数，对系统进行优化。,3.1标准的M/M/1模型(M/M/1/),97,例3某医院手术室根据病人来诊和完成手术时间的记录，任意抽查了100个工作小时，每小时来就诊的病人数n的出现次数如下表所示；又任意抽查了100个完成手术的病历，所用时间v(单位：小时)出现的次数如下表所示。,3.1标准的M/M/1模型(M/M/1/),98,(1)每小时病人平均到达率(人/小时)每次手术平均时间(小时/人)每小时完成手术人数(平均服务率)(人/小时)(2)取，可以通过统计检验的方法，认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。(3)说明服务机构(手术室)有84%的时间是繁忙的，有16%的时间是空闲的。(4)依次代入(12-21)式，算出各指标：在病房中病人数(期望值)(人)排队等待病人数(期望值)(人)病人在病房中逗留时间(期望值)(小时)病人排队等待时间(期望值)(小时),3.1标准的M/M/1模型(M/M/1/),99,例2：某修理店只有一位修理工，来修理的顾客到达过程为Poisson流，平均每小时4人；修理时间服从负指数分布，平均需要6分钟。试求：修理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内等待时间超过10分钟的概率。,3.1标准的M/M/1模型(M/M/1/),100,解：本例可看成一个M/M/1/排队问题，其中=4，=1/0.1=10(人/小时），=/=2/5t=1-F(w)=e-(-)tt=10分钟,=10人/小时=10/60=1/6=4人/小时=4/60=1/15PT10=e-10(1/6-1/15)=e-1=0.3677,3.1标准的M/M/1模型(M/M/1/),104,例1：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗留时间；等待编组的列车平均数。如果列车因站中2股道均被占用而停在站外或前方站时，每列车每小时费用为a元，求每天由于列车在站外等待而造成的损失。,3.1标准的M/M/1模型(M/M/1/),105,解：本例可看成一个M/M/1/排队问题，其中=2，=3，=/=2/32=W1-P0-P1-P2=W1-(l-)-(l-)1-(l-)2=1*3=3=(2/3)3=0.296（小时）故每天列车由于等待而支出的平均费用E=24W0a=24*2*0.296*a=14.2a元,3.1标准的M/M/1模型(M/M/1/),107,如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。当N=1时为即时制的情形；当N时为容量无限制的情形。,3.2系统的容量有限制的情况(M/M/1/N/),108,泊松输入负指数分布服务的排队系统的一般决策过程：根据已知条件绘制状态转移速度图；依据状态转移速度图写出各稳态概率之间的关系；求出P0及Pn；计算各项数量运行指标；用系统运行指标构造目标函数，对系统进行优化。,3.2系统的容量有限制的情况(M/M/1/N/),109,3.2系统的容量有限制的情况(M/M/1/N/),稳态情形下各状态间概率强度的转换关系图状态概率的稳态方程,110,3.2系统的容量有限制的情况(M/M/1/N/),稳态情形下各状态间概率强度的转换关系图状态概率的稳态方程其中(12-23b)也可写成，则有,111,3.2系统的容量有限制的情况(M/M/1/N/),由,N则(/)nP0=1n=0,N即P0=1/(/)n=n=0,(1-/)/(1-(/)N+1,1/(N+1)=,112,M/M/1/N/排队系统的各项指标：(1)队长(期望值)(2)队列长(期望值)(3)顾客逗留时间(期望值)(4)顾客等待时间(期望值)(5)有效到达率,3.2系统的容量有限制的情况(M/M/1/N/),令，得到,113,(1)平均队长Ls：,(1),试证=1时,Ls=N/2,3.2系统的容量有限制的情况(M/M/1/N/),114,M/M/1/N/排队系统的各项指标：(1)队长(期望值)(2)队列长(期望值)(3)顾客逗留时间(期望值)(4)顾客等待时间(期望值)(5)有效到达率,3.2系统的容量有限制的情况(M/M/1/N/),令，得到,115,(5)有效到达率e系统容量有限，当满员（n=N）时，顾客将被拒绝，实际的顾客到达率与不一样，,此种情况的公式与前类似,只有Ls不同,e与不同。求e必须先求得P0或PN才行。,可以证明：,3.2系统的容量有限制的情况(M/M/1/N/),116,M/M/1/N/排队系统各项指标的归纳(当时)：,3.2系统的容量有限制的情况(M/M/1/N/),117,例2某单人理发馆共有六把椅子接待顾客排队，无座时将离去，顾客平均到达率为3人/h，理发时间平均为15分钟，求：(1)求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值;(3)求有效到达率;(4)求一顾客在系统中的逗留时间和排队时间平均值;(5)在可能到来的顾客中，有百分之几不等待就离开？,3.2系统的容量有限制的情况(M/M/1/N/),118,(1)求某一顾客到达就能理发的概率:,(2)求需要等待的顾客数的期望值:,(3)求有效到达率:,(4)求一顾客在系统中的逗留时间和排队时间平均值:,3.2系统的容量有限制的情况(M/M/1/N/),119,(5)在可能到来的顾客中，有百分之几不等待就离开？,顾客为何不等待就离去？,因为系统已经满员,3.2系统的容量有限制的情况(M/M/1/N/),故拒绝的概率为3.71%,120,例4某单人理发馆为等待的顾客准备了6把椅子，当6把椅子都坐满时，再来的顾客将不进店而离开。顾客的平均到达率为3人/小时，理发平均需要15分钟。则系统的容量为N=6+1=7，人/小时，人/小时。(1)某顾客一到达就能理发的概率(2)需要等待的顾客数的期望值(3)有效到达率(人/小时)(4)一顾客在理发馆内逗留的期望时间(小时)(分钟),3.2系统的容量有限制的情况(M/M/1/N/),121,(5)在可能到来的顾客中不等待就离开的概率这也是理发馆的损失率。,以本例为例，比较队长为有限和无限的情形：,3.2系统的容量有限制的情况(M/M/1/N/),122,背景设有m台机器(顾客总体)，机器因故障停机表示“到达”，待修的机器形成队列，修理工人是服务员，本节讨论单服务员的情形。顾客总体虽只有m个，但每个顾客到来并经过服务后，仍回到原来总体，所以仍然可以再到来。如在机器故障问题中，同一台机器出了故障(到来)并经修好(服务完了)仍可再出故障，形成循环。模型符号中的表示对系统的容量没有限制，但实际上它不会超过m，所以可写成(M/M/1/m/m)。,3.3顾客源为有限的情形(M/M/1/m),123,泊松输入负指数分布服务的排队系统的一般决策过程：根据已知条件绘制状态转移速度图；依据状态转移速度图写出各稳态概率之间的关系；求出P0及Pn；计算各项数量运行指标；用系统运行指标构造目标函数，对系统进行优化。,124,设每个顾客的到达率相同，均为(这里的含义是单台机器在单位时间里发生故障的概率或平均次数)；设系统内顾客数为Ls，则系统外的顾客平均数为mLs，所以系统的有效到达率为e=(mLs)(12-26)考虑稳态情况下状态间的转移率由状态0转移到状态1：每台设备由正常状态转移为故障状态的转移率为P0，m台设备由无故障状态转移为有一台设备(不论哪一台)发生故障的转移率为mP0。由状态1转移到状态0：其状态转移率为P1。所以，状态0时有平衡方程为：mP0=P1,3.3顾客源为有限的情形(M/M/1/m),125,各状态间的转移差分方程解得(注意到因而不要求）系统的各项指标为,3.3顾客源为有限的情形(M/M/1/m),126,例5某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求：(1)修理工空闲的概率；(2)五台机器都出故障的概率；(3)出故障的平均台数；(4)等待修理的平均台数；(5)平均停工时间；(6)平均等待修理时间；(7)评价这些结果。,3.3顾客源为有限的情形(M/M/1/m),127,解：(1)(2)五台机器都出现故障的概率(3)出故障的平均台数(台)(4)等待修理的平均台数(台)(5)平均停工时间(分钟)(6)平均等待修理时间(分钟)(7)机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。,3.3顾客源为有限的情形(M/M/1/m),128,第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M/G/1模型第6节经济分析系统的最优化第7节分析排队系统的随机模拟法,排队论,129,本节讨论单队、并列的多服务台（服务台数为c）的情形。4.1标准的M/M/c模型4.2M/M/c型系统和c个M/M/1型系统的比较4.3系统容量有限的情形（M/M/c/N/）4.4顾客源有限的情形（M/M/c/m）,第4节多服务台负指数分布排队系统的分析,130,4.1标准的M/M/c模型,标准的M/M/c模型各种特征的规定与标准的M/M/1模型的规定相同。各服务台工作是相互独立的(不搞协作)，且平均服务率相同。整个服务机构的平均服务率为(当)；为(当)。令，只有当时才不会排成无限的队列称为系统的服务强度或服务机构的平均利用率。,131,4.1标准的M/M/c模型,M/M/c排队系统的状态概率分布状态1转移到状态0：即系统中有一名顾客被服务完了(离去)的转移率为。状态2转移到状态1：两个服务台上被服务的顾客中有一个被服务完成而离去。因为不限哪一个，于是状态的转移率为。状态n转移到n-1：当时，状态转移率为；当时，因为只有c个服务台，最多有c个顾客在被服务，个顾客在等候，因此这时状态转移率应为。,132,4.1标准的M/M/c模型,由图12-13可得这里，且用递推法解上述差分方程，可求得状态概率。,133,4.1标准的M/M/c模型,系统的运行指标为：平均队长平均等待时间和逗留时间可由Little公式求得，顾客必须等待的概率（即所有服务台均被占用）为,134,4.1标准的M/M/c模型,例6某售票处有三个窗口，顾客的到达服从泊松过程，平均到达率每分钟(人)，服务(售票)时间服从负指数分布，平均服务率每分钟人。现设顾客到达后排成一队，依次向空闲的窗口购票如图12-14(a)，这就是一个M/M/c型的系统，其中，符合要求的条件，代入公式得：,135,4.1标准的M/M/c模型,(1)整个售票处空闲概率(2)平均队长(3)平均等待时间和逗留时间(分钟)(分钟)顾客到达后必须等待(即系统中顾客数已有3人即各服务台都没有空闲)的概率,136,例6.某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达=0.9（人），服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：1.顾客排成一队，依次购票；(M/M/3/)2.顾客在每个窗口排一队，不准串队。(M/M/1/三个系统并联)求:（1）售票处空闲的概率。（2）平均等待时间和逗留时间。（3）队长和队列长。,4.2M/M/c型系统和c个M/M/1型系统的比较,137,4.2M/M/c型系统和c个M/M/1型系统的比较,现就例6说明，如果原题除排队方式外其他条件不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，见图12-14(b)而每个队列平均到达率为(每分钟)这样，原来的系统就变成3个M/M/1型的子系统。=0.4,=/=0.75,P0=1-=0.25,138,4.2M/M/c型系统和c个M/M/1型系统的比较,现就例6说明，如果原题除排队方式外其他条件不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，见图12-14(b)而每个队列平均到达率为(每分钟)这样，原来的系统就变成3个M/M/1型的子系统。现按M/M/1型解决这个问题，并与上面结果比较如下：,从表中各指标的对比可以看出：单队比三队有显著优越性。,作业！,139,4.3系统的容量有限制的情形（M/M/c/N/）,设系统的容量最大限制为，当系统中顾客数n已达到N(即队列中顾客数已达N-c)时，再来的顾客即被拒绝，其他条件与标准的M/M/c型相同。这时系统的状态概率和运行指标如下：其中，但现在已不必对加以限制。,140,4.3系统的容量有限制的情形（M/M/c/N/）,特别当(即时制)时当即关于的公式被称为爱尔朗损失公式。,例如，停车场就不允许排队等待空位的情形！,141,4.3系统的容量有限制的情形（M/M/c/N/）,这时的运行指标如下：,142,4.3系统的容量有限制的情形（M/M/c/N/）,例7在某风景区准备建造旅馆，顾客到达为泊松流，每天平均到(=)6人，顾客平均逗留时间()为2天，试就该旅馆在具有(c)1，2，3，8个房间的条件下，分别计算每天客房平均占用数及满员概率。这是即时式，因为在客房满员条件下，旅客显然不能排队等待。计算过程通过表12-12进行()。,143,(2),(3)n!,(7),(5),4.3系统的容量有限制的情形（M/M/c/N/）,6.93,0.58,0.42,2.52105,1.07104,4.03104,4.30108,8,6.14,0.51,0.49,1.45104,7.11103,5.04103,3.58107,7,5.33,0.44,0.56,7.46103,4.15103,720,2.99106,6,4.48,0.37,0.63,3.31103,2.07103,120,2.49105,5,3.62,0.30,0.70,1.24103,864,24,2.07104,4,2.74,0.23,0.77,373,288,6,1.73103,3,1.83,0.15,0.85,85,72,2,1.44102,2,0.92,0.08,0.92,13,12,1,1.210,1,1,1,1,1,1,0,(8)Ls(答),(4),(1)n,第(4)栏(2)/(3),