运筹学-第十章-排队论定稿素材PPT课件

.,1,排队论,.,2,排队论,引言生灭过程和Poisson过程M/M/s等待制排队模型,.,3,第一节引言,一、排队系统的特征及排队论,排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,.,4,排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。,除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。,排队的不一定是人，也可以是物：,.,5,例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。,.,6,排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。,实际的排队系统可以千差万别，但都可以一般地描述如下：,顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1-1至1-4,.,7,图1-1单服务台排队系统,图1-2单队列S个服务台并联的排队系统,.,8,图1-3S个队列S个服务台的并联排队系统,图1-4单队多个服务台的串联排队系统,.,9,类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等,.,10,尽管各种排队系统的具体形式不同，但都可以由图1-5加以描述,图1-5随机服务系统,通常称上图表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。,.,11,所谓随机性,是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。,一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统,.,12,小结,排队系统又称随机服务系统有请求服务的人或物；有为顾客服务的人或物；顾客到达时间与接受服务时间是随机的。结构：顾客到达-排队-服务机构服务-顾客离去,.,13,二、排队系统的描述,实际中的排队系统各有不同，但概括起来都由三个基本部分组成：,1输入过程2排队及排队规则3服务机制,.,14,1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。,(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而车间内停机待修得机器显然是有限的。,.,15,(2)顾客到达方式这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,.,16,(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,.,17,2排队及排队规则,(1)排队排队分为有限排队和无限排队两类。有限排队是指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被被占满时，后面再来的顾客将不能进入系统；无限排队是指系统中顾客数可以是无限的，队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务，这类系统又称为等待制排队系统。,.,18,有限排队系统,损失制排队系统,混合制排队系统,（排队空间为0的系统）,（允许排队，但又不允许队列无限长）,.,19,这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。,损失制排队系统,（排队空间为0的系统）,.,20,等待制排队系统当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票，故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有：,先到先服务（FCFS）后到先服务（LCFS）优先权（PR）随机服务（RAND）,仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。,.,21,混合制排队系统这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：,队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。如旅馆的床位是有限的。,等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,（允许排队，但又不允许队列无限长）,.,22,逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。,不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，K为系统中可容纳的顾客数,则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。,.,23,3服务机制,排队系统的服务机制可以从以下3方面来描述：,服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：,单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式以及多队多服务台并串联混合式等等。,.,24,(2)服务方式。,这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。医生看病是单个服务,(3)服务时间的分布,一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、等等。,.,25,三、排队系统的分类符号表示,肯道尔（D.G.Kendall）分类（1953）：X/Y/Z/A/B/C其中：X顾客到达的分布；Y服务时间的分布；Z服务台数；A系统容量；B顾客源的个体数。C服务规则表示分布的符号：M-负指数分布或泊松分布；D-定长分布；Ek-k阶爱尔朗分布；GI-一般独立随机分布；G-一般随机分布,.,26,例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。,某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统,.,27,四、排队系统的主要数量指标评价排队系统的优劣。,下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布、忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,.,28,1、队长与排队长(1)队长:系统中的顾客数（n）；N(t)-N-L(2)排队长:系统中排队等待服务的顾客数;Nq(t)-Nq-Lq,.,29,2、逗留时间与等待时间(1)逗留时间:指一个顾客在系统中的全部停留时间；T(t)-T-W(2)等待时间:指一个顾客在系统中的排队等待时间；Tq(t)-Tq-Wq,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。,.,30,3、忙期和闲期(1)忙期:是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。(2)闲期:与忙期相对的是闲期，即服务机构连续保持空闲的时间。,在排队系统中，忙期和闲期总是交替出现的。,.,31,4、其他相关指标(1)忙期服务量：指一个忙期内系统平均完成服务的顾客数；(2)损失率:指顾客到达排队系统，未接受服务而离去的概率;（对损失制或系统容量有限而言）(3)服务强度：=/s；,.,32,根据前面的约定，我们将主要分析系统的平稳分布。于是记：,Pn：当系统达到统计平衡时处于状态n的概率（pn(t)）,n:当系统处于状态n时，新来顾客的平均到达率(单位时间内来到系统的平均顾客数),n：当系统处于状态n时，整个系统的平均服务率（单位时间内可以服务完的顾客数）,.,33,当n为常数时，记为；当每个服务台的平均服务率为常数时，记每个服务台的服务率为。,s表示系统中并行的服务台数,则当ns时，有ns,于是令=/s，称为服务强度（trafficintensity）,.,34,随机变量：数随着实验的结果的不同而变化离散型：的所有可能只有限或至多可列个连续型：（）取值于某个区间（a，b）分布函数(连续):,五、概率论知识复习,.,35,条件概率:,.,36,式中为常数(0)，称X服从参数为的泊松分布，若在上式中引入时间参数t，即令t代替，则有：,1.泊松分布在概率论中，我们曾学过泊松分布，设随机变量为X，则有：,n=0,1,2,（1）,与时间有关的随机变量的概率，是一个随机过程，即泊松过程。,t0，n=0,1,2,（2）,.,37,P(X(0)=0)=1。不相交区间上增量相互独立，即对一切0t1s)的概率分布为泊松分布。若X还满足X(t)-X(s)的分布仅依赖于t-s，则称X为齐次泊松过程;,泊松过程需要满足的条件是：,.,38,（t2t1，n0）,若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即：,当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成普阿松流)。,.,39,平稳性：即对于足够小的t，有：,普阿松流具有如下特性：,在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。,.,40,普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.,由此知，在(t，t+t)区间内没有顾客到达的概率为：,令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t),0是常数，它表示单位时间到达的顾客数，称为概率强度。,即,P0+P1+P2=1,.,41,泊松过程的数字特征,（n个顾客到达的概率）,.,42,2、负指数分布,密度函数,数学期望,方差,随机变量T,分布函数,.,43,fT(t)是一个严格下降函数,.,44,3.爱尔朗(Erlang)分布设v1,v2，,vk是k个独立的随机变量，服从相同参数k的负指数分布，那么：,其概率密度函数是,则称T服从k阶爱尔朗分布。其数字特征为：,串列k个服务台，每台服务时间相互独立，服从相同负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间服从上述k阶Erlang分布。,.,45,例:有易碎物品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件的概率:,.,46,破碎物品少于3件的概率为91.97破碎物品多于3件的概率为:,3.至少有一件破碎的概率为Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.632,.,47,2001年全国数学竞赛的B题“公交车调度”,某条公交线路上行方向共14站，下行方向共,13站.公交公司配给该线路同一型号的大客车，每,辆标准载客100人，据统计客车在该线路上运行的,平均速度为20公里/小时.运营调度要求，乘客候车,时间一般不要超过10分钟，早高峰一般不要超过,例子,.,48,5分钟，车辆满载率不应超过120%，一般也不要,低于50%.,试根据这些材料和要求，为该线路设计一个,便于操作的全天（工作日）的公交车调度方案,包括两个起点站的发车时刻表；一共需要多少,辆车；这个方案以怎样的程度照顾到了乘客和,公交公司双方的利益；等等.,.,49,1.问题分析,将公交车的运行看作是提供服务，即服务机构；,将乘客看作顾客，乘客乘坐公交车看作是接受公交,的服务.公交车运行中乘客的数目描述了系统的状,态，随着时间的变化，一些乘客得到服务后离去，,又有一些新的顾客到来，在人数较多时就要排队等,.,50,服务系统，这里拟用排队论来解决该问题.按排队,论的要求，将公交车看作服务机构，乘客看作顾客.,候，而且，顾客到来的时间具有随机性，对顾客的,服务时间也有随机性，所以公交车运行系统是一个,随时间变化的随机动态系统，可以看作一个随机,.,51,2.基本假设,(i).某站旅客到达为泊松过程,(ii).公交车对每批乘客服务时间为相互独立的负,指数分布，每批服务时间是指公交车从起始站出,乘客到达时间间隔服从参数为的k阶爱尔朗分布：,发再返回起始站所需的时间为.,.,52,服从参数为的负指数分布.,其中表示运行一个程序的平均时间.,.,53,3.模型的建立与求解,k阶爱尔朗分布的概率密度为：,到达间隔的期望值,.,54,公交车服务系统的服务强度为：,以平均等待队长衡量乘客的满意度，系统,以乘客的等待时间在非高峰期不超过10分,服务台的平均占有数衡量公交车公司的利益作,为规划模型的目标；,钟，高峰期不超过5分钟，以及车容量在区间,(50,120)作为约束条件，建立随机规划模型:,.,55,约束条件为：,对上述模型求解即可得到公交车调度的一个,完整方案.至此，利用排队论来建立调度问题的,一个明确、完整的随机规划数学模型，可以利用,.,56,第二节生灭过程和Poisson过程,一、生灭过程简介,一类非常重要其广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。,.,57,定义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为一个生灭过程。,.,58,顾客到达“生”；顾客离开“灭”,顾客到达,顾客离去,生灭过程示意图：,.,59,一般说来，得到是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为,n=0,1,2，.,.,60,各种方式发生概率表,.,61,方式1，2，3，4互不相容且完备，于是：,t2项都变为零,对上式求导有：,.,62,当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则:,.,63,我们假设系统是平稳的，即与时刻无关，于是可得：,.,64,继续迭代：,记,则平稳状态的分布为：,如何求P0?,.,65,由概率分布的要求：,有：,于是：,.,66,小结,系统达到平稳状态后的状态分布-Pn,.,67,举例,某小型超市有一个收款台。交款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min/人的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。求收款台前有n名顾客的概率Pn,.,68,解：,n=1,2.,则有,由级数可知：,当|q|0称为过程N(t)的强度，而o(t)为当t-0时关于t的高阶无穷小。,注：,.,71,（2）独立性任意两个不相交区间内顾客到达情况相互独立,（3）普通性在t,t+t内多于一个顾客到达的概率为,亦即对于充分小的t，在t,t+t内出现2个或2个以上质点的概率与出现一个质点的概率相比可以忽略不计。,则称N(t),t0为Poisson过程（强度为）。,.,72,定理1设N(t)为时间0,t内到达系统的顾客数，则N(t),t0为Poisson过程的充分必要条件是：,n=1,2,定理1说明，如果顾客的到达为Poisson流的话，则到达顾客数的分布恰为Poisson分布。,.,73,举例,顾客按泊松流到达餐厅，平均每小时20人，在上午11：07餐厅内有18人试求：到11：12餐厅内有20名顾客的概率,分析：依题意知20（人/小时）,由公式,可知：,在（1/12）h内到达顾客2人的概率为：,.,74,但无论是从Poisson过程的定义，还是根据其概率分布去对顾客的到达情况进行分析，都有许多不便之处。,实际问题中比较容易得到和进行分析的往往是顾客相继到达系统的时刻，或相继到达的时间间隔。,.,75,定理2设N(t)为时间0,t内到达系统的顾客数，则N(t),t0为参数为的Poisson过程的充分必要条件是：相续到达时间间隔服从相互独立的参数为的负指数分布。,定理2说明，顾客相续到达时间间隔服从相互独立的参数为的负指数分布，与到达过程为参数的Poisson过程是等价的。,.,76,举例,某排队系统，顾客到达为泊松流，平均1人/h。假如有一名顾客于中午12点到达该排队系统情况下。试求：下一名分别于下午1点前、12点间、2点后到达的概率。,.,77,分析：因顾客到达为泊松流，则说明顾客到达时间间隔T服从负指数分布，故T的概率密度fT(t)为：,（1）因下一名顾客在下午1:00前到达，有0T1,则,（2）下一名顾客在下午1:002:00之间达到，即1T2,则,.,78,第三节M/M/s等待制排队模型,一、单服务台模型,M/M/1/是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。,.,79,1、队长的分布,由n=(n=0，1，2，)n=(n=0，1，2，)记=/并设4)；(7)在六天工作日内系统中没有顾客的小时数；(8)若决定当顾客平均逗留时间超过半个小时时，就应增加一个售票窗口，试问这相当于要求顾客的平均到达率是原有的几倍？,举例,.,94,解：按题意可知,=24人/小时，=40人/小时，=/=0.6,（1）,（2）,（3）,（4）,（5）,.,95,（6）,（7）因每天系统内没有顾客的小时数为8p0=3.2小时,故一周六天工作日内没有顾客的小时数为6*3.2=19.2小时.,（8）当,1=38,于是,.,96,3、忙期和闲期,在平衡状态下，忙期B和闲期I一般均为随机变量，求它们的分布比较麻烦。因此我们一般考虑平均忙期和平均闲期,.,97,由于忙期和闲期出现的概率分布为和1,所以在一段时间内可以认为忙期和闲期的总长度之比为,又因为忙期和闲期是交替出现的，所以在充分长的时间里，它们出现的平均次数应是相同的。于是，忙期的平均长度和闲期的平均长度之比也