运筹学-第十章-排队论

排队论排队论引言生灭过程和Poisson过程M/M/s等待制排队模型第一节引言一、排队系统的特征及排队论排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。实际的排队系统可以千差万别，但都可以一般地描述如下：顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图10-1至10-4图10-1单服务台排队系统图10-2单队列——S个服务台并联的排队系统图10-3S个队列——S个服务台的并联排队系统图10-4单队——多个服务台的串联排队系统类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等尽管各种排队系统的具体形式不同，但都可以由图10-5加以描述图10-5随机服务系统通常称上图表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统小结排队系统又称随机服务系统①有请求服务的人或物；②有为顾客服务的人或物；③顾客到达时间与接受服务时间是随机的。结构：顾客到达-----排队------服务机构服务------顾客离去二、排队系统的描述实际中的排队系统各有不同，但概括起来都由三个基本部分组成：1输入过程；2排队及排队规则3服务机制1．输入过程．这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述一个输入过程。(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而车间内停机待修得机器显然是有限的。(2)顾客到达方式这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。2．排队及排队规则(1)排队排队分为有限排队和无限排队两类。有限排队是指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被被占满时，后面再来的顾客将不能进入系统；无限排队是指系统中顾客数可以是无限的，队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务，这类系统又称为等待制排队系统。有限排队系统损失制排队系统混合制排队系统（排队空间为0的系统）（允许排队，但又不允许队列无限长）这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。损失制排队系统（排队空间为0的系统）混合制排队系统这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。如旅馆的床位是有限的。②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。（允许排队，但又不允许队列无限长）③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。(K为系统中可容纳的顾客数)(2)排队规则当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票，故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有：•先到先服务（FCFS）•后到先服务（LCFS）•优先权（PS）•随机服务仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。3．服务机制排队系统的服务机制可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：①单队——单服务台式；②单队——多服务台并联式；③多队——多服务台并联式；④单队——多服务台串联式；⑤单队——多服务台并串联混合式以及多队——多服务台并串联混合式等等。(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。三、排队系统的符号表示肯道尔（D.G.Kendall）分类：X/Y/Z/A/B/C其中：X顾客到达的分布；Y服务时间的分布；Z服务台数；A系统容量；B顾客源的个体数。C服务规则表示分布的符号：M---负指数分布或泊松输入；D----定长分布；Ek----k阶爱尔朗分布；GI----一般独立随机分布；G----一般随机分布例如：某排队问题为M／M／S／∞／∞／FCFS／，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统四、排队系统的主要数量指标——评价排队系统的优劣。下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。1、队长与排队长(1)队长:系统中的顾客数（n）；N(t)----N----L(2)排队长:系统中排队等待服务的顾客数;Nq(t)----Nq----Lq2、逗留时间与等待时间(1)逗留时间:——指一个顾客在系统中的全部停留时间；T(t)----T----W(2)等待时间:——指一个顾客在系统中的排队等待时间；Tq(t)----Tq-----Wq这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。2、忙期和闲期(1)忙期:是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。(2)闲期:与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。BBII3、其他相关指标(1)忙期服务量：指一个忙期内系统平均完成服务的顾客数；(2)损失率:指顾客到达排队系统，未接受服务而离去的概率;（对损失制或系统容量有限而言）(3)服务强度：=/s；根据前面的约定，我们将主要分析系统的平稳分布。于是记：Pn：当系统达到统计平衡时处于状态n的概率（pn(t)）λn:当系统处于状态n时，新来顾客的平均到达率(单位时间内来到系统的平均顾客数)μn：当系统处于状态n时，整个系统的平均服务率。（单位时间内可以服务完的顾客数）当λn为常数时，记为λ；当每个服务台的平均服务率为常数时，记每个服务台的服务率为μ。S表示系统中并行的服务台数则当n≥s时，有μn＝sμ,于是令=/s，称为服务强度（trafficintensity）负指数分布密度函数0fort00)(tforetftT均值1)(TE方差21)(TVar随机变量T分布函数tetTP1)(fT(t)t1)(TE)()0(ttTtPtTPfT(t)tttfT(t)是一个严格下降函数第二节生灭过程和Poisson过程一、生灭过程简介一类非常重要其广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。定义1设{N(t)，t≥0}为一个随机过程。如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)，t≥0}为一个生灭过程。顾客到达——“生”；顾客离开——“灭”服务机构顾客聚顾客散顾客到达顾客离去n，n，生灭过程示意图：为求平稳分布，考虑系统在t+Δt时刻可能处的任一状态n的概率。状态转移图一般说来，得到是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为,n=0,1,2()(){()}nNtptPNtn的分布np方式T时刻状态概率（t,t+Δt）内发生的事件发生的概率1nPn(t)无到达，无离去（1-λnΔt）(1-μnΔt)2n-1Pn-1(t)到达一个，无离去λn-1Δt(1-μn-1Δt)3n+1Pn+1(t)无到达，离去一个(1-λn+1Δt)μn+1Δt4nPn(t)到达一个，离去一个(λnΔt)(μnΔt)各种方式发生概率表方式1，2，3，4互不相容且完备，于是：111111()()(1)(1)()()(1)()(1)()()()()nnnnnnnnnnnnnPttPtttPtttPtttPttt0()(()())limnnntdPttPttPtdtt1111()()()()nnnnnnnPtPtPtΔt2项都变为零对上式求导有：当n=0时，只有方式1和3，4发生，且方