1、排队论(Queuing Theory),也称为随机服务系统理论(Random Service System Theory),是一门研究排队和等待服务现象的科学.它在研究各种排队系统概率规律性的基础上,解决相应排队系统的最优设计和最优控制问题.排队论里把要求服务的对象称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”.顾客与服务员组成了服务系统.顾客为了得到某种服务而到达系统,若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统.,1909年,丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生.排队论早期研究电话
2、、通信中的问题,现在它们仍然是排队论的重要应用领域.近几十年排队论在计算机通讯网络系统、交通运输、医疗卫生、库存管理、公共服务等诸多领域中得到广泛应用.,(1878-1929),随机性是排队系统的一个普遍特点,顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间是随机的.这样的服务系统称为随机服务系统.如果为了减少排队而增加服务设施,人力和物力的支出就大,甚至会出现空闲浪费;如果服务设施太少,顾客排队等待的时间就会很长.如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,这就是随机服务系统理论排队论所要研究解决的问题.,一.基 本 概 念,(一)排队系统的描述 1.排队系统的特
3、征(1)请求服务的人或物顾客；(2)为顾客服务的人或物服务员或服务台；(3)顾客到达系统的时刻是随机的,为每一位顾客提供服务的时间是随机的,因而整个排队系统的状态也是随机的.,2.排队系统的基本组成部分 排队系统有输入过程、服务规则和服务台等三个组成部分.输入过程 指要求服务的顾客按怎样的规律到达排队系统的过程,也称其为顾客流.可以从三个方面来描述一个输入过程.(1)顾客总体数 又称顾客源或输入源.顾客源可以是有限的,也可以是无限的.例如,到售票处购票的顾客总数可以认为是无限的,而某个工厂因故障待修的机床则是有限的.,(2)顾客到达方式 单个到达或成批到达.病人到医院看病是顾客单个到达的例子.
4、在库存问题中如将材料进货或产品入库看作是顾客,那么这种顾客是成批到达的.(3)顾客流的概率分布或相继顾客到达的时间间隔的分布 这是求解排队系统有关运行指标问题时,首先需要确定的指标,即在一定的时间间隔内到达k(k=1,2,)个顾客的概率分布.顾客流的概率分布一般有定长分布、二项分布、Poisson分布(最简单流)以及Erlang分布等.,服务规则 一般可以分为损失制、等待制和混合制等三类.(1)损失制 如果顾客到达排队系统时,所有服务台都已被先来的顾客占用,那么他们就自动离开系统永不再来.如电话拔号后出现忙音,顾客不愿等待而自动挂断电话，如要再打,就需重新拨号,这种服务规则即为损失制.(2)等
5、待制 当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务.例如,排队等待售票、故障设备等待维修等.,在等待制中,服务台在选择顾客进行服务时,常有如下四种规则：先到先服务 按顾客到达的先后顺序对顾客进行服务,这是最普遍的情形.后到先服务 例如仓库中迭放的钢材,后迭放上去的先被领走.随机服务 即当服务台空闲时,不按照排队顺序而随意指定某个顾客去接受服务.优先权服务 如老人、儿童优先进车站;危重病员先就诊;遇到重要数据需要处理计算机立即中断其他数据的处理等.,(3)混合制 这是等待制与损失制相结合的一种服务规则,一般指允许排队,但不允许队列无限长.一般有三种情形：队长有限 当排队等待服务的
6、顾客人数超过规定数量时,后来的顾客自动离去,即系统的等待空间是有限的.如在最多只能容纳m个顾客的系统中,当新顾客到达时,若系统中的顾客数(称为队长)小于m,则可进入系统排队或接受服务;否则,便离开系统,并不再回来.如水库的库容是有限的,旅馆的床位是有限的.,等待时间有限 即顾客在系统中的等待时间不超过某一给定的长度T,当等待时间超过T时,顾客将自动离去,并不再回来.如在易损坏的电子元件库存问题中,超过一定存储时间的元件被自动认为失效.逗留时间(等待时间与服务时间之和)有限 例如用高射炮射击飞机,飞机越过高射炮射击有效区域的时间有限.,服务台 从三个方面来描述：(1)服务台数量及构成形式 从数量
7、上来看,服务台有单服务台和多服务台之分.从构成形式上来看,服务台有：单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等.,单服务台排队系统,单队列n个服务台并联的排队系统,n个队列n个服务台的并联排队系统,单队多个服务台的串联排队系统,多队多服务台混联、网络系统,一般排队系统的描述,(2)服务方式 在某一时刻接受服务的顾客数,它有单个服务和成批服务两种.(3)服务时间的分布 一般情况下,对每一个顾客的服务时间是一随机变量,其概率分布有定长分布、负指数分布、k级Erlang分布、一般分布(所有顾客的服务时间都是
8、独立同分布的)等等.3.排队系统的描述符号与分类 为了区别各种排队系统,根据输入过程、服务规则和服务台的变化对排队模型进行描述或分类,1953年英国统计学家D.G.Kendall,(1918-2007)提出了一种目前在排队论中被广泛采用的记号,后来又被扩充为如下的表达方式：X/Y/Z/A/B/C各符号的意义为：,X表示顾客相继到达间隔时间分布,常用下列符号：M表示到达过程为Poisson过程或负指数分布；D表示定长输入；Ek表示k阶Erlang分布；G表示一般相互独立的随机分布.,Y表示服务时间分布,所用符号与表示顾客到达间隔时间分布相同.Z表示服务台(员)个数.A表示系统中顾客容量限额:如系
9、统容量为m(m0),有n个服务台，当m=n时,说明系统不允许等待,即为损失制.m=时为等待制系统,此时一般省略不写.nm时为混合制系统.B表示顾客源限额,分有限与无限两种,表示顾客源无限,此时一般也省略不写.,C表示服务规则，常用下列符号：FCFS 表示先到先服务的排队规则；LCFS 表示后到先服务的排队规则；PR 表示优先权服务的排队规则.例如：排队问题M/M/n/FCFS表示顾客到达间隔时间为Poisson流(负指数分布),服务时间为负指数分布,有n个服务台,系统等待空间容量无限(等待制),顾客源无限,采用先到先服务规则.,在很多情况下,排队问题仅用上述表达形式中的前3个、4个或5个符号.
10、如不特别说明,均理解为系统等待空间容量无限,顾客源无限,先到先服务,单个服务的等待制系统.(二)排队系统的主要运行指标 研究排队系统目的是通过了解系统运行的状况,对系统进行调整和控制,使系统处于最优运行状态.因此,首先需要描述系统的运行状况,主要运行指标有：,1.队长和等待队长 队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和).等待队长是指系统中正在排队等待服务的顾客数.队长和等待队长一般都是随机变量,我们希望能确定它们的分布，或至少能确定它们的期望值(即平均队长和平均等待队长).队长的分布是顾客和服务员都关心的,特别对系统设计人员来说,如果能知道队长的分布,就能确定队长超
11、过某个值的概率,从而确定合理的等待空间.,2.等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止的这段时间称为等待时间,是随机变量,也是顾客最关心的指标,因为顾客通常希望等待时间越短越好.从顾客到达时刻起到他接受服务完成止的这段时间称为逗留时间,也是随机变量,顾客同样非常关心.对于这两个指标的研究当然是希望能够确定它们的分布,或至少能够知道顾客的平均等待时间和平均逗留时间.,除了上述几个主要运行指标外,还会用到其他一些重要的指标.如在损失制或系统容量有限的情况下,由于顾客被拒绝,而使服务系统受到损失的顾客损失率及系统强度等.由于相当一部分排队系统在运行了一定时间后,都会趋于一个平稳状态,在
12、平稳状态下,运行指标与系统所处的时刻无关,而且系统初始状态的影响也会消失.我们将主要讨论系统平稳状态的性质.(三)一些常用记号Pn 稳态系统任一时刻状态为n的概率.平均到达率；1/平均到达间隔.,平均服务率；1/平均服务时间.Ls平均队长 稳态系统任一时刻的所有顾客数的期望值；Lq平均等待队长 稳态系统任一时刻的等待服务的顾客数的期望值；Ws平均逗留时间 在任意时刻进入稳态系统的顾客逗留时间的期望值；Wq平均等待时间 在任意时刻进入稳态系统的顾客等待时间的期望值.对于损失制和混合制的排队系统,顾客在到达服务系统时,若系统容量已满则离去,到达的顾客不一定全部进入系统，为此引入有效平均到达率.,e
13、 有效平均到达率 每单位时间内进入系统的平均顾客数(期望值).这时就是每单位时间内来到系统(包括未进入系统)的平均顾客数(期望值).对于等待制的排队系统,有e=.(四)Little公式 在系统达到稳态时，有效平均到达率为常数e，则有下面的John D.C.Little(美国,1928-)公式：,(一)输入过程 输入过程描述顾客以怎样的规律到达系统，一般用相继两顾客到达时间间隔来描述系统输入特征.主要输入过程有：1.定长输入.顾客有规则地等距到达，每隔时间到达一个顾客.这时相继顾客到达间隔的分布函数F(t)为：,二.输入过程和服务时间分布,2.Poisson输入，又称最简单流.满足下面三个条件的
14、输入称之为最简单流.(1)平稳性.又称输入过程是平稳的，指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关,即对任意(0,)，在(,+t或(0,t)内恰好到达k个顾客的概率相等：设初始条件为,且有.,(2)无后效性.在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的.通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响.(3)单个性又称普通性.在充分小的时段内最多到达一个顾客.可以证明,对于Poisson流,随机变量N(t)服从Poisson分布,即在长度为t的时间内到达k个顾客的概率为,其中参数0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均
15、到达率.对于Poisson流，可以证明其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，服从负指数分布，其分布函数和分布密度分别为：,3.k阶Erlang输入.在参数为的Poisson输入中,对任意的j与k,设第j与第j+k个顾客之间的到达间隔为,可以证明，随机变量Tk服从参数为的k阶Erlang分布其分布密度为：,其中k为非负整数.例如某排队系统有并联的k个服务台,顾客流为Poisson流，规定第i,k+i,2k+i,个顾客排入第i号台(i=1,2,k),则第k台所获得的顾客流,即为k阶Erlang输入流,其他各台,从它的第一个顾客到达以后开始所获得的流也为k阶Erlang输入流.,
16、4.成批到达的输入.排队系统每次到达的顾客不一定是一个,而可能是一批,每批顾客的数目n是一个随机变量,其分布为:(二)服务时间分布 1.定长分布.每一个顾客的被服务时间都是常数，此时服务时间t的分布函数为：2.负指数分布.各个顾客的被服务时间相互独立,具有相同的负指数分布,分布函数为,其中0为一常数，服务时间t的数学期望1/为平均被服务时间.3.k阶Erlang分布.每个顾客的被服务时间相互独立，具有相同的Erlang分布,密度函数为 其中0为一常数，平均服务时间为 当k=1时,Erlang分布化归为负指数分布.当k时，得到长度为1/的定长分布.,(三)排队论研究的基本问题 排队论研究的首要问
17、题是排队系统主要运行指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题.与这两个问题相关的还包括排队系统的统计推断问题.1.通过研究主要运行指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征.2.统计推断问题.建立适当的排队模型是排队论研究的第一步，建立模型过程中经,常要考虑如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等.3.系统优化问题,又称为系统控制问题或系统运营问题，基本目的是使系统处于最优或最合理的状态.系统优化问题包括最优设计问题和最优运营问题,例如有最少费用问题、服务率的控制问题、服务台的开
18、关策略、顾客(或服务)根据优先权的最优排序等方面的问题.,排队系统的一般决策过程：根据已知条件绘制状态转移速度图;依据状态转移速度图写出各稳态概率之 间的关系;求出 P0 及 Pn;计算各项运行指标;用系统运行指标构造目标函数，对系统 进行优化.,三.几个排队模型,(一)M/M/n/n排队模型顾客到达的间隔时间负指数分布，参数为顾客接受服务的时间负指数分布，参数为系统有n个服务台系统最多容纳n个顾客 系统的状态空间,1.M/M/n/n状态转移图,2.稳态概率之间的关系(令,称为系统 负荷水平或强度)对0状态,有 故 对1状态,有 故 对k-1状态,有 故 对n-1状态,有 故 正则条件,3.求
19、出平稳分布,4.运行指标,(1)系统损失概率,(2)单位时间内平均损失的顾客数,(3)有效平均到达率,(4)占用服务台的均值,显然(5)顾客在系统中平均逗留时间 根据Little公式可得 即等于顾客的平均被服务时间.(6)服务台的效率,例1 某计算机有5个终端,用户按Possion流到达,平均每分钟到达0.2个用户,每个用户平均用机时间为15分钟,用机时间服从负指数分布,当5个终端被占用时,后来的用户只能到其他计算机处接受服务.求系统的运行指标.解 这是M/M/5/5排队模型.平均到达率=12户/小时,平均服务率=4户/小时,系统强度.,(1)系统损失概率,(2)每小时内平均损失的用户数,(户
20、),(3)用户有效平均到达率,(户/小时),(4)占用终端的均值或系统平均队长,(个),(5)用户在系统中平均逗留时间,(小时),(6)终端的服务效率,(二)M/M/n排队模型顾客到达的间隔时间负指数分布，参数为顾客接受服务的时间负指数分布，参数为系统有n个服务台系统容量没有限制 系统的状态空间,1.M/M/n状态转移图,2.稳态概率之间的关系(其中)对0状态,有 故 对1状态,有 故 对n-1状态,有 故 对n状态,有 故 对n+r-1状态,有 故 正则条件,3.求出平稳分布,当 时,由正则条件可得,4.运行指标,(1)平均等待队长,(2)占用服务台的均值,(3)平均队长,(6)必须排队等待
21、的概率,(4)平均等待时间 根据Little公式可得,(5)平均逗留时间 根据Little公式可得,例2 某城市火车站有4台电子触摸屏供旅客查询,旅客按Possion流到达,每位旅客在触摸屏查询时间服从负指数分布,平均查询时间为3分钟,如果所有触摸屏被占用时就排队等待,根据以往统计资料知道触摸屏被占用的均值为1.5台.求系统的运行指标.解 这是M/M/4排队模型.由条件可知平均服务率=1/3位/分钟,台,因此.,(1)平均等待队长,(人),(2)平均队长,(人),(3)平均等待时间,(分钟),(4)平均逗留时间,(分钟),(5)必须排队等待的概率,(三)M/M/n/m(mn)排队模型顾客到达的
22、间隔时间负指数分布，参数为顾客接受服务的时间负指数分布，参数为系统有n个服务台系统最多容纳m个顾客 系统的状态空间,1.M/M/n/m状态转移图,2.稳态概率之间的关系(其中)对0状态,有 故 对1状态,有 故 对n-1状态,有 故 对n状态,有 故 对m-1状态,有 故 正则条件,3.求出平稳分布,由正则条件可得,4.运行指标,(1)系统损失概率,(2)单位时间内平均损失的顾客数,(3)有效平均到达率,(4)占用服务台的均值,从而,(5)平均等待队长,当 时,当 时,(6)平均队长,(7)平均等待时间 根据Little公式可得,(8)平均逗留时间 根据Little公式可得,注 若m=n时,即是M/M/n/n排队模型;若 令,则成为M/M/n/n排队 模型.,例3 某加油站有两条加油管,汽车按平均每2分钟1辆的Possion流到达,加油时间服从负指数分布,参数=0.5辆/分钟,除加油的车外,站内最多只能停放3辆车等待,如果当汽车到达时发现位置已满,它即往别处加油.求系统的运行指标.解 这是M/M/2/5排队模型.由条件可知=0.5,加油站的空闲率,
