第12章排队论(清华教材)

排队论Queueingtheory一、排队系统的特征及排队论第一节引言排队论（queueingtheory）是研究排队系统的数学理论和方法排队论又叫随机服务系统理论。在日常生活中，人们会遇到各种各样的排队问题。如进餐馆就餐，到图书馆借书，在车站等车，去医院看病，去售票处购票，上工具房领物品等等。在这些问题中，餐馆的服务员与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医生与病人、售票员与买票人、管理员与工人等，均分别构成一个排队系统或服务系统。是运筹学的一个重要分支。排队问题的表现形式往往是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥挤现象会愈来愈普遍。一、排队系统的特征（2）第一节引言（2）排队除了是有形的队列外，还可以是无形的队列。排队的可以是人，也可以是物。如生产线上的原材料或半成品在等待加工；因故障而停止运转的机器在等待修理；码头上的船只等待装货或卸货；要降落的飞机因跑道被占用而在空中盘旋等等。当然，提供服务的也可以是人，也可以是跑道、自动售货机、公共汽车等。为了一致起见，我们约定一些术语：顾客将要求得到服务的对象统称为“顾客”服务员或服务机构将提供服务的服务者称为“服务员’或“服务机构”排队系统的一般描述（1）实际的排队系统可以千差万别，但都可以一般地描述如下：顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统顾客到达服务台服务完成后离去队列正在接受服务的顾客单服务台排队系统顾客到达服务台1服务完成后离去队列多服务台排队系统服务台2服务台S排队系统的一般描述（2）但不管具体的排队系统何种形式，都可描述成下列形式顾客到达服务台1服务完成后离去多个队列多服务台多队列的排队系统服务台2服务台S多服务台串联排队系统队列顾客到达服务台1服务完成后离去队列服务台2输入（聚）服务机构输出（散）排队系统的一般描述（3）上图通常称为一个随机聚散服务系统输入（聚）服务机构输出（散）任一排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达，“散”表示顾客的离去。随机性则是排队系统的一个普通特点：是指顾客的到达情况（如相继到达时间间隔）与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的.因此，排队论又称为随机服务系统理论。二、排队系统的描述排队系统概括起来可看成由3个基本部分组成：1.输入过程输入过程说明顾客接怎样的规律到达系统，需要从三个方面来刻划一个输入过程(1)顾客总体（顾客源）数可以是有限的，也可以是无限的河流上游流入水库的水量可认为是无限的车间内停机待修的机器是有限的输入过程排队及排队规则服务机制(2)到达方式是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到达(3)顾客（单个或成批）相继到达时间间隔的分布这是刻划输入过程的最重要的内容令T0＝0，Tn表示第n个顾客到达的时刻则有T0T1T2…Tn…输入过程(2)(3)顾客（单个或成批）相继到达时间间隔的分布这是刻划输入过程的最重要的内容令T0＝0，Tn表示第n个顾客到达的时刻则有T0T1T2…Tn…顾客到达的时刻顾客相继到达的间隔时刻记Xn=Tn-Tn-1,(n＝1，2，…)则Xn是第n个顾客与第n一1个顾客到达的时间间隔一般，假定{Xn}是独立同分布的记分布函数为A(t)输入过程(3)1)定长分布(D)顾客相继到达时间间隔为一常数a如产品通过传送带进入包装箱就是定长分布的例子。用随机变量表示所在顾客到达间隔时间，则P(＝a)=1，用分布函数表示有：其数学期望atattPtF10}{)(关于{Xn}的分布，排队论中经常用到的有以下几种：Ea输入过程(4)称服从负指数分布，其分布函数为负指数分布常作各种“寿命”分布的近似，例如无线电器元件的寿命、动物寿命、电话问题中的通话时间等负指数分布的一个重要性质是无记忆性或无后效性即}{}|{xPtxtP2)负指数分布（记为M）一个随机变量，它的分布密度函数为000)(ttetat0001}{)(ttetPtFt其数学期望1E方差21D输入过程(5）3)最简流或称Poisson流(M)顾客相继到达时间间隔｛Xn｝为独立的,服从同参数的负指数分布其密度函数为000)(ttetat（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)每个顾客接受服务的时间相互独立，具有相同的负指数分布：000)(ttetbt其中μ＞0为一常数3、服务机制的描述(2)(3)K阶爱尔朗分布(EK)每个顾客接受服务的时间服从k阶爱尔朗分布，其密度函数为其中μ＞0，为一常数tkkektkktb)!1()()(1爱尔朗分布比负指数分布具有更多的适应性当k=1时，爱尔朗分布即为负指数分布；当k增加时，爱尔朗分布逐渐变为对称的事实上，当k≥30以后，爱尔朗分布近似于正态分布。当k→∞时，由方差为1/kμ2可知，方差将趋于零，即为完全非随机的。所以，K阶爱尔朗分布可看成完全随机（K=1）与完全非随机之间的分布，能更广泛地适应于现实世界。三、排队系统的符号表示和模型分类可根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类：D.G.Kendall提出一种目前在排队论中被广泛采用的“Kendall记号”A表示系统的容量，即可容纳的最多顾客数其一般形式为：X／Y／Z／A／B／C其中X表示顾客相继到达时间间隔的分布；Y表示服务时间的分布；B表示顾客源的数目Z表示服务台的个数；C表示服务规则例如，M／M／1／∞／∞／FCFS表示了一个顾客的到达时间间隔服从相同的负指数分布、服务时间为负指数分布、单个服务台、系统容量为无限（等待制）、顾客源无限、排队规则为先来先服务的排队模型。三、排队系统的符号表示(2)在排队论中，一般约定如下：如果Kendall记号中略去后3项时例如：M／M／1／∞／∞／FCFS表示为M／M／1的排队模型M／M／s／K则表示了一个顾客相继到时间间隔服从相同的负指数分布、服务时间为负指数分布、s个服务台、系统容量为K、顾客源无限、先来先服务的排队模型。是指X／Y／Z／∞／∞／FCFS的情形GI／M／1则表示一个单服务台、服务时间为负指数分布、顾客相继到达时间间隔为独立同分布的等待制排队模型，四.排队系统的主要数量指标和记号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,称为平均排队长根据前面的约定，我们将主要分析系统的平稳分布，当系统达到统计平衡时