教学材料《运筹学》-第8章

第8章排队论学习目标通过本章的学习，了解排队论基本概念及随机服务系统基本特征，认识输入过程和服务时间分布，掌握泊松输入—指数服务排队模型和排队系统的优化问题的求解。上一页下一页返回第8章排队论关键词汇排队论(QueuingTheory)随机服务系统(StochasticServiceSystem)Kendall符号(Kedall-Symbol)泊松过程(PoissonProcess)负指数分布(NegativeExponentialDistribution)队长(QueueLength,theAverageNumberofUnitsintheSystem)队列长(QueueSize,theAverageNumberofUnitsWaitingintheQueue)逗留时间(TheAverageTimeintheSystembyanArrival)等待时间(WaitingTime)上一页下一页返回第8章排队论状态概率(StateProbability)Little公式(Little'sFormula)M/M/1模型(M/M/1Model)生灭过程(Birth-deathProcess)M/M/c模型(M/M/cModel)M/M/1/m/m模型(M/M/1/m/mModel)M/M/c/m/m模型(M/M/c/m/mModel)M/G/1模型(M/G/1Model)M/D/1模型(M/D/1Model)排队系统优化(QueuingSystemsOptimization)上一页下一页返回第8章排队论案例导引例一某火车站售票处有3个窗口，同时售各车次的车票。购票顾客的陆续到达时间是随机的，服从泊松分布，平均每小时到达54人。售票员对每位顾客的售票服务时间也是随机变量，服从负指数分布，每小时可平均服务24人。现在分两种情况讨论:

第一种情况，购票顾客排成一队，依次购票;

第二种情况，购票顾客在每个窗口排一队，依次购票，不准串队。分别在不同情况下计算:(1)售票员(1人，2人，3人)空闲的概率。

(2)购票顾客平均需要等待多少时间才能购票?一个顾客来购票，从到达售票处到购完票平均需要多少时间?(3)每个售票处内平均有多少顾客在排队等待购票?售票处平均有多少顾客(包括排队等待的和正在购票的)?上一页下一页返回第8章排队论

例二考虑人们日常遇到的一些问题:上、下班或节假日，当候车人较多时，搭乘公共汽车需要排队等待;顾客到商店购买物品或到银行、储蓄所存取款;病人到医院看病候诊;旅客到火车站售票处排队购买车票;几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆，则部分顾客只得在各自的要车处等待;通讯卫星与地面若干待传递的信息;生产线上的原料、半成品等待加工;因故障停止运转的机器等待工人修理;码头的船只等待装却货物;要降落的飞机因跑道不空而在空中盘旋，等等。案例思考题:(1)分析上面例题的共同特点是什么?提炼问题特征。

(2)对于这类问题，我们关心哪些事情?如何得到我们关心的信息?若得到有关信息，我们可以进一步做些什么有益的工作?上一页返回下一页8.1排队论基本概念

排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory)，是一门研究拥挤现象(排队、等待)的科学。1909年，丹麦工程师爱尔朗(A.K.Erlang)在研究电话系统时创立了这个研究方向，一百年来排队论的理论日渐完善，应用越来越广泛。特别是自20世纪50年代以来，随着计算机科学与技术的飞速发展，排队论的应用领域大大拓宽，显示出很好的发展前景。排队论是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。下一页返回上一页8.1排队论基本概念

通过前面的例子我们看到，排队是在日常生活和生产中经常遇到的现象。存在有形的排队和无形的排队现象，顾客分散在不同地方约定出租车，由于出租车数量不足，就会形成一个等待派车的无形队列。排队的顾客一般是人，如买车票、买东西、就医等;排队的顾客也可以是物，如等待传递的信息、生产线上的原料、因故障停止运转的机器、要降落的飞机等。显然，上述例子中所指问题虽各不相同，但却都有一些共同特征:要求得到某种服务的人或物(顾客)，提供服务的人或机构(服务台)，顾客到来与服务时间的随机性等。上一页下一页返回8.1排队论基本概念8.1.1排队系统的系统特征和基本排队过程

1)排队系统特征实际的排队系统虽然千差万别，但是它们有以下的共同特征。①顾客:有请求服务的人或物，统称顾客。②服务台:有为顾客服务的人或物，称服务员或服务台。③随机性:顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间也常常是随机的(有时其中某一个可以是定长的)，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。上一页下一页返回8.1排队论基本概念2)基本排队过程

图8-1表示了一般排队问题的基本排队过程。从图8-1可知，每个顾客由顾客源(潜在的顾客群)，按一定方式到达服务系统，构成了这个随机服务系统的输入，可称为“聚”;顾客到达系统后，首先加入队列排队等待，等待过程结束后，服务台按一定规则从队列中选择顾客进行服务;获得了服务的顾客立即离开，就是本系统的输出，可称为“散”。通常，由图8-1表示的系统称为随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去，所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。上一页下一页返回8.1排队论基本概念

面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。于是，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论—排队论所要研究解决的问题。上一页下一页返回8.1排队论基本概念8.1.2排队系统的基本组成部分

通常，排队系统都有输入过程、服务规则和服务台等3个组成部分。

(1)输入过程。这是指要求服务的顾客到达排队系统过程的规律特征，有时把它简称为顾客流(单位时间到达的顾客数)。排队系统的输入过程一般涉及3个方面。①顾客总体数，又称顾客源、输入源。这是指潜在顾客数量(顾客一定是从某个潜在顾客集合来到排队系统的，故称“源”)。顾客源可以是无限的，指潜在顾客与实际到达的顾客数相比，数量相差非常大的情况。这种情况下，顾客到达系统的随机规律不会因某些潜在顾客的加入或退出而改变，如到医院看病、到商店购物、到火车站售票处购票的顾客总数可以认为是无限的;顾客源也可以是有限的，指潜在上一页下一页返回8.1排队论基本概念

顾客与实际到达的顾客数相比，数量相差不大的情况。这种情况下，只要有某些潜在顾客加入或退出，顾客到达系统的随机规律就会受到影响而改变，如某个工厂车间因故障待修的机床，这时车间内的机床是潜在顾客，当机床出现故障，需要维修人员检修时机床就成为了顾客。当机床被修好恢复工作，表示此顾客离开了系统。显然，这种情况下的顾客源是有限的。②顾客到达方式。这是描述顾客是怎样来到系统的，如他们是单个到达，还是成批到达。例如，病人到医院看病就是单个到达的;而在库存问题中，如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。下文的讨论在单个到达的基础上进行。上一页下一页返回8.1排队论基本概念③顾客流的概率分布，或顾客相继到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达k个顾客(k=1,2,…)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。

(2)服务规则。这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。①损失制。这是不允许等待的系统。如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们不等待，就自动离开系统。典型例子是，如大城市某停车场的停车位是有限的，这些停车位就是此排队系统的服务台，当所有停车位均已经被占用时，再来的汽车因无法停车而自动离去，这种服务规则即为损失制。上一页下一页返回8.1排队论基本概念②等待制。这是指当顾客来到系统时，若所有服务台都不空，则顾客加入排队行列等待服务，直到服务完成才离开系统。例如，排队等待售票、故障设备等待维修等。在等待制中，服务台在选择顾客进行服务时，常有如下四种规则:

先到先服务:按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。后到先服务:仓库中叠放的钢材，后叠放上去的都先被领走，就属于这种情况。随机服务:当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如通电话呼叫要求服务的情况。优先权服务:如老人、儿童先进车站，危重病员先就诊，遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。上一页下一页返回8.1排队论基本概念③混合制。这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种:

队长有限:当系统中的顾客人数(称为队长)超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳N个顾客的系统中，当新顾客到达时，若系统中的顾客数小于N时，则可进入系统排队或接受服务;否则，便离开系统。如理发店有2位理发师，除2个理发用椅外，另准备5把椅子放在店内，这意味着系统最多容纳7位顾客，即N=7。当理发店已有7位顾客时，再来的顾客就自动离去了。等待时间有限:顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。上一页下一页返回8.1排队论基本概念

逗留时间(等待时间与服务时间之和)有限:例如，用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内飞机未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记、为系统中服务台的个数，则当N=、时，混合制即成为损失制;当N=时，混合制即成为等待制。下文的讨论主要涉及队长有限的混合制问题。

(3)服务台情况。服务台情况可以从以下3方面来描述。①服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，在获得服务后离开系统。实际中，有许多不同形式的排队系统，如串并混联的系统、网络排队系统等。从构成形式上看，常见的服务台数量及排队结构情况有如下几种形式。上一页下一页返回8.1排队论基本概念(a)单队—单服务台式(如图8-2所示)。只有一个服务台，顾客到达时，如果服务台空闲，就接受服务，否则排队等待。

(b)单队—多服务台并联式(如图8-3所示)。有s(s>1)个服务台，顾客到达时，如果服务台空闲，就接受服务。否则，排成一队等待。在这种情况下，顾客接受服务的顺序顾客到达顺序完全一致，可以说，这是多个服务台完全共享的情况。

(a)多队—多服务台并联式(如图8-4所示)。有s(s>1)个服务台，顾客到达时，如果服务台空闲，就接受服务。否则，任选一个服务台进行排队等待，理论上不准串队。这种情况下，整个系统中有s个队列，互不影响，实际上这相当于s个单服务台的系统在工作。上一页下一页返回8.1排队论基本概念(d)单队—多服务台串联式(如图8-5所示)。有多个服务台按顺序排列，顾客到达每一服务台时，均面临单服务台的服务情况。由于是串联系统，所以各服务台的服务是有联系的。

(e)单队—多服务台并串联混合式，以及多队—多服务台并串联混合式(如图8-6所示)。这种情况相当于上述情况的混合。②服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客，属于成批服务。本文只讨论单个服务方式。③服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)，等等。上一页下一页返回8.1排队论基本概念8.1.3排队系统的描述符号与分类根据上述分析，排队系统涉及众多因素，各因素的差异必然会影响到对系统的认识和分析。为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，肯道尔(D.G.Kendall)提出了一种在单个到达及单个服务的前提下，描述众多排队模型的方式，目前在排队论中被广泛采用，称为“Kendall记号”。这种表达方式通常用6段符号，取如下固定格式表示:A/B/C/D/E/F

这里的字符A,B,C,D,E,F只是为了下文说明的方便，其本身不带有任何含义，重要的是它们代表的位置。各位置符号的意义为:上一页下一页返回8.1排队论基本概念A—表示顾客相继到达间隔时间分布。常用下列符号:

①M—表示到达过程为泊松过程(从流的角度看，随机变量为单位时间到达的顾客数)或负指数分布(随机变量为顾客相继到达的间隔时间)。②D—表示定长输入(顾客相继到达间隔时间是常数的情况)。

③Ek—表示左阶爱尔朗分布。

④G—表示一般相互独立的随机分布(顾客相继到达间隔时间是独立同分布的)。

B—表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。①M—表示到达过程为泊松过程(从流的角度看，随机变量为单位时间服务的顾客数)或负指数分布(随机变量取为每位顾客服务的时间)。上一页下一页返回8.1排队论基本概念②D—表示定长输入(为每位顾客服务的时间是常数的情况)。

③Ek—表示左阶爱尔朗分布。④G—表示一般相互独立的随机分布(为每位顾客服务的时间是独立同分布的)。

C—表示顾客共享服务台(员)的个数:"1”则表示单个服务台，“s”(s>1)表示多个服务台。

D—表示系统的顾客容量，或称队长容量限制数;如系统有N个位子(包括等待的和正在接受服务的顾客数)，则‘s≤N<∞，当N=s时，说明系统不允许等待，即为损失制。N=∞时为等待制系统。N为有限整数时，表示为混合制系统。上一页下一页返回8.1排队论基本概念E—表示顾客源的数量，分有限与无限两种。∞表示顾客源无限，一般若潜在顾客与可能到达系统的顾客数相比，比值非常大(即不会因为一些潜在顾客的变化而影响系统的输入随机特性)时，可确定为顾客源无限。例如，考虑一个工厂车间内，有限的机器设备因故障停机而进行维修服务的排队问题时，顾客源是有限的，为车间内的机器设备数(潜在顾客数)。

F—表示等待制或混合制排队系统的服务规则，常考虑用下列符号表示有关情况:

①FCFS:表示先到先服务的排队规则。②LCFS:表示后到先服务的排队规则。③PR:表示优先权服务的排队规则。利用“Kendall记号”可以较清晰地描述排队系统。例如，某排队问题为M/M/a/∞/∞/FCFS上一页下一页返回8.1排队论基本概念表示顾客到达间隔时间为负指数分布(或泊松流);服务时间为负指数分布;有s(s>1)个服务台;系统队长容量无限(等待制);顾客源无限，采用先到先服务规则。实际应用中，为了简便，规定了默认的省略形式:当第6段的服务规则为FCFS时，可省略而只用5段记号;若在此基础上，第5段的顾客源为无限时，可进一步省略而只用4段记号;若在此基础上，还有第4段的系统队长容量限制为无穷时，可再进一步省略而只用二段记号。由此，某些情况下排队问题仅用上述表达形式中的前3个符号。如不特别说明，又习于只有3段记号的排队系统描述，均理解为系统队长空间容量无限、顾客源无限，先到先那务，单个服务的等待制系统。上一页下一页返回8.1排队论基本概念8.1.4排队系统的主要数量指标研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标包括以下几个。

1)队长和排队长(队列长)

队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)，排队长是指系统中正在排队等待服务的顾客数，队长和排队长一般都是随机变量。对这两个指标进行研究时，当然是希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。队长的分布是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而确定合理的等待空间。上一页下一页返回8.1排队论基本概念2)等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，它是个随机变量，也是顾客最关心的指标，因为顾客通常是希望等待时间越短越好。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是个随机变量，顾客同样非常关心。对这两个指标的研究是希望能确定它们的分布，或至少能知道顾客的平均等待时间和平均逗留时间。

3)忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次空闲止的这段时间，即服务机构连续忙的时间，这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度。与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。上一页下一页返回8.1排队论基本概念除了上述几个基本数量指标外，还会用到其他一些重要的指标，如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。下面给出上述一些主要数量指标的常用记号。

4)一些数量指标的常用记号排队系统具有的共同特征是随机性，它对系统的运行起着根本性的作用。随机性在一般情况下，又与事件发生的时刻有关，因此，需要考虑下面的随机变量。

N(t):随机变量。表示在时刻t，系统中的顾客数(又称为系统的状态)，即队长。

Na(t):随机变量。表示在时刻t，系统中排队的顾客数，即排队长(队列长)。上一页下一页返回8.1排队论基本概念T(t):随机变量。表示时刻t到达系统的顾客，在系统中的逗留时间。

Ta(t):随机变量。表示时刻t到达系统的顾客，在系统中的等待时间。上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于(或近似趋于)一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的平稳状态下的性质，即统计平衡性质。本章使用如下具有统计平衡性质(平稳状态下)的主要性能指标。上一页下一页返回8.1排队论基本概念(1)主要性能指标。

L—平均队长，即稳态系统任一时刻的所有顾客数的期望值。

La—平均排队长(队列长)，即稳态系统任一时刻的等待服务的顾客数的期望值。

W一平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值。

Wa—平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而对顾客而言系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。上一页下一页返回8.1排队论基本概念(2)参数数量指标。

s—系统中顾客共享的并联服务台的数目。

λ—顾客的平均到达率(单位时间到达的顾客数)。相继到达顾客的平均间隔时间为1/λ。

μ—平均服务率(单位时间服务的顾客数)。为顾客服务的平均时间为1/μ

。ρ—服务强度，即单位时间内，顾客平均到达数与服务台平均服务顾客数的比值，表达式为ρ=λ/(sμ)。上一页下一页返回8.1排队论基本概念(3)基本特征量。

—稳态系统状态概率，即任一时刻系统状态为n(系统中恰好有n个顾客)的概率;特别当n=0时，P0为稳态系统所有服务台全部空闲(系统中顾客数为0)的概率。

λe—有效平均到达率，即单位时间内进入系统的期望顾客数。对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则顾客自动离去，不再进入系统。这就是说，到达的顾客不一定全部进入系统接受服务。因此，需要考虑实际进入系统的顾客数期望值，为此引入有效平均到达率λe。实际上，λ是单位时间内来到系统(包括未进入系统)的期望顾客数，对于等待制的排队系统，有λe=λ0一般地， 。上一页下一页返回8.1排队论基本概念

在实际中，可以引入平均有效离去率的概念。同有效到达率一样，由于系统容量有限，实际到达的顾客是有损失的，既然顾客没有进入系统，其离去情况也必然受到影响。从平稳系统中均值的意义看，容易理解平均有效离去率等于平均有效到达率，即μ

e=λe

。一般地，平均有效离去率(顾客接受服务后离去的数学期望值)为 。

5)李特尔(Little)公式对于λe

、L,、La、W、Wa这5个量之间的关系，李特尔(JohnD.C.Little)建立了相关的关系式。在系统达到稳态时，假定有效平均到达率为λe

，则有下面的公式上一页下一页返回8.1排队论基本概念公式(8一1)可以作这样的几何解释(如图8-7）:稳态时，顾客进入系统后，每单位时间平均到达λe位顾客。平均队长L由时间段内W个λe位顾客组成，即L=λeW。同理，可得到La=λeWa。假设平均服务时间为常数1/μ，则有顾客平均逗留时间是顾客平均等待时间与平均服务时间之和，即将公式(8-1)和式(8-2)代入式(8-3)，即可得到上一页下一页返回8.1排队论基本概念因此，只要知道λe与L,、La、W、Wa俄四者之一，则其余三者就可由Little公式求得。对于平均队长和平均队列长，可用下列公式计算。因此，只要知道Pn(n=0,1,2,}}})，则L或La

就可由式(8-5)或式(8-6)求得，从而再由式(8-1)~式(8-4)就能求得四项主要工作指标。上一页下一页返回8.1排队论基本概念思考题(1)排队论主要研究的问题有什么特点?(2)试述排队模型的种类及各组成部分的特征。(3)Kendall符号A/B/C/D/E/F中各字母分别代表什么意义，它们的内涵是什么?(4)理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念。(5)排队系统的主要数量指标有哪些?理解它们的内涵。上一页返回下一页8.2研究的基本问题与排队论问题求解思路8.2.1排队论研究的基本问题排队论研究的首要问题是认识、分析当前的系统，即研究系统的整体性质、排队系统主要数量指标的概率规律，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。

(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。

(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到这样的问题:检验系统是否达到平稳状态、检验顾客相继到达时间间隔的相互独立性、确定服务时间的分布及有关参数等。下一页返回上一页8.2研究的基本问题与排队论问题求解思路(3)系统优化问题，又称为系统控制问题或系统运营问题。研究的基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，涉及内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。对于一般的排队系统运行情况的分析，通常是在给定输入与服务的条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标:系统中顾客数(队长)的期望值La排队等待的顾客数(排队长)的期望值La顾客在系统中全部时间(逗留时间)的期望值W、顾客排队等待时间的期望值Wa

。上一页下一页返回8.2研究的基本问题与排队论问题求解思路8.2.2重要的概率分布与生灭过程由前所述，顾客到达和服务时间一般都是随机变量。在排队系统中，常考虑的概率分布有如下几种(下面进行简单介绍，用ξ表示时间随机变量、用N表示顾客数)。

1)定长分布定长分布是指顾客有规则地等距到达(或服务时间为常数)，每隔时间α到达一个顾客(或服务一个顾客)。这时顾客相继到达间隔(或服务时间)ξ的分布函数F(t)为上一页下一页返回8.2研究的基本问题与排队论问题求解思路2)泊松(Poisson)输入泊松输入又称最简单流。对顾客流(单位时间的顾客数)而言，满足下面4个条件的输入称为最简单流。

u)平稳性。又称作输入过程是平稳的，指在长度为t的时段内恰好到达h个顾客的概率仅与时段长度有关，而与时段起点无关，即对任意a∈(0,∞)，在(a,a+t]或(0,t]内恰好到达k个顾客的概率相等。即

(2)无后效性。指在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的。上一页下一页返回8.2研究的基本问题与排队论问题求解思路(3)单个性又称普通性。指在充分小的时段(，内有2个及2个以上顾客到达的概率很小，即其中， 表示在 时间段内到达k个顾客的概率。单个性的含义是，当时间间隔充分地小时，近似地只有两种状态:有1个顾客或没有顾客到达。

(4)有限性。指在任意有限时间区间内，到达的顾客数是有限的。因为泊松流实际应用最广，也最容易处理，因而研究得也较多。可以证明，对于泊松流，在长度为t的时间内到达k个顾客的概率 服从泊松分布，即上一页下一页返回8.2研究的基本问题与排队论问题求解思路

其中参数λ>0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。泊松分布的均值E[N]和方差D[N]有，E[N]=D[N]=λ。如果顾客到达是以几为参数的泊松流，可以证明顾客相继到达时间间隔ξi,i=1,2,…是相互独立同分布的，其分布是以几为参数的负指数分布。3)负指数分布分布函数为其中，拜μ>0为一常数，是单位时间平均服务的顾客数，称为平均服务率。负指数分布的数学期望(均值)E(ξ)=1/μ

，即平均月及务时间是参数。的倒数。上一页下一页返回8.2研究的基本问题与排队论问题求解思路4)k阶爱尔朗(Erlang)分布k阶爱尔朗分布是指时间随机变量ξ相互独立，具有相同的分布，其分布密度为其中，k为非负整数。k阶爱尔朗分布的分布函数为上一页下一页返回8.2研究的基本问题与排队论问题求解思路k阶爱尔朗分布的数学期望为E[ξ]=k/λ,方差为D[ξ]=k/λ2。可以证明，在参数为几的泊松输入中，对任意的了与k，设第了与第了+k个顾客之间的到达间隔为 ，则随机变量Tk的分布必遵从参数为λ的k阶爱尔朗分布。例如，某排队系统有并联的k个服务台，顾客流为泊松流，规定第i,k+i,2k+i,…个顾客排入第i号台(i=1，2，…，k)，则第k台所获得的顾客流即为爱尔朗输入流，其他各台从它的第一个顾客到达以后开始所获得的流也为爱尔朗输人流。特别地，当k=1时，k阶爱尔朗分布将化为负指数分布。上一页下一页返回8.2研究的基本问题与排队论问题求解思路刘生灭过程与状态转移速度图假定一个系统具有状态集S={0，1，2，…，n}，并且存在常数t(t≥0)时刻，记状态随机变量为K(t)，系统内有n个顾客的概率为Dn(t)，经过△t时间，如果满足则称这个随机过程 为有限状态S上的生灭过程。当系统具有可列无限状态集S={0，1，2，…}时，则称为无限状态的生灭过程。上一页下一页返回8.2研究的基本问题与排队论问题求解思路

我们把充分小的△t固定，直接用参数λn和μn拜表示λn△t和μn△t，生灭过程可利用状态转移速度图来描述“生”“灭”导致状态转移的过程。注意，实际上，λn和μn的取值不需要考虑△t的大小，只要保证二者的基础时段一致即可(计算中考虑的是二者的比率)。有限状态生灭过程的状态转移速度图如图8-8所示。无限状态生灭过程的状态转移速度图如图8-9所示。根据泊松流的普通性，当△t充分小时，在(t,t+△t)时间段内有一个顾客到达的概率为λn△t+o(△t)，而无顾客到达的概率为1-λn△t+o(△t)，故泊松输入—指数服务排队系统的状态转移过程是生灭过程。因此，可以通过状态转移速度图研究状态概率之间的关系。上一页下一页返回8.2研究的基本问题与排队论问题求解思路8.2.3泊松输入—指数服务排队系统的求解

1)状态概率之间的关系为了便于理解，下面用两个思路研究泊松输入—指数服务排队系统中，状态概率之间的关系。

(1)直接通过概率发生情况讨论系统状态概率之间的关系。设λn为当系统状态n时，顾客进入系统的平均速度;μn为系统状态n时，顾客离开系统的平均速度;Dn(t)为在t时刻，系统内有n个顾客的概率。那么，根据普通性，当△t充分小时，在(t,t+△t)有一个顾客到达的概率为λn△t，而无顾客到达的概率为1-λn△t。这种情况下，可以有4种状态转化发生导致在t+△t时刻系统中有n个(n>0)顾客，表8-1所示为各种方式发生概率。上一页下一页返回8.2研究的基本问题与排队论问题求解思路显然，方式1，2，3，4互不相容且完备，于是由于系统是稳态的，因而Dn(t)关于t的导数为零，即注意:式((8-13)中的(△t)2项都变为零。对于稳态系统，状态与时刻无关，以下省略参数t，用Dn取代Dn(t)。上一页下一页返回8.2研究的基本问题与排队论问题求解思路当n=0(即系统中无顾客)时，表8-1中的状态概率只有方式1,3,4发生，且方式1中无离去的概率为1，则式(8-13)左端只含有两项。根据式(8-13)，可以推导出各状态概率之间的关系:上一页下一页返回8.2研究的基本问题与排队论问题求解思路由于各状态发生的事件两两不相容且完备，故有艺 。于是根据各状态概率的关系可求出状态概率 。

(2)利用状态转移速度图导出各状态概率之间的关系。不失一般性，我们以无限状态的生灭过程的状态转移速度图来讨论泊松输入—指数服务排队系统的状态转移规律。排队系统的状态是指系统中的顾客数0,1,2,…,n-l,n,n+1,…,那么系统位于各个状态的概率分别为P0，P1，P2,...,Pn-1,Pn,Pn+1,...。系统中某一状态的概率仅与其相邻状态的概率以及从相邻状态转移到该状态的转入率λn和转出率μn有关，可以建立相应的状态转移速度图(图8-10)。上一页下一页返回8.2研究的基本问题与排队论问题求解思路图中，圆圈表示状态，其中的数字、符号表示系统中该状态的顾客数，箭头表示从一个状态到另一个状态的转移。λi表示由状态i转移到状态i+1的转移速率，i=0,1,2,…;λj表示由状态j转移到状态j一1的转移速率，j=1,2,...

根据上面的讨论，顾客的泊松输入和服务时间负指数分布意味着具有普通性(单个性)，即在充分短的时间段内至多到达或服务一个顾客。在这个意义下，当时间单位段充分小时，单位时间到达的顾客数λ(单位时间接受完服务的顾客数μ)可以视为这充分小的单位时间段内到达(离开)一个顾客的可能性(转移速率)。由生灭过程(图8-10)可得到:转入率=转出率，于是上一页下一页返回8.2研究的基本问题与排队论问题求解思路当n=0时，,可得 。当n=1时， ，将 代入，可得 ，于是有p2= 。一般地，当n>0时， ，可导出根据概率性质: ，可计算pn（n=0,1,2，…）。上一页下一页返回8.2研究的基本问题与排队论问题求解思路2)泊松输入—指数服务排队系统的求解步骤排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数不同，顾客源有限无限、排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型。若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面以泊松输入—指数服务排队系统为主，介绍求解步骤。首先，在分析问题的基础上，用肯道尔(Kendall)符号描述所研究的排队系统模型。对于泊松输入—指数服务排队系统，确定基本参数系统中顾客共享的并联服务台的数目s、顾客的平均到达率(单位时间到达的顾客数)λ、平均服务率(单位时间服务的顾客数)μ等，注意λ和μ必须单位一致(单位时间的顾客数)。进行下列工作。上一页下一页返回8.2研究的基本问题与排队论问题求解思路(1)根据已知条件绘制状态转移速度图。这一步的关键问题是转移速率参数λ

n

和μn的确定。(2)依据状态转移速度图写出各稳态概率之间的关系。可以按照前面介绍的思路，找出状态概率之间的关系，用p0来表示p0(n=0,1,2,…)。(3)求出p0及pn。根据概率性质 ，可计算p0(n=0,1,2,…)。(4)计算各项数量运行指标。计算有效平均到达率 ，以及 (服务台数 为1时)或 (服务台数大于1时)。上一页下一页返回8.2研究的基本问题与排队论问题求解思路

然后利用李特尔(Little)公式求出其他几个量La(服务台数为1时)或L(服务台数大于1时)、W、Wa。根据问题的要求，再计算其他所需的量。

(5)用系统运行指标构造目标函数，对系统进行优化。有些问题需要考虑系统优化的问题，这时需要根据要求构造目标函数，进行优化计算。例8.1某汽车加油站用两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达18辆汽车。若加油站中已有k辆车，当k≥2时，有k/6的顾客将自动离去。加油时间服从负指数分布，平均每辆车需要5分钟。试求:上一页下一页返回8.2研究的基本问题与排队论问题求解思路(a)系统空闲的概率为多少?(b)求系统满的概率是多少?(c)求系统服务台不空的概率;(d)若服务一个顾客，加油站可以获得利润10元，问平均每小时可获得利润为多少元?(e)每小时有多少顾客数因等待问题没有接受服务而离去?(f)加油站平均有多少辆车在等待加油?平均有多少个车位被占用?进入加油站的顾客需要等多长时间才能开始加油?进入加油站的顾客需要多长时间才能离去?

解注意有下划线的文字，本例的模型是非标准的M/M/2/6模型。按照问题的实际情况，绘出状态转移速度图(图8-11)，注意当状态n>1时，转出速率为2μ

，这是因为有2个顾客接受服务，考虑有1个顾客离去的速率。参数以小时为单位λ=18,μ=60/5=120。上一页下一页返回8.2研究的基本问题与排队论问题求解思路稳态概率关系:由p0+p1+p2+p3+p4+p5+p6=1得到p0=0.22433,p1=0.33649,p2=0.25237,p3=0.12618，p4=0.04732，p5=0.01183，p6=0.00148。上一页下一页返回8.2研究的基本问题与排队论问题求解思路计算运行指标:(a)系统空闲的概率p0=0.22433。(b)系统满的概率即p6=0.00148。(c)系统服务台不空的概率，即p忙=p2+p3+p4+p5+p6=1-p0-p1=0.43918。(d)每小时服务的平均顾客数，即平均有效离去率。服务一个顾客，加油站可以获得利润10元，故平均一小时可获利润10μe=145.78元。

(e)每小时顾客数因等待问题没有接受服务而离去的期望值，称为平均损失量,注意λe=μe

。上一页下一页返回8.2研究的基本问题与排队论问题求解思路(f)首先计算 ，再利 用Little公式求其他量:故加油站平均有0.26223辆车在等待加油，平均有1.47708个车位被占用，进入加油站的顾客需要等1.08分钟才能开始加油，进入加油站的顾客需要6.08分钟才能离去。上一页下一页返回8.2研究的基本问题与排队论问题求解思路思考题(1)了解本章主要研究排队论哪些基本问题。(2)分别讨论泊松分布、负指数分布、爱尔朗分布的主要性质;泊松分布和负指数分布的联系和区别是什么?(3)什么是生灭过程?理解状态转移速度图的意义。

(4)试述队长和排队长、等待时间和逗留时间、有效到达率、损失率等概念及他们之间的联系与区别。

(5)理解泊松输入—指数服务排队模型的特征及求解过程。上一页返回下一页8.3泊松输入—指数服务排队模型8.3.1单服务台无限源排队系统(M/M/1/./.)1)M/M/1/∞/∞系统此系统的主要参数为服务台数目为1、顾客的平均到达率(单位时间到达的顾客数)为λ、平均服务率(单位时间服务的顾客数)为μ，服务强度为ρ=λ/μ

。状态转移速度图如图8-12所示。稳态概率方程为当ρ≥1时， 不收敛，故应ρ<1，即λ<μ。根据概率性质 ，把式(8-15)代入，即 ，得到下一页返回上一页8.3泊松输入—指数服务排队模型由于系统容量无限，有λe=λ，下面计算平均队长利用李特尔(Little)公式求出其他三个量La、W、Wa：上一页下一页返回8.3泊松输入—指数服务排队模型在排队系统中，常用到以下一些指标。设系统内顾客数的随机变量为N，那么系统内顾客数多于k个的概率为可以证明，顾客逗留时间服从参数为μ-λ的负指数分布。设顾客在系统内逗留时间的随机变量为U，那么顾客逗留时间超过t的概率为设忙期、闲期和忙的概率、闲的概率分别为T忙、T闲和p忙、p闲，那么可以进行计算:上一页下一页返回8.3泊松输入—指数服务排队模型可以看到，T闲

=1/λ(当时间段充分小时，1/λ就反映了在这个时间段内没有顾客的时间)，于是例8.2某医院急诊室一次只能诊治1个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。对此排队系统分析如下。(模型为M/M/1/∞/∞，可简记为M/M/1)(a)先确定参数值。由题意知这是单服务台系统，有λ=3(人/小时)，μ=60/15=4(人/小时)，故服务强度为上一页下一页返回8.3泊松输入—指数服务排队模型(b)计算稳态概率:p0=1-ρ=1-0.75=0.25,pn=ρnp0;其中，p0是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。而病人需要等待的概率也是急诊室繁忙的概率，为P(Q>0)=1一p0=ρ=0.75。C.)计算系统主要工作指标:此模型的平均有效到达率，即到达率λ。急诊室内外的病人平均数: (人)，以下用Little公式计算。急诊室外排队等待的病人平均数: (人)。病人在急诊室内外平均逗留时间: (小时)。病人平均等候时间:上一页下一页返回8.3泊松输入—指数服务排队模型(d)为使病人平均逗留时间不超过半小时，平均服务时间应减少到多少?由于 ，把λ=3,μ

≥5代入解得，平均服务时间为即平均服务时间至少应减少3分钟。(e)若医院希望候诊的病人90%以上都能有座位，则候诊室至少应安置多少座位?设应安置x个座位，则加上急诊室内一个座位，共有x+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于x+1个”的概率不小于90%，即上一页下一页返回8.3泊松输入—指数服务排队模型两边取对数为 ，因ρ<1，故所以x≥6，即候诊室至少应安置6个座位。

2)M/M/1/N/∞系统此系统的主要参数包括:服务台数目为1、顾客的平均到达率为(单位时间到达的顾客数)λ、平均服务率(单位时间服务的顾客数)为μ，服务强度为ρ=λ/μ

，系统容量(队长)有限为N，状态转移速度图如图8-13所示。上一页下一页返回8.3泊松输入—指数服务排队模型稳态概率方程根据概率性质: ，把式(8-16)代入，即 ，得到由于系统容量(队长)有限为N，根据状态转移速度图(图8-13)有上一页下一页返回8.3泊松输入—指数服务排队模型可以推出平均队长实际上，当N不是很大时，可以用公式 直接计算。利用李特尔(Little)公式求出其他三个量L、W、Wa

：上一页下一页返回8.3泊松输入—指数服务排队模型在这类排队系统中，常用损失率指标为例8.3某美容店为私人开办并自理业务，店内面积有限，只能安置3个座位供顾客等候，一旦满座，则后来者不再进店而自动离开。已知顾客到达间隔与美容时间均为指数分布，平均到达间隔80分钟，平均美容时间为50分钟。试求任一顾客的期望等侯时间及该店潜在顾客的损失率。解这是一个M/M/1/N系统。由题意知上一页下一页返回8.3泊松输入—指数服务排队模型故服务强度则可计算出 进一步可计算这里N=4，可以直接用期望值公式计算。下面用Little公式计算。

上一页下一页返回8.3泊松输入—指数服务排队模型故任一顾客期望等待时间为该店潜在顾客的损失率即系统满员的概率:3)损失制M/M/1/1系统顾客到达时若服务台被占用则立即离开。因为只有p0和p1，直接可得上一页下一页返回8.3泊松输入—指数服务排队模型

例8.4某重要设施是由三道防线组成的防空系统。第一道防线上配备2座武器，第二道防线上配备3座武器，第三道防线上配备1座武器，所有的武器类型一样。武器对来犯敌人的射击时间服从μ=1(架/分钟)的指数分布，敌机来犯服从λ=2(架/分钟)的泊松流。试估计该防空系统的有效率。解考虑敌机进犯时，每道防线的武器将联合发挥作用。于是该防空系统的有效率=1-三道防线的损失率三道防线均可看成M/M/1/1系统，前一防线的损失即为后一防线的输入。设第一、二、三道防线成功防卫的事件分别为A1,A2,A3, 为A的反事件。那么上一页下一页返回8.3泊松输入—指数服务排队模型第一道防线:第二道防线:上一页下一页返回8.3泊松输入—指数服务排队模型第三道防线:总损失率=λ3损/λ=0.05/2=0.025,该防空系统的有效率=1一总损失率=0.975。上一页下一页返回8.3泊松输入—指数服务排队模型8.3.2多服务台无限源排队系统(M/M/s/./.1)M/M/s/∞/∞系统此系统的主要参数包括:服务台数目为s(s>1)、顾客的平均到达率(单位时间到达的顾客数)λ、每个服务台(各服务台服务时间是相互独立且同分布)的平均服务率(单位时间服务的顾客数)μ、服务强度为ρ=λ/sμ。状态转移速度图如图8-14所示，状态转入速率与状态无关，均为几，而状态转出速率与接受服务的顾客数有关。若有左个顾客接受服务，其中一个顾客接受完服务的可能性为kμ

。上一页下一页返回8.3泊松输入—指数服务排队模型根据上面的分析，可得当n<s时， ；当n≥s时， 。于是上一页下一页返回8.3泊松输入—指数服务排队模型根据概率性质: ，把式(8-18)代入，即得到可以推出利用李特尔(Little)公式求出其他三个量L、W、Wa：上一页下一页返回8.3泊松输入—指数服务排队模型

例8.5某火车站售票处有3个窗口同时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达λ=0.9(人/分钟)，服务时间服从负指数分布，平均服务率μ=24(人/小时)，分两种情况:①顾客排成一队，依次购票;②顾客在每个窗口排一队，不准串队。求:(a)售票处空闲的概率;(b)平均等待时间和逗留时间;(c)平均队长和平均队列长。解①首先，建立排队模型M/M/3/∞/∞。参数单位应相同λ=0.9(人/分钟)，μ=0.4(人/分钟)。记λ=λ/(3μ)=0.75，由图8-15,稳态概率之间的关系为上一页下一页返回8.3泊松输入—指数服务排队模型由于是计算平均队列长上一页下一页返回8.3泊松输入—指数服务排队模型记 ，求不定积分再求微分，得又λe=λ，利用李特尔(Little)公式求出其他三个量L、W,、Wa：上一页下一页返回8.3泊松输入—指数服务排队模型故售票处完全空闲的概率为0.0748;平均等待时间Wa=1.893分钟;平均逗留时间W=4.393分钟;平均队长L=3.954(人);平均队列长La=1.704(人)。②实质上，此情况为M/M/3/∞/∞三个相同的独立系统并联系统。对每个系统，参数单位应相同λ=0.3(人/分钟)μ=0.4(人/分钟)。记ρ=λ/μ=0.75，于是p0=1-ρ=0.25，2个服务台空闲的概率成=0.625,3个服务台都空闲的概率成p02=0.015625，计算平均队长，L=ρ/(1-ρ

)=3,3个系统的总顾客数为9。又λ

e=λ

，利用李特尔(Little)公式求出其他三个量:上一页下一页返回8.3泊松输入—指数服务排队模型3个系统的总排队顾客数为6.75。故售票处完全空闲的概率为0.015625;平均等待时间Wa=7.5(分钟);平均逗留时间W=10(分钟);平均队长L=9(人);平均队列长L。=6.75(人)。相比之下(见表8-2)，排1队共享3个服务台效率好。须注意，本例②限制不准串队，这是理论研究的要求，在实践中，若允许在保持各排队顺序的前提下串队，实际效率相差不会这样大，但是差距肯定会有的。

2)M/M/s/N/∞系统此系统的主要参数为服务台数目为s，顾客的平均到达率(单位时间到达的顾客数)λ,平均服务率(单位时间服务的顾客数)μ,服务强度为ρ=λ/sμ,系统容量(队长)有限为N。状态转移速度图如图8-16所示。上一页下一页返回8.3泊松输入—指数服务排队模型稳态概率方程:根据上面的分析，可得当n<s时， ；当N≥n≥s时，于是根据概率性质 ，把式(8一18)代入，即得到上一页下一页返回8.3泊松输入—指数服务排队模型同单服务台的分析，这里也有 ，可以推出利用李特尔(Little)公式求出其他三个量L、W、Wa为在这类排队系统中，损失率指标与单服务台的情况是相同的:上一页下一页返回8.3泊松输入—指数服务排队模型

例8.6某街口汽车加油站可同时为2辆汽车加油，同时还可容纳3辆汽车等待，超过此限则不能等待而自动离去。汽车到达间隔与加油时间均为指数分布，平均每小时到达16辆，平均加油时间为每辆6分钟。求每辆汽车的平均逗留时间。解这是一个M/M/s/N系统，由题意知

(辆/小时)μ=60/10=6(辆/小时),则上一页下一页返回8.3泊松输入—指数服务排队模型也可以用定义直接计算:平均有效到达率利用李特尔(Little)公式求出其他三个量L、W、Wa：即每辆汽车平均逗留9分钟。

3)损失制M/M/s/s

顾客到达时若服务台被占用则顾客立即离开，此即M/M/s/N中N=s的情形。于是，稳态概率方程为上一页下一页返回8.3泊松输入—指数服务排队模型根据概率性质 ，即得到利用李特尔(Little)公式求出其他两个量L、W：上一页下一页返回8.3泊松输入—指数服务排队模型8.3.3有限源排队系统(M/M/s/m/m)

该系统的顾客源数为m，故称为有限源系统。由于顾客源是m个，那么系统容量实质上最多有m个。构成此系统的典型情况有:s名电工共同负责m台机器的维修;m个车工共同使用s个电动砂轮;m个人员共同使用s个计算机终端;一家几口人共同使用一个卫生间，等等。下面以第1种情况为例加以说明。在这种情况下，顾客源即m台机器，机器发生故障表示顾客到达，s名电工即服务台。由于故障机器修好后，经过一段时间的运转还会发生故障，因此该排队系统具有如图8-17所示的有限源排队系统结构形式。上一页下一页返回8.3泊松输入—指数服务排队模型

假定:①m台机器质量相同，每台机器连续运转时间相互独立且都服从参数为λ的指数分布。每台机器平均连续运转时间为(1/λ)，而λ则是一台机器在单位运转时间内发生故障的平均次数。②、个工人技术程度相同，每人对机器的修复时间相互独立，每台机器的修复时间都服从参数为μ的指数分布。工人修复每台机器的平均时间为(1/μ)

，而μ则是一个工人在单位时间内修复的机器的台次。③机器的正常运转与修理状态相互独立，修复的机器具有与新机器相同的质量。对于s=1和s>1，计算方面有些差异，下面分别讨论。

(1)M/M/1/tn/tn系统状态转移速度图如图8-18所示。上一页下一页返回8.3泊松输入—指数服务排队模型

此系统的输入(即机器发生故障情况)为，顾客源中剩余的顾客数(运转的机器数)乘以每个顾客到达(每台机器发生故障)的概率。由此得到稳态概率方程:根据概率性质 ,把式(8-20)代入，即 ,记 ，得到注意，由定义上一页下一页返回8.3泊松输入—指数服务排队模型又得到利用李特尔(Little)公式求出其他三个量L、W、Wa：例8.7一个工人负责照管6台自动机床，当机床需要加料、发生故障或刀具磨损时就自动停车，等待工人维护。设每台机床平均每小时停车一次，每次工人维护的平均时间为0.1小时，间隔时间均服从负指数分布。试分析该系统运行情况。解由题意知，这是一个M/M/1/6/6系统，有上一页下一页返回8.3泊松输入—指数服务排队模型工人空闲的概率停车的机床(包括正在维护和等待维护)的平均数为上一页下一页返回8.3泊松输入—指数服务排队模型利用李特尔(Little)公式求出其他三个量L、W、Wa：因此，等待维护的机床平均数:La=0.3295(台)

平均停车时间:W=9.83(分钟)平均等待时间:生产损失率(即停车机床所占比例):机床利用率:上一页下一页返回8.3泊松输入—指数服务排队模型(2)M/M/s/m/m系统状态转移速度图如图8-19所示。此系统的输入、输出同前面有关论述，这里不再讨论。由图8-19得到稳态概率方程:仍记ρ=λ/μ,当n<s时当n≥s时,根据概率性质 ，代入上两式中，即得到上一页下一页返回8.3泊松输入—指数服务排队模型注意，由定义又 ，可求出L及λe。再进一步利用李特尔

(Little)公式求出其他其他三个量L、W、Wa：例8.8若将例8.6改为由3个技术程度相同的工人共同照管20台自动机床，其他数据不变，试分析此时系统的运行情况，并与例8.6进行比较。解由题意知，这是一个M/M/3/20/20系统，有s=3，m=20，λ=1(台/小时)，μ=10(台/小时)，ρ=0.1上一页下一页返回8.3泊松输入—指数服务排队模型机床全好率(即20台机床全部同时正常运转的概率)为为了计算四项主要工作指标，先要按下式分别算出p1,p2,…,p20。通过计算知道p12=0.00007，而当n≥13时，Pn<0.5×10-5，故可忽略不计。于是上一页下一页返回8.3泊松输入—指数服务排队模型工人平均空闲时间(即单位时间内平均每人空闲的时间)为上一页下一页返回8.3泊松输入—指数服务排队模型而单台系统的该项指标即p0。例8.7、例8.8各项指标的比较，见表8-3。由此可见，协作共管优于个人承包，虽然照管的台数增加了(平均每人增加0.6)台，利用率反而提高了，但每个工人的空闲时间相应地减少了。上一页下一页返回8.3泊松输入—指数服务排队模型思考题

(1)分析单服务台无限源排队系统状态转移:吏度图转入、转出:吏率的特点;讨论单服务台无限源排队系统各模型及其计算过程的异同点。

(2)分析多服务台无限源排队系统状态转移:吏度图转入、转出:吏率的特点;讨论多服务台无限源排队系统各模型及其计算过程的异同点。

(3)分析有限源排队系统状态转移:吏度图转入、转出:吏率的特点;讨论有限源排队系统各模型及其计算过程的异同点。

(4)小结各排队系统模型求解中的共同点和不同点(转入速率与顾客源有关、转出:吏率与服务台数量有关、单服务台先计算平均队长、多服务台先计算平均队列长等。上一页返回下一页8.4其他模型选介8.4.1M/G/1排队系统我们讨论具有泊松输入、一般独立服务的单服务台系统的排队模型。设顾客的平均到达率为λ，任一顾客的服务时间为随机变量V，且有那么，服务强度为ρ=λ/μ可以证明，不论v服从什么分布，只要ρ<1，系统就能达到稳态，并有稳态概率从而根据波拉切克(Pollaczek)——欣钦(Khintchine)公式可以导出下一页返回上一页8.4其他模型选介对于ρ<1，李特尔(Little)公式成立。这时λ

e=λ(系统的容量无限制)，于是可以求出其他三个量L、W、Wa：例8.9某储蓄所有一个服务窗口，顾客按泊松分布平均每小时到达10人。为任一顾客办理存款、取款等业务的时间V(小时)~N(0.05,0.012）。试求，该储蓄所空闲的概率及其主要工作指标。解由题意知上一页