运筹学第十章 排队论ppt课件.ppt

《运筹学第十章 排队论ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第十章 排队论ppt课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、排队论,排队论,引言生灭过程和Poisson过程M/M/s等待制排队模型,第一节 引言,一、排队系统的特征及排队论,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。,除了上述有形的排队之外，还有大量的所谓“无形”排队现

2、象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。,排队的不一定是人，也可以是物：,例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。,排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。,实际的排队系统可以千差万别，但都可以一般地描述如下：,顾客为了

3、得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图10-1至10-4,图10-1 单服务台排队系统,图10-2 单队列S个服务台并联的排队系统,图10-3 S个队列S个服务台的并联排队系统,图10-4 单队多个服务台的串联排队系统,类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等,尽管各种排队系统的具体形式不同，但都可以由图10-5加以描述,图10-5 随机服务系统,通常称上图表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。,所谓随机性则是排队系统的

4、一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。,一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统,小结,排队系统又称随机服务系统 有请求服务的人或物； 有为顾客服务的人或物； 顾客到达时间与接受服务时间是随机的。结构： 顾客到达 - 排队 - 服务机构服务 - 顾客离去,二、排队系统的描述,实际中的排队系统各有不同，但概括起来都由三个基本部分组成：,1 输入过程；2 排队及排队规则3 服务机制,1输入过程这是指要求服务的顾客是按怎样的规律到达排队

5、系统的过程，有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。,(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而车间内停机待修得机器显然是有限的。,(2)顾客到达方式这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(

6、K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,2排队及排队规则,排队排队分为有限排队和无限排队两类。有限排队是指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被被占满时，后面再来的顾客将不能进入系统；无限排队是指系统中顾客数可以是无限的，队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务，这类系统又称为等待制排队系统。,有限排队系统,损失制排队系统,混合制排队系统,（排队空间为0的系统）,（允许排队，但又不允许队列无限长）,这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永

7、不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。,损失制排队系统,（排队空间为0的系统）,混合制排队系统这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：, 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 如旅馆的床位是有限的。, 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T 时，顾客将自动离去，并不再回来。如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,（

8、允许排队，但又不允许队列无限长）, 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t 时，若在这个时间内未被击落，也就不可能再被击落了。,不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。(K为系统中可容纳的顾客数),(2)排队规则当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票，故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有：,先到先服务（FCFS）后到先服务（LCFS）优先权（PS）随机服务,

9、仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。,3服务机制,排队系统的服务机制可以从以下3方面来描述：,服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：,单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式 以及多队多服务台并串联混合式等等。,(2) 服务方式。,这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。,(3) 服务时间

10、的分布,一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。,三、排队系统的符号表示,肯道尔（D.G.Kendall）分类：X / Y / Z / A / B /C 其中： X 顾客到达的分布； Y 服务时间的分布； Z 服务台数； A 系统容量； B 顾客源的个体数。 C 服务规则表示分布的符号：M-负指数分布或泊松输入；D-定长分布；Ek-k阶爱尔朗分布；GI-一般独立随机分布；G-一般随机分布,例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时

11、间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。,某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统,四、排队系统的主要数量指标 评价排队系统的优劣。,下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初

12、始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,1、队长与排队长 (1)队长: 系统中的顾客数（n）； N(t)-N-L (2)排队长: 系统中排队等待服务的顾客数; Nq(t)- Nq-Lq,2、逗留时间与等待时间 (1)逗留时间: 指一个顾客在系统中的全部停留时间； T(t)-T-W (2)等待时间: 指一个顾客在系统中的排队等待时间； Tq(t)- Tq-Wq,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。,2、忙期和闲期 (1)忙期: 是指从顾

13、客到达空闲着的服务机构起，到服务机构再次 成为空闲止的这段时间，即服务机构连续忙的时间。 (2)闲期: 与忙期相对的是闲期，即服务机构连续保持空闲的时间。,在排队系统中，忙期和闲期总是交替出现的。,3、其他相关指标 (1)忙期服务量：指一个忙期内系统平均完成 服务的顾客数； (2)损失率: 指顾客到达排队系统，未接受服务 而离去的概率; （对损失制或系统容量有限而言） (3)服务强度： = /s ；,根据前面的约定，我们将主要分析系统的平稳分布。于是记：,Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)）,n :当系统处于状态n时，新来顾客的平均到达率(单位 时间内来到系统的平均顾客数

14、),n：当系统处于状态n时，整个系统的平均服务率。 （单位时间内可以服务完的顾客数）,当n为常数时，记为；当每个服务台的平均服务率为常数时，记每个服务台的服务率为。,S表示系统中并行的服务台数,则当ns时，有ns ,于是令 = /s ， 称为服务强度 （traffic intensity）,负指数分布,密度函数,均值,方差,随机变量 T,分布函数,fT(t) 是一个严格下降函数,第二节 生灭过程和Poisson过程,一、生灭过程简介,一类非常重要其广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。,定义1 设N(t)，t0 为一个随机过

15、程。如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 为一个生灭过程。,顾客到达“生”；顾客离开“灭”,顾客到达,顾客离去,生灭过程示意图：,一般说来，得到 是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2,各种方式发生概率表,方式1，2，3，4互不相容且完备，于是：,t2项都变为

16、零,对上式求导有：,当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则:,我们假设系统是稳态的，即与时刻无关，于是可得：,继续迭代：,记,则平稳状态的分布为：,如何求P0?,由概率分布的要求：,有：,于是：,小结,系统达到平稳状态后的状态分布-Pn,举例,某小型超市有一个收款台。交款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。求 收款台前有n 名顾客的概率Pn,解：,n=1,2.,则有,由级数可知：,当|q

17、| 1时， 其和为,由,可知：,二、Poission过程和负指数分布,Poission过程（又称为Poisson流，最简流）是排队论中经常用来描述顾客到达的特殊随机过程。实际上它是一个纯生过程，与概率论中的Poisson分布和负指数分布有密切的联系。,下面结合排对论的术语，给出Poisson过程的定义：,定义2 设N(t)为时间 0, t 内到达系统的顾客数，如果满足下面三个条件：,（1）平稳性：在t, t + t内有一个顾客到达的概率为,即其中常数0称为过程N(t)的强度，而o(t)为当t-0时关于t 的高阶无穷小。,注：,（2） 独立性任意两个不相交区间内顾客到达情况相互独立,（3） 普通

18、性在 t, t+t 内多于一个顾客到达的概率为,亦即对于充分小的t，在 t, t+t 内出现2个或2个以上质点的概率与出现一个质点的概率相比可以忽略不计。,则称 N(t), t 0 为Poisson过程（强度为 ）。,定理1 设N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为Poisson过程的充分必要条件是：,n=1,2,定理1说明，如果顾客的到达为Poisson流的话，则到达顾客数的分布恰为Poisson分布。,举例,顾客按泊松流到达餐厅，平均每小时20人，在上午11：07餐厅内有18人试求：到11：12餐厅内有20名顾客的概率,分析：依题意知 20 （人/小时）,

19、由公式,可知：,在（1/12）h内到达顾客2人的概率为：,但无论是从Poisson过程的定义，还是根据其概率分布去对顾客的到达情况进行分析，都有许多不便之处。,实际问题中比较容易得到和进行分析的往往是顾客相继到达系统的时刻，或相继到达的时间间隔。,定理2设N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为参数为的Poisson过程的充分必要条件是：相续到达时间间隔服从相互独立的参数为的负指数分布。,定理2说明，顾客相续到达时间间隔服从相互独立的参数为的负指数分布，与到达过程为参数的Poisson过程是等价的。,举例,某排队系统，顾客到达为泊松流，平均1人/h。假如有一名顾

20、客于中午12点到达该排队系统情况下。试求：下一名分别于下午1点前、12点间、2点后到达的概率。,分析：因顾客到达为泊松流，则说明顾客到达时间间隔T服从负指数分布，故T的概率密度fT(t)为：,（1）因下一名顾客在下午1:00前到达，有 0 T 1,则,（2）下一名顾客在下午1:002:00之间达到，即 1 T 2,（1）因下一名顾客在下午2:00以后到达，即 T 2,则,第三节 M/M/s等待制排队模型,一、单服务台模型,M/M/1/ 是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。,1、队长的分布,由n =( n=0，

21、1，2，) n =( n=0，1，2，)记 = / 并设 1 (否则队列将排至无限远)， 则,n= 1,2,.,n= 1,2,.,而,因此,n=0,1,2,10.9,10.10,公式10.10给出了在平衡条件下系统中顾客数为n的概率。,公式10.9不难看出， 是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称为服务强度，它反映了系统繁忙的程度。,2、几个主要数量指标,对单服务台等待排队系统，由已得到的平稳状态下队长的分布，可以得到平均队长L为：,平均排队长Lq为：,利用Little公式可求得：,平均逗留时间W为：,平均等待时间Wq为：,关于顾客在系统中的逗留时间T,可说明它

22、服从 的负指数分布 ,即有,小结, = / ,n=0,1,2,举例,某修理店只有一个修理工，来修理的顾客到达过程为Poisson流，平均4人/h; 修理时间服从负指数分布，平均需要6min。试求：（1）修理店空闲的概率（2）店内恰有3个顾客的概率（3）店内至少有1个顾客的概率（4）在店内的平均顾客数（5）每位顾客在店内的平均逗留时间（6）等待服务的平均顾客数（7）每位顾客平均等待服务时间（8）顾客在店内等待时间超过10min的概率,解 本例可看成一个M/M/1/排队问题，其中,（1）修理店空闲的概率,（2）店内恰有3个顾客的概率,（3）店内至少有1个顾客的概率,（4）在店内的平均顾客数,（5）

23、每位顾客在店内的平均逗留时间,（人）,（6）等待服务的平均顾客数,（人）,（7）每位顾客平均等待服务的时间,（8）顾客在店内逗留时间超过10min的概率,由于逗留时间服从参数 的负指数分布，即分布函数为,则,注：对于： 1小时 10 人 则 1分钟 10/60=1/6(人)。同理,某车间的工具仓库只有一个管理员，平均有4人/h来领工具，到达过程为Poisson流；领工具的时间服从负指数分布，平均为6min。试求,（1）仓库内没有人领工具的概率（2）仓库内领工具的工人的平均数（3）排队等待领工具的工人的平均数（4）工人在系统中的平均花费时间（5）工人平均排队时间,解：本题属于M/M/1系统,（1

24、）仓库内没有人领工具的概率,（2）仓库内领工具的工人的平均数,（3）排队等待领工具的工人的平均数,（4）工人在系统中的平均花费时间,（5）工人平均排队时间,某音乐厅设有一个售票处，营业时间为8时到16时，假定顾客流和服务时间均为负指数分布，且顾客到来的平均间隔时间为2.5分钟，窗口为每位顾客服务平均需要1.5分钟，,试求：(1)顾客不需要等待的概率；(2)平均队长L；(3)顾客在系统内平均逗留时间W； (4)平均排队等待人数Lq；(5)平均排队等待时间Wq；(6)系统内顾客人数超过4个的概率p(L 4)；(7)在六天工作日内系统中没有顾客的小时数； (8)若决定当顾客平均逗留时间超过半个小时时

25、，就应增加一个售票窗口，试问这相当于要求顾客的平均到达率是原有的几倍？,举例,解：按题意可知,=24人/小时， =40人/小时， = / =0.6,（1）,（2）,（3）,（4）,（5）,（6）,（7）因每天系统内没有顾客的小时数为8p0=3.2小时,故一周六天工作日内没有顾客的小时数为6*3.2=19.2小时.,（8）当,1=38,于是,3、忙期和闲期,在平衡状态下，忙期B和闲期I一般均为随机变量，求它们的分布比较麻烦。因此我们一般考虑平均忙期 和平均闲期,由于忙期和闲期出现的概率分布为和1 ,所以在一段时间内可以认为忙期和闲期的总长度之比为,又因为忙期和闲期是交替出现的，所以在充分长的时间

26、里，它们出现的平均次数应是相同的。于是，忙期的平均长度 和闲期的平均长度 之比也应是,又因为在到达为Poisson流时，根据负指数分布的无记忆性和到达与服务相互独立的假设，容易证明从系统空闲时刻起到下一个顾客到达时刻止（即闲期）的时间间隔仍服从参数为的负指数分布，且与到达时间间隔相互独立。,因此，平均闲期应为,将上面两式比较，发现平均逗留时间（W）=平均忙期（ ）,这一结果看上去是显然的，顾客在系统中逗留的时间越长，服务员连续忙的时间也就越长。因此，一个顾客在系统内的平均逗留时间应等于服务员平均连续忙的时间,二、多服务台模型,M/M/s/ 是指：设顾客单个到达，相继到达时间服从参数为的负指数分

27、布，服务台数为s，每个服务台的服务时间相互独立，且服从参数为的负指数分布，系统空间无限，允许无限排队。,当考虑系统处于平稳状态后队长N的概率分布,有,n=1,2,s,ns,1、队长的分布,故,其中,上面两个式子给出了平衡条件下系统中顾客数为n的概率，当ns时，即系统中顾客数大于服务台个数，这时再来的顾客必须等待，因此记：,Erlang等待公式,它给出了顾客到达系统时需要等待的概率,由平稳状态下队长N的概率分布，可得到平均排队长Lq:,2、几个主要数量指标,由平均排队长Lq，可得到平均排队长L为：,L=平均排队长 + 正在接受服务的顾客的平均数,正在接受服务的顾客的平均数？,记系统中正在接受服务的顾客的平均数为,显然 也是正在忙的服务台的平均数，故：,上式说明，平均在忙的服务台个数不依赖于服务台个数s,在求得“正在接受服务的顾客的平均数” 后,我们可求得平均对长L,L=平均排队长 + 正在接受服务的顾客的平均数,对于多服务台系统，Little公式依然成立，即有,