计算机系统建模与分析排队论

计算机系统的建模与分析一、排队论及其应用二、PetriNets及其应用排队论及其应用内容框架输入过程排队规则服务台排队系统分类符号表示研究方式典型模型及其应用系统意义画状态转移速度图写状态转移速度矩阵给出状态概率方程计算基本数量指标应用举例排队论排队论(QueuingTheory)：又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计（静态）和最优控制（动态）问题。排队论所讨论的是一个系统对一群体提供某种服务时该群体占用此服务系统时所呈现的状态。在界定排队问题中，必须交代清楚的事项包括：

1．群体到达系统的情况；

2．系统对群体中各个部分提供服务时花费的时间长短；

3．系统提供服务的先后次序；

到达系统的个体称作“顾客”;提供服务的系统可由一个或者一个以上的“服务台”组成;“服务时间”相当于顾客占用服务台的时间;而服务台对顾客们提供服务的次序则称作“排队规则”。服务系统的状态通常是以顾客留在服务系统上的数量来表示，这个数量称作“队列长度”或者简称为“队长”;有时也以顾客停留在系统上的时间表示，这段时间称作“等待时间”。等待时间由两个部份组成，其一为顾客等候使用服务台的“延误时间”,其二为占用服务台的时间，即服务时间。排队论的一些应用问题1、通讯问题电话交换机通常仅有有限条电话线以沟通音汛如果在某一时刻所有的电话线均被占用，那么新的使用要求就必须等到有一条线空下来时方能满足，这时电话线的使用要求是排队问题电话线为服务台，而占用电话线的时间为服务时间，而一般使用电话线的排列规则为“先到先占”．

2、公共服务问题许多公共服务事业对群众提供服务的水平，或者公共服务设施的使用情况也可纳入排队问题。例如银行的服务人员，邮局的服务员，医院的病床，饭店的座位等可当作服务台，服务时间以及到达顾客则与实际的情形完全一致一般来说排队规则均为先到先占．但是在某些情形下也可以有优先权的出现，例如病危的患者可以有优先占用病床的权利．3、救护、公安系统警察，消防人员，消防车，医院救护车均可当作服务台，紧急事故的发生相当于顾客的到达，通常这类问题都要求极低的服务台使用率，因而当一件紧急事故发生后有足够的应付能力(至少有一个服务台可以立即使用)．4、存量问题储存系统中存量的变化的随机行为和排队论中的队列长度变化的随机行为有相似的地方。例如，零售商店货柜上的商品，图书馆的藏书，水库的存水量都可视作队长，卖出的商品，借出的书籍，放水灌溉或发电可视作顾客的离去，而进货、还书、由下雨或河水引入增加贮水量则为顾客到达。5、交通问题港口的码头是服务台，船只为顾客。码头的使用决定了港口的吞吐量。飞机跑道或者停机坪可以作为服务台，飞机起降为顾客的服务要求，如何安排飞机班次便利旅客并使飞机起降依次不紊是机场调度的重要问题。

6、生产线问题在工厂生产线上，机器、工人甚至物料运输设备如何安排以保证生产率的水平，降低生产过程中原料和半成品的存量往往也可通过排队问题的研究获得解决．在这类问题里，产品为顾客，机器、工人或者有关生产、运输设备为服务台．7、计算机配置问题在计算机内部中央处理机，输入输出设备可当作服务台，计算程序为顾客．在计算机网络问题里计算机本身可以当作服务台，计算机程序或指令通过网络可由一个计算机传送至另一计算机，这类问题通常都以网络队列形式出现．排队论的起源与发展排队论起源于20世纪初的电话通话，20世纪初Bell电话公司为减少电话呼叫，研究电话线路合理配置问题。1909—1920年丹麦数学家、电气工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。他发表了开创性论文“概率论和电话通讯理论”。排队论的起源与发展20世纪30年代中期，当费勒(W.Feller)引进了生灭过程时，排队论才被数学界承认为一门重要的学科。20世纪50年代初，堪道尔(D.G.Kendall)对排队论作了系统的研究，他用嵌入马尔柯夫(A.A.Markov)链方法研究排队论，使排队论得到了进一步的发展。从20世纪60年代起，主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究。D.G.Kendall排队问题的界定要说明一个排队问题必须了解顾客到达的过程、服务时间、排队规则以及服务系统的结构。到达过程通常可用两个连续到达时刻的间隔或简称为“到达间隔”来表示。单位时间内平均到达的个数称为“到达率”，其值等于平均到达间隔的倒数．到达过程的形式可以是下列任何一种．1、规则到达也就是每隔一固定的时间就有一个顾客到达。例如，在自动化生产线上，有时进料问题可以是这种形式的到达过程。2、完全随机到达又称泊松到达过程。到达间隔为指数分布，各个间隔为相同分布而互相独立的随机变量，这种形式具有的特性往往使得数学推演极为简单，同时在应用方面也颇符合实际，因此也是最为普遍采用的形式。完全随机的假设是基于在任何时刻一个到达发生的机会完全相同，而两个或两个以上的到达同时发生的可能性却极低。3、一般相同而独立的到达或称更新到达过程。这类形式比之第二类较具一般性，各个到达时间为相互独立、相同分布的随机变数，但是不一定是指数分布。在正常情形下，机器的故障发生常常用这类假设，连续两次故障间隔即为一到达间隔。4、成批到达在实例中却不乏成批到达的情形。工厂、商店进货通常总是一次到达许多件。有时虽然一次仅有一个顾客到达。但是在极短的时间内有多个到达时也可以成批到达视之。(譬如连环车祸，一部车子为一个到达，车祸可能在短期内连续出现)。至于到达的批量可以为常数，也可以是随机变量。5、非平稳到达在某些情形下，到达频率可以因时而异。最常见的实例是交通问题和电话通讯问题。上下班时车辆拥挤，而上班时间电话使用频率也较高。6、依态到达到达频率也可以因服务系统的状态而定．例如：高朋满座的地方也会使人不耐久候而转往他家，在这些情况下，到达率都和队列长度有关。有时也因延误时间长短而定，高明满座的饭店如果座位极多，那么懂得排队论概念的人就知道饭店的队列虽久但是因为服务台(座位)多，那么延误时间就会比较短，只须稍候片刻就极可能挨到座位。7、连续到达在有些排队问题里(如水库管理)到达却是一个连续变数，有时为了方便起见我们也可以把离散的假定为连续到达以简化计算或推演求解，明显的例子是大都市车辆在马路上川流不息，由于数量庞大有时可当作流体来处理．服务时间的类别也有多种，通常是以服务时间长度的分布来表示。平均服务时间的倒数称作“服务率”，也可视作服务台在被占用期间，单位时间内可以完成服务的平均次数。到达率与服务串之间的关系是度量服务系统负荷量的重要指标．

1．常数

2．指数分布

3．爱尔兰分布

4．超指数分布

5．库克斯类分布

6．依剩余服务时间随机变化而界定的分布第一类是指服务时间永远不变，第三、四类都具有指数分布的某些共同特性，在计算上较为简单，第五类是一般化的分布但是可以用许多指数随机变数的随机组合来表示，第六类主要用于队列上下界限的研究，第五、六两类都不具有特定的数学式子，而代表一群或一类的分布．排队系统的特征及其组成排队系统的特征即拥挤现象的共性：有请求服务的人或物，即顾客；有提供服务的人或物，即服务员或服务台；具有随机性，即各种排队系统中，顾客相继到达的时间间隔以及对每一位顾客服务的时间是随机的。随机性是排队系统的一个重要特征。排队系统的基本组成一般的排队系统，都可由下图加以描述。排队系统排队系统的基本组成部分通常，排队系统都有输入过程、服务规则和服务台等3个组成部分：

输入过程：这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述一个输入过程。

顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到医院看病的病人可以认为是无限的，而某个工厂因故障待修的机床则是有限的。顾客到达方式：这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。

顾客流的概率分布，或称相继顾客到达的时间间隔的分布：这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。2.服务规则:这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。

(1)损失制:这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统,永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。(2)等待制：这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：

①先到先服务(FCFS,FirstComeFirstServe)：按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务(LCFS,LastComeFirstServe)：仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。③随机服务（SIRO，SeverInRandomOrder）：即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。

④优先权服务(PR,Preference)：如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。(3)混合制（Losingsystemandwaitingsystem）：这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限:当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。②等待时间有限:即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。

不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。服务机构（服务台）3．服务台情况：服务台可以从以下3方面来描述：

(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：

①单队——单服务台式；②单队——多服务台并联式；③多队——多服务台并联式；④单队——多服务台串联式；⑤单队——多服务台并串联混合式,以及多队——多服务台并串联混合式等等。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。单一服务台单队列系统这个系统仅有一个服务台，如下图所示，方块代表服务台，圆圈代表顾客，箭头表示顾客流动的方向。图1单队单台排队系统多服务台（并联）单队列系统数个完全相同的服务台(假定为N个)，到达的顾客可以使用其中任何一个服务台．如果到达者只排一个队列(如下图所示)，那么在服务台全被占满时，该服务系统的排队情形就近似于单一服务台系统，如果每个服务台的服务率为，队列的随机行为接近单一服务台以服务率为n

的随机行为。图2单队列——S个服务台并联的排队系统多服务台多队列系统假设到达者被依次安排去不同的服务台，那么服务系统就有n个队列，每个队列的随机行为相同，整个服务系统就如同n个单一服务台系统，如果到达率为

，则每个单一服务台的到达率就是

／n

．若每个服务台有自己的队列，同时顾客可以自由移换到较短的队列上，那么就队列长度的变化而言，这种排队方式与单一队列没有什么区别．图3S个队列——S个服务台的并联排队系统多服务台（串联）单队列系统图4多服务台串联排队系统多服务台混合结构这种结构应用于多服务项目的大型系统。如在大型医院的健康体检项目中，每个体检项目有多位医生提供服务，不同项目的服务需要排队等待。图5多队——多服务台混联、网络系统(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。排队系统的描述符号与分类为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（D．G．Kendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F

各符号的意义为：Kendall记号A：表示顾客相继到达间隔时间分布，常用下列符号：M：表示到达过程为泊松过程或负指数分布；D：表示定长输入；Ek：表示k阶爱尔朗分布；G：表示一般相互独立的随机分布；Geo：表示几何分布；Kendall记号B：表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M：表示服务过程为泊松过程或负指数分布；D：表示定长分布；Ek

：表示k阶爱尔朗分布；G：表示一般相互独立的随机分布；Geo：表示几何分布；Kendall记号C：表示服务台(员)个数：“1”则表示单个服务台，“s”。(s＞1)表示多个服务台。D：表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则0<K<∞，当K=0时，说明系统不允许等待，即为损失制。K=∞时为等待制系统，此时∞般省略不写。K为有限整数时，表示为混合制系统。E：表示顾客源限额，分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。Kendall记号F：表示服务规则，常用下列符号：

FCFS：表示先到先服务的排队规则；

LCFS：表示后到先服务的排队规则；

PR：表示优先权服务的排队规则。例如：某排队问题为M／M／S／∞／∞／FCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。Kendall记号可以将Kendall记号的含义简记为：到达间隔/服务时间/服务台数/系统容量/顾客源数/服务规则在Kendall记号中，一般约定如下：如果服务规则为先到先服务，则可以省略最后一项；如果顾客源数为∞，服务规则为先到先服务则可以省略最后两项；如果系统容量与顾客源数均为∞，服务规则为先到先服务则可以省略最后三项；例子1、M／M／1／∞／∞／FCFS表示泊松输入，服务时间服从负指数分布、1个服务台、系统容量无限制、顾客源无限的先到先服务的排队系统。2、G／EK／1／N／∞／FCFS表示顾客到达的时间服从一般独立分布、服务时间服从K阶爱尔朗分布、1个服务台、系统容量为N、顾客源无限的先到先服务的排队系统。习题试解释以下排队系统的含义。1、M/M/12、M/M/53、M/G/34、M/G/1/m/N5、Geo/Ek/S/m/N/LCFS解答1、M/M/1顾客到达系统的时间间隔与服务时间均服从负指数分布，服务台数量为1；系统容量和顾客源数量无限制；服务规则为先到先服务；2、M/M/5顾客到达系统的时间间隔与服务时间均服从负指数分布，服务台数量为5；系统容量和顾客源数量无限制；服务规则为先到先服务；3、M/G/3顾客到达系统的时间间隔服从负指数分布，对顾客的服务时间服从一般分布，服务台数量为3；系统容量和顾客源数量无限制；服务规则为先到先服务；4、M/G/1/m/N顾客到达系统的时间间隔服从负指数分布，对顾客的服务时间服从一般分布，服务台数量为1；系统容量限制为m；顾客源数量限制为N；服务规则为先到先服务；5、Geo/Ek/S/m/N/LCFS顾客到达系统的时间间隔服从几何分布，对顾客的服务时间服从K阶爱尔朗分布，服务台数量为S；系统容量限制为m；顾客源数量限制为N；服务规则为后到先服务；排队系统研究的问题1、排队系统的数量指标（特征量）研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：特征量平均到达率：单位时间内到达系统的顾客数的平均值，即单位时间内顾客的平均到达率，记作，而1/表示相邻两个顾客到达的平均间隔时间。平均服务率：单位时间内一个服务台能够服务完的平均顾客数，记作，而1/表示每个顾客的平均服务时间；恰有n个顾客的概率：在时刻t系统中恰有n个顾客的概率pn(t)，显然p0(t)为系统空闲概率。特征量队长和队列长

队长是指系统中的平均顾客数，即排队等待的顾客数与正在接受服务的顾客数之和；

等待队长（或队列长）是指系统中正在排队等待服务的平均顾客数。队长和等待队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值。特征量队长的分布是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而可以改变服务方式，确定合理的等待空间。特征量等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量，也是顾客最关心的指标，因为顾客通常希望等待时间越短越好。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量，同样为顾客非常关心。对这两个指标的研究当然是希望能确定它们的分布，或至少能知道顾客的平均等待时间和平均逗留时间。从服务机构的角度来看，还关心以下指标：绝对通过能力A：单位时间内被服务完顾客的平均值；系统的相对通过能力Q：单位时间内被服务完顾客数与请求服务顾客数之比；忙期是指从顾客到达空闲着的服务台起，到服务台再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，可以表征服务台的服务强度。特征量闲期：即服务台连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的；K阶繁忙期：对于有n个服务台的系统，从系统中开始有K个顾客在等待服务时起一直到有一个服务台空闲时为止这段时间称为系统的K阶繁忙期，零阶繁忙期又称繁忙期。损失率：对于损失制的排队系统中，系统满员概率称为系统的损失率。

一些数量指标的常用记号(1)主要数量指标平均队长L或Ls：即稳态系统中正在接受服务与排队等待服务的顾客总数的期望值；平均等待队长Lq：即稳态系统中排队等待服务的顾客数的期望值；平均逗留时间W或Ws：即顾客在系统中排队等待服务的时间与接受服务的时间之和的期望值；平均等待时间Wq：即顾客在系统中等待服务时间的期望值。其他常用数量指标：单位时间内达到系统的平均顾客数（平均到达率）；e:单位时间内达到并进入系统的平均顾客数（有效平均到达率），在等待制系统中有＝e：单位时间内一个服务台能够服务完的平均顾客数（平均服务率）；基本关系式1L=Lq+S该式揭示了指标L与Lq之间的数量关系，式中S是平均忙的服务台数，即正在接受服务的平均顾客数。该式的物理意义是：平均逗留队长是平均等待队长与正在接受服务的平均顾客数之和。S的计算方法：因为排队系统达到稳态时，单位时间内到达并进入系统的平均顾客数e

等于单位时间内接受服务完毕离开系统的平均顾客数S*，即有e

＝S*故S=e/基本关系式2W=Wq+V该式揭示了指标W与Wq之间的数量关系，式中V是对每个顾客的平均服务时间。该式的物理意义是：平均逗留时间是平均等待时间与对每个顾客的平均服务时间之和。V的计算方法：因为每个服务台的平均服务率为故V=1/基本关系式3L=e

W该式揭示了指标L与W之间的数量关系。该式的物理意义是：平均队长等于单位时间内到达并进入系统的平均顾客数乘以平均逗留时间，即等于平均逗留时间内进入系统的总的平均顾客数。基本关系式4Lq=e

Wq该式揭示了指标Lq与Wq之间的数量关系。该式的物理意义是：平均等待队长等于单位时间内到达并进入系统的平均顾客数乘以平均等待时间，即等于平均等待时间内进入系统的总的平均顾客数。Little公式公式L=e

W与公式Lq=e

Wq统称为Little公式。其形式类似于公式“距离＝速度×时间”，它是排队论中的一个著名公式，适用于存在稳态分布的任何排队系统。Little公式揭示了排队系统中四个基本性能指标L与W、Lq与Wq之间的数量关系。为了求得排队系统的各项稳态性能指标，必须先计算出稳态时系统中有j个顾客的概率Pj例子例1：一个步兵排平均有30名战士，每个战士平均在该排服役三年，则L＝30，W＝3，那么

＝30／3＝10，即平均每年有10个新人加入该排，也平均有10人退役转业或调职他处。例2：一个工人在工作台边操作车床，如果平均有10件工作在工作台和车床上，每小时有4件工作进入工作台，那么每件工作平均要等W＝L／

＝10／4＝2.5小时才能完成。排队问题中常见的事件流（第2次课）将同类事件一个（批）个（批）随机地来到服务窗口要求服务的序列称作事件流。如电话局接到的呼唤流、计算机出现的故障流、进站的汽车流、看病的人流、去某公司应聘考试的考生流等均是事件流。显然，这些事件流均为随机变量，由于顾客（用户）到达系统的间隔时间与服务时间均为非负，故它们还是非负的随机变量。常用的有下述几个分布：

1、二项分布每次试验成功的概率都是p，失败的概率都是q=1-p.这样的n次独立重复试验称作n重贝努里试验，简称贝努里试验或贝努里概型.用X表示n重贝努里试验中事件A（成功）出现的次数，则称随机变量X服从参数为n和p的二项分布，记作X~B(n,p)注:

贝努里概型对试验结果没有等可能的要求，但有下述要求：（1）每次试验条件相同；二项分布描述的是n重贝努里试验中出现“成功”次数X的概率分布.（2）每次试验只考虑两个互逆结果A或，且P(A)=p

，；（3）各次试验相互独立.2、泊松流又称最简单事件流。它具有如下特点：（1）平稳性。在任何一段长度为t的时间区间内，出现任意数量事件的概率只与t有关，而与t所处的位置（或与起始时刻）无关。记为平稳流的强度。

(2)无后效性（又称无记忆性或马氏性）。在互不相交的两时间区间内所出现的事件数是相互独立的。如到商店购物的顾客，待修的机器，进站的列车等均具有无后效性。

(3）普通性。在同一瞬间，多于一个事件出现的概率（或同时到达系统有两个或两个以上顾客的概率）可忽略不计。设随机变量X所有可能取的值为0,1,2,…,且概率分布为：其中>0是常数,则称X服从参数为的泊松分布,记作X~P().易见例

某一无线寻呼台,每分钟收到寻呼的次数X服从参数=3的泊松分布.

求:(1)一分钟内恰好收到3次寻的概率.(2)一分钟内收到2至5次寻呼的概率.解:

(1)P{X=3}=p(3;3)=(33/3!)e-3≈0.2240(2)P{2≤X≤5}=P{X=2}+P{X=3}+P{X=4}+P{X=5}=[(32/2!)+(33/3!)+(34/4!)+(35/5!)]e-3≈0.7169历史上，泊松分布是作为二项分布的近似，于1837年由法国数学家泊松引入的.二项分布与泊松分布命题对于二项分布B(n,p),当n充分大,p又很小时,则对任意固定的非负整数k,有近似公式负指数分布当顾客流为泊松流时，用T表示两个相继顾客到达系统的时间间隔，记其分布函数为由于故有相应的分布密度为：它就是负指数分布的密度函数。易知：E(T)=1/D(T)=1/2通常，服务窗为一顾客服务所需的时间的分布函数与分布密度为其中参数为单位时间内服务窗所完成服务的顾客均值数，且有4、爱尔兰分布考察最简单的事件流，记各事件到达系统的时间间隔序列为，且它们是同负指数分布的随机变量序列，，如下图所示。及拉氏变换的性质得到再查反拉氏变换表知并且指数分布若随机变量X具有概率密度则称X

服从参数为的指数分布常简记为X~E().输入过程和服务时间分布一、输入过程由前所述，输入过程是描述各种类型的顾客以怎样的规律到达系统，一般用相继两顾客到达时间间隔来描述系统输入特征。主要输入过程有：

1．定长输入。这是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为：例如，生产自动线上产品从传送带上进入包装箱就是这种情况．2．泊松(poisson)输入，又称最简单流。满足下面3个条件的输入称之为最简单流。

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

设初始条件为,且有(2)无后效性。指在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响，否则就是关联的。(3)单个性又称普通性。指在充分小的时段内最多到达一个顾客。因为泊松流实际应用最广，也最容易处理，因而研究得也较多．可以证明，对于泊松流，在长度为t的时间内到达K个顾客的概率vk(t)服从泊松分布，即其中参数>0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。对于泊松流，不难证明其相继顾客到达时间间隔i，i=1,2,…是相互独立同分布的，其分布函数为负指数分布：泊松(poisson)输入在排队论中的意义：实际问题中最常见；数字处理简单；当实际流与泊松流有较大出入时，经过一定的变换，结果也可以达到一定的精度。负指数分布负指数分布是排队论中最常用、最重要的一种分布。它既能代表某些达到间隔的分布，也能代表某些服务时间的分布。若随机变量t的概率密度为式中常数

>0，则称T服从参数为的负指数分布，其数学期望E(T)=1/

，方差D(T)=1/

2。E(T)表示顾客相继到达时的平均间隔时间。以上负指数分布是描述输入情况的，随机变量是到达间隔，若将上式中的换成，则变为描述服务时间的参数为的负指数分布。泊松过程与负指数分布的关系：定理：随机过程{M(t),t>=0}是强度为的泊松过程的充分必要条件是：顾客相继到达的时间间隔{τk，k=1,2,3…}相互独立，且服从参数为的负指数分布。爱尔朗输入.这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为

其中k为非负整数。可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为：则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：例某排队系统有并联的k个服务台，顾客流为泊松流，规定第i,K+i,2K+i…个顾客排入第i号台(i=1,2,…,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。此外，爱尔朗分布中，当K＝1时将化为负指数分布。4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为：到达时间间隔可能是上述几类输入中的一种。服务时间分布1．定长分布。每一个顾客的服务时间都是常数，此时服务时间t的分布函数为：

2．负指数分布。即各个顾客的服务时间相互独立，具有相同的负指数分布：

其中>0为一常数，服务时间t的数学期望称为平均服务时间。服务时间分布3.爱尔朗分布.即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为

其中>0为一常数，此种的平均服务时间为：

K=1时爱尔朗分布化归为负指数分布当K→∞时，得到长度为1/的定长服务。4、一般服务分布。所有顾客的服务时间都是相互独立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。5、多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类型不同6、服务时间依赖于队长的情况。指服务员排队的人愈多，服务的速度也就愈快。服务时间分布复习1、排队系统的组成2、排队系统的描述符号3、排队系统的特征量排队系统的组成一般的排队系统，都可由下图加以描述。排队系统排队系统的组成排队系统由输入过程、服务规则和服务台3个组成部分：

输入过程：这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述一个输入过程。

顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。顾客到达方式：这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。顾客流的概率分布，或称相继顾客到达的时间间隔的分布：这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。2.服务规则:这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。

(1)损失制:这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统,永不再来。(2)等待制：这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：

①先到先服务(FCFS,FirstComeFirstServe)：按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务(LCFS,LastComeFirstServe)：仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。③随机服务（SIRO，SeverInRandomOrder）：即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。

④优先权服务(PR,Preference)：如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。(3)混合制（Losingsystemandwaitingsystem）：这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限:当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。②等待时间有限:即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。③逗留时间(等待时间与服务时间之和)有限。

损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。服务机构（服务台）3．服务台情况：服务台可以从以下3方面来描述：

(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：

①单队——单服务台式；②单队——多服务台并联式；③多队——多服务台并联式；④单队——多服务台串联式；⑤单队——多服务台并串联混合式,以及多队——多服务台并串联混合式等等。单一服务台单队列系统这个系统仅有一个服务台，如下图所示，方块代表服务台，圆圈代表顾客，箭头表示顾客流动的方向。图1单队单台排队系统多服务台（并联）单队列系统数个完全相同的服务台(假定为N个)，到达的顾客可以使用其中任何一个服务台．如果到达者只排一个队列(如下图所示)，那么在服务台全被占满时，该服务系统的排队情形就近似于单一服务台系统，如果每个服务台的服务率为，队列的随机行为接近单一服务台以服务率为n

的随机行为。图2单队列——S个服务台并联的排队系统多服务台多队列系统假设到达者被依次安排去不同的服务台，那么服务系统就有n个队列，每个队列的随机行为相同，整个服务系统就如同n个单一服务台系统，如果到达率为

，则每个单一服务台的到达率就是

／n

．若每个服务台有自己的队列，同时顾客可以自由移换到较短的队列上，那么就队列长度的变化而言，这种排队方式与单一队列没有什么区别．图3S个队列——S个服务台的并联排队系统多服务台（串联）单队列系统图4多服务台串联排队系统多服务台混合结构这种结构应用于多服务项目的大型系统。如在大型医院的健康体检项目中，每个体检项目有多位医生提供服务，不同项目的服务需要排队等待。图5多队——多服务台混联、网络系统(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。排队系统的描述符号为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（D．G．Kendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F

各符号的意义为：Kendall记号A：表示顾客相继到达间隔时间分布，常用下列符号：M：表示到达过程为泊松过程或负指数分布；D：表示定长输入；Ek：表示k阶爱尔朗分布；G：表示一般相互独立的随机分布；Geo：表示几何分布；Kendall记号B：表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M：表示服务过程为泊松过程或负指数分布；D：表示定长分布；Ek

：表示k阶爱尔朗分布；G：表示一般相互独立的随机分布；Geo：表示几何分布；Kendall记号C：表示服务台(员)个数：“1”则表示单个服务台，“s”。(s＞1)表示多个服务台。D：表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则0<K<∞，当K=0时，说明系统不允许等待，即为损失制。K=∞时为等待制系统，此时∞般省略不写。K为有限整数时，表示为混合制系统。E：表示顾客源限额，分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。Kendall记号F：表示服务规则，常用下列符号：

FCFS：表示先到先服务的排队规则；

LCFS：表示后到先服务的排队规则；

PR：表示优先权服务的排队规则。例如：某排队问题为M／M／S／∞／∞／FCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。Kendall记号可以将Kendall记号的含义简记为：到达间隔/服务时间/服务台数/系统容量/顾客源数/服务规则在Kendall记号中，一般约定如下：如果服务规则为先到先服务，则可以省略最后一项；如果顾客源数为∞，服务规则为先到先服务则可以省略最后两项；如果系统容量与顾客源数均为∞，服务规则为先到先服务则可以省略最后三项；例子1、M／M／1／∞／∞／FCFS表示泊松输入，服务时间服从负指数分布、1个服务台、系统容量无限制、顾客源无限的先到先服务的排队系统。2、G／EK／1／N／∞／FCFS表示顾客到达的时间服从一般独立分布、服务时间服从K阶爱尔朗分布、1个服务台、系统容量为N、顾客源无限的先到先服务的排队系统。排队系统的特征量(1)主要数量指标平均队长L或Ls：即稳态系统中正在接受服务与排队等待服务的顾客总数的期望值；平均等待队长Lq：即稳态系统中排队等待服务的顾客数的期望值；平均逗留时间W或Ws：即顾客在系统中排队等待服务的时间与接受服务的时间之和的期望值；平均等待时间Wq：即顾客在系统中等待服务时间的期望值。其他常用数量指标：单位时间内达到系统的平均顾客数（平均到达率）；e:单位时间内达到并进入系统的平均顾客数（有效平均到达率），在等待制系统中有＝e：单位时间内一个服务台能够服务完的平均顾客数（平均服务率）；基本关系式1L=Lq+S该式揭示了指标L与Lq之间的数量关系，式中S是平均忙的服务台数，即正在接受服务的平均顾客数。该式的物理意义是：平均逗留队长是平均等待队长与正在接受服务的平均顾客数之和。S的计算方法：因为排队系统达到稳态时，单位时间内到达并进入系统的平均顾客数e

等于单位时间内接受服务完毕离开系统的平均顾客数S*，即有e

＝S*故S=e/基本关系式2W=Wq+V该式揭示了指标W与Wq之间的数量关系，式中V是对每个顾客的平均服务时间。该式的物理意义是：平均逗留时间是平均等待时间与对每个顾客的平均服务时间之和。V的计算方法：因为每个服务台的平均服务率为故V=1/基本关系式3L=e

W该式揭示了指标L与W之间的数量关系。该式的物理意义是：平均队长等于单位时间内到达并进入系统的平均顾客数乘以平均逗留时间，即等于平均逗留时间内进入系统的总的平均顾客数。基本关系式4Lq=e

Wq该式揭示了指标Lq与Wq之间的数量关系。该式的物理意义是：平均等待队长等于单位时间内到达并进入系统的平均顾客数乘以平均等待时间，即等于平均等待时间内进入系统的总的平均顾客数。Little公式公式L=e

W与公式Lq=e

Wq统称为Little公式。其形式类似于公式“距离＝速度×时间”，它是排队论中的一个著名公式，适用于存在稳态分布的任何排队系统。Little公式揭示了排队系统中四个基本性能指标L与W、Lq与Wq之间的数量关系。为了求得排队系统的各项稳态性能指标，必须先计算出稳态时系统中有j个顾客的概率PjM/M/1/N/∞/FCFS1、系统意义顾客按照泊松流输入，平均到达率为；服务时间服从负指数分布，平均服务率为；1个服务台；系统容量为N，顾客源无限，排队规则为先到先服务的混合制排队系统；当顾客来到系统时，若系统中的顾客已经等于N，则离去M/M/1/N/∞/FCFS2、状态转移速度图1）系统状态：系统中的顾客数2）状态转移速度图用圆圈表示状态符号，箭头表示从一个状态到另一个状态的转移。0N-112N-2λλλλμμμμNM/M/1/N/∞/FCFS3）写出状态转移速度矩阵，进而写出系统稳态条件下的状态概率平衡方程（简称状态概率方程）注意：状态转移速度矩阵的特点是每一行元素之和等于0M/M/1/N/∞/FCFS状态概率方程PA=0其中：P=(P0,P1,P2,P3,……Pn)M/M/1/N/∞/FCFS把状态概率方程打开，写出状态概率方程组即可求出基本概率指标。1、基本概率指标PA=0第一项：－λP0＋μP1＝0P1＝(λ/μ)P0第二项：λP0－（μ＋λ）P1＋μP2＝0P2＝(λ/μ)2P0M/M/1/N/∞/FCFS依此类推：Pn＝(λ/μ)nP01≤n≤N如何求P0呢？代入（P0+P1+…+Pn)=1故有（P0＋(λ/μ)P0+…+(λ/μ)nP0）＝1P0（1＋(λ/μ)+…+(λ/μ)n）＝1于是：P0＝1/(1＋(λ/μ)+…+(λ/μ)n)当λ＝μ时P0＝1/(N+1)当λ≠μ时P0＝（1－λ/μ）/(1－(λ/μ)N+1)M/M/1/N/∞/FCFSPn＝(λ/μ)np0故当λ＝μ时Pn＝1/(N+1)当λ≠μ时Pn＝（1－λ/μ）/(1－(λ/μ)N+1)(λ/μ)nM/M/1/N/∞/FCFS得到系统状态概率方程组的第二种方法：当系统处于稳态时，对每个状态来说，转入率应等于转出率。根据这个结果即可获得系统稳态条件下的状态概率方程，进一步即可计算稳态系统的各项运行数量指标。当系统状态为0时，有λP0＝μP1故P1＝(λ/μ)P0当系统状态n≥1时，有λPn-1+μPn+1=(λ+μ)Pn当系统状态n=N时，有λPn-1=μPn于是得到简化形式的稳态概率方程组：Pn＝(λ/μ)np01≤n≤N代入（P0+P1+…+Pn)=10N-112N-2λλλλμμμμN故有（P0＋(λ/μ)P0+…+(λ/μ)nP0）＝1P0（1＋(λ/μ)+…+(λ/μ)n）＝1于是：P0＝1/(1＋(λ/μ)+…+(λ/μ)n)当λ＝μ时P0＝1/(N+1)当λ≠μ时P0＝（1－λ/μ）/(1－(λ/μ)N+1)1）P0为系统空闲的概率，因此系统不空的概率即服务台忙的概率（系统满的概率或系统损失的概率）P忙＝1－P02）平均队长（系统中顾客数的期望值）Ls和平均队列长Lq(系统中排队等待服务的顾客数的期望值)∞∞

Ls=∑nPnLq=∑(n-1)Pn

n=0n=13)有效到达率e

（有效离去率μe

）：平均每单位时间进入（离去）系统的顾客数。在稳态情况下两者相等，因此有：e

=μe=∑nPn=∑μnPn4）平均逗留时间Ws和平均等待时间Wq:由Little公式可知：Ws＝Ls

/e

Wq＝

Lq

/e

由平均服务率μ的定义可以得到每个顾客的平均服务时间为1/μ，因此有：Ws＝Wq+

1/μ5）其他公式由Little公式还可以得到：①平均队长和平均队列长的另外一组计算公式Ls＝Wse

Lq＝

Wqe②有效到达率的另外一组计算公式e

＝λ（1－PN）＋0PN即系统不满时，顾客以λ的速度进入系统e

＝μ（1－P0）＋0P0即系统不空时，顾客以μ的速度离开系统③系统平均每单位时间损失的顾客数损＝λ－e

＝λPN④闲期和忙期从服务台闲到下一个顾客来到的平均间隔时间是1/λ，因此平均闲期长为：T闲＝1/λ由于服务台忙闲间隔出现，故有：T忙/T闲＝P忙/P闲＝(1-P0)/P0，于是T忙＝T闲×

P忙/P闲＝T闲×

(1-P0)/P0＝1/λ×

(1-P0)/P0例子某汽车加油站有一台油泵为汽车加油，站内可容纳4辆汽车，当站内停满车时，后来的汽车只能到别处加油，若需加油的汽车按照泊松流到达，平均每小时4辆。每辆车加油所需时间服从负指数分布，平均每辆需12分钟，试求系统有关运行指标。1、分析为什么是M/M/1/4/∞/FCFS排队系统。2、选用适当公式计算有关指标。λ＝4（辆/小时）μ=1/(12/60)=5（辆/小时），于是①P0＝（1－λ/μ）/(1－(λ/μ)N+1)P0＝（1－4/5)/(1-(4/5)4+1)=0.2/0.67232P0=0.2975由于Pn＝(λ/μ)np0故P1≈0.8*0.2975=0.2380P2≈0.82*0.2975=0.1904P3≈0.83*0.2975=0.1523P4≈0.84*0.2975=0.1218②平均队长Ls

4

Ls=∑nPn=P1+2P2+3P3+4P4

n=0

=0.2380+2*0.1904+3*0.1523+4*0.1218

=1.5629③有效到达率e

=λ（1－PN）＋0PN

e

=4*(1-P4）=4*(1-0.1218)=3.5128④逗留时间Ws

Ws＝Ls

/e

=1.5629/3.5128=0.4450⑤等待时间WqWq＝Ws-1/μ＝0.4450－0.2=0.2450⑥平均队列长LqLq＝

Wqe=0.2450*3.5128=0.86⑦系统平均每单位时间损失的顾客数损损＝λ－e

＝λPN=4*0.1218=0.4872⑧忙期T忙＝T闲×

P忙/P闲＝T闲×

(1-P0)/P0＝1/e×

(1-P0)/P0=1/3.5128*(1-0.2975)/0.2975=0.8注意M/M/1/N/∞/FCFS当N趋于∞时为等待制系统；当N趋于0时为损失制系统；思考题试画出M/M/1客源无限的损失制排队系统的状态转移速度图，写出相应的状态转移速度矩阵及相应的基本数量指标表达式。1）M/M/1损失制排队系统状态转移速度图和状态转移速度矩阵01λμ2）系统在稳态时的状态概率方程：PA=0即（P0，P1）＝03）M/M/1损失制系统特征量计算公式P0=μ/(λ+μ)P1=λ/(λ+μ)P损=P忙=P1=λ/(λ+μ)例子某汽车加油站有一台油泵为汽车加油，站内可容纳1辆汽车，当站内停满车时，后来的汽车只能到别处加油，若需加油的汽车按照泊松流到达，平均每小时4辆。每辆车加油所需时间服从负指数分布，平均每辆需12分钟，试求系统有关运行指标。1、该系统是M/M/1/1/∞/FCFS损失制排队系统。2、选用适当公式计算有关指标。λ＝4（辆/小时）μ=1/(12/60)=5（辆/小时），于是P0=μ/(λ+μ)＝0.56P1=λ/(λ+μ)＝0.44P损=P忙=P1=λ/(λ+μ)＝0.44每小时接待的顾客数为：e

=λP0+0P1=λμ/(λ+μ)＝2.2（辆/小时）每小时损失的顾客数为：损＝λ－e=4－2.2＝1.8（辆/小时）M/M/1等待制排队系统1、系统的意义顾客按泊松流输入，平均到达率为λ，服务时间服从负指数分布、平均服务率为μ，1个服务台，系统容量和顾客源为无限。当顾客来到系统时，若服务台忙，则顾客排队等待服务，排队规则为先到先服务的排队系统。2、系统的状态转移速度图0n12n-1λλλλμμμμλμ3、状态转移概率矩阵：4、状态概率方程PA=0打开即得计算个概率的公式。在等待制系统中，要求λ/μ<1，否则系统将是超负荷的，不能达到稳态和无法讨论。相应的数量指标通过进一步计算可简化成下面更简单的形式。M/M/1等待制系统特征量计算公式P0=1/((λ/μ)0+(λ/μ)1+…+(λ/μ)n+…)=1-(λ/μ)Pn=(λ/μ)nP0=(λ/μ)n(1-(λ/μ))n=0,1,2,…Ls=λ/(μ-λ)e

＝μ（1－P0)=λWs＝Ls

/e=1/(μ-λ)Wq=Ws-

1/μ=1/(μ-λ)-1/μ=λ

/μ(μ-λ)Lq＝

Wqe=

λ2

/μ(μ-λ)例子某汽车加油站有一台油泵为汽车加油，站内可容纳汽车量无限，若需加油的汽车按照泊松流到达，平均每小时4辆。每辆车加油所需时间服从负指数分布，平均每辆需12分钟，试求系统有关运行指标。1、该系统属于M/M/1等待制排队系统。2、选用适当公式计算有关指标。计算一般遵循以下顺序：Ls=λ/(μ-λ)＝4/(5-4)=4e

＝μ（1－P0)=λ=4Lq＝

Wqe=

λ2

/μ(μ-λ)=16/5=3.2Ws＝Ls

/e=1/(μ-λ)=1Wq=Ws-

1/μ=1-1/5=0.8练习1、某音乐厅设有一个售票处，营业时间为8时到16时，假定顾客流和服务时间均为负指数分布，且顾客到来的平均间隔时间为2.5分钟，窗口为每位顾客服务平均需1.5分钟，试求：

1)顾客不需等待的概率p0;

2)平均排队长度Ls

3)顾客在系统内平均逗留时间Ws

4)平均排队等待人数Lq

5)平均排队等待时间Wq；

6）系统内顾客人数超过4个的概率；

7)顾客在系统内逗留时间大于15分钟的概率；

8）在六天工作日内系统中没有顾客的小时数；

9）若决定当顾客平均逗留时间超过半小时时，就应增加一个售票窗口，试问这相当于要求顾客的平均到达率是原有的几倍？课堂练习某维修店只有一个修理工人，来修理的顾客达到次数服从泊松分布，平均每小时4人，修理时间服从负指数分布，平均需6分钟。求：1、修理店空闲时间概率；2、店内有三个顾客的概率3、店内至少有一个顾客的概率；4、店内顾客平均数；5、在店内平均逗留时间；6、等待服务的顾客平均数；7、平均等待服务时间；该系统为M/M/1/∞/∞/FCFS模型，λ＝4人/小时μ＝10人/小时1、P0=1-(λ/μ)＝1－4/10=0.6Pn=(λ/μ)nP0=(λ/μ)n(1-(λ/μ))2、P3=(λ/μ)3(1-(λ/μ))=0.03843、1－P0=0.44、Ls=λ/(μ-λ)＝4/(10-4)=2/3（人）5、Ws＝1/(μ-λ)＝1/(10-4)（小时）=10(分钟）6、Lq＝

Wqe=

λ2

/μ(μ-λ)＝16/(10*6)=4/15（人）7、Wq=Ws-

1/μ=λ

/μ(μ-λ)＝1/15（小时）多服务台指数分布排队系统M/M/C/N/∞/FCFS混合制排队系统1、系统意义：顾客按泊松流输入，到达率为λ；服务时间服从负指数分布，服务率为μ；有C个服务台，先到先服务，系统容量为N（N>C），顾客源无限的混合制排队系统。顾客到达系统时，若无空闲服务台，系统中顾客数小于N，则排队等待服务；若系统中顾客数等于N，则离开系统另求服务。2、系统状态转移速度图：0N-112N-2λλλλμcμ2μcμNCC-1λλcμcμC+13μλ(c-1)μλcμcμλλ稳态下状态概率方程PA=0其中：P=(P0,P1,P2,P3,……Pn)状态转移速度矩阵由此可得稳态概率应满足的关系：当n<c时，有λP0＝μP1故P1＝(λ/μ)P0λP0－（μ＋λ）P1＋2μP2＝02μP2＝－λP0＋（μ＋λ）P1P2＝(λ2/2μ2)P0令ρ=λ/（cμ），称为系统负荷强度，可得Pn的一般表达式：Pn＝λ/(nμ)Pn-1=(c/n)ρPn-1Pn＝1/n!(λ/μ)nP0Pn＝cn/n!ρn

P0当c<n≤N时λPn－1＋cμPn+1=(λ+cμ)PnPn＝cn/c!ρn

P0也可以根据系统处于稳态时每个状态的转入率等于转出率求得Pn的一般表达式。系统的基本数量指标由（P0+P1+…+Pn)=1可得

c-1P0=[∑cn/n!ρn+(cc/c!)*((ρc-ρN+1)/(1-ρ))]-1

n=0于是：cn/n﹗ρnP0

n<cPn=

cc/c﹗ρnP0

cn

N

NN-1λe=∑

λnPn=∑

λPn+0PN=λ(1-PN)n=0n=0Ls=Lq+λe/μ=Lq+cρ

(1-PN)

NLq=∑(n-c)Pn

n=c+1Lq=(ccρc+1P0

)/(c!(1-ρ

)2)[1-ρN-c

-(N-c)

ρ

N-c(1-ρ)]Wq=Lq/λe=Lq/(λ(1-PN))Ws=Wq+1/μ例子某汽车加油站有2台油泵为汽车加油，站内可容纳4辆汽车，当站内停满车时，后来的汽车只能到别处加油，若需加油的汽车按照泊松流到达，平均每小时4辆。每辆车加油所需时间服从负指数分布，平均每辆需12分钟，试求系统有关运行指标。该系统是M/M/2/4/∞/FCFS混合制排队系统；其中λ＝4（辆/小时）μ=1/(12/60)=5（辆/小时）C=2,ρ=λ/（cμ）=0.4

c-1P0=[∑cn/n!ρn+(cc/c!)*((ρc-ρN+1)/(1-ρ))]-1

n=0P0=[1+2ρ+22(ρ2-ρ5)/2!(1-ρ)]-1P0=[1+0.8+2*(0.42-0.45)/(1-0.4)]-1P0=0