排队论及其模型

1排队论运筹学2排队论排队论(queuingtheory)也称随机服务系统理论(RandomServiceSystemTheory)，是为研究和解决具有拥挤现象的问题而发展起来的一门应用数学的分支。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。3排队论排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。4排队论排队论(queuingtheory)研究内容包括三个部分：(1)排队系统的性态问题(2)排队系统的最优化问题(3)排队系统的统计推断问题性态问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等。最优化，又分静态最优和动态最优，前者指最优设计，后者指现有排队系统的最优运营。统计推断，即判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理，研究设计改进措施等。5排队论第1节基本概念第2节到达间隔的分布和服务时间的分布第3节单服务台负指数分布排队系统的分析第4节多服务台负指数分布排队系统的分析第5节一般服务时间M/G/1模型第6节经济分析——系统的最优化第7节分析排队系统的随机模拟法6第1节基本概念1.1排队过程的一般表示1.2排队系统的组织和特征1.3排队模型的分类1.4排队问题的求解7不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。1.1排队过程的一般表示81.1排队过程的一般表示各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队过程的一般模型91.1排队过程的一般表示到达的顾客要求服务内容服务机构1.不能运转的机器2.修理技工3.病人4.电话呼唤5.文件稿6.提货单7.到达机场上空的飞机8.驶入港口的货船9.上游河水进入水库10.进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装(卸)货装(卸)放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库管理员跑道货码头(泊位)水闸管理员我方高射炮形形色色的排队系统10实际的排队系统虽然千差万别，但是它们有以下的共同特征：(1)有请求服务的人或物——顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。1.2排队系统的组成和特征111.2排队系统的组成和特征排队系统由三个基本部分组成：①输入过程②排队规则③服务机构121.2排队系统的组成和特征输入过程输入即指顾客到达排队系统。输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从以下几个方面来描述—个输入过程(1)顾客的总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。131.2排队系统的组成和特征输入过程(2)顾客到来的方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。141.2排队系统的组成和特征输入过程(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。151.2排队系统的组成和特征输入过程(4)顾客的到达可以是相互独立的。(5)输入过程可以是平稳的，或称对时间是齐次的，即描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的。161.2排队系统的组成和特征排队规则这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。171.2排队系统的组成和特征排队规则(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务(FCFS)后到先服务(LCFS)随机服务(RS)有优先权的服务181.2排队系统的组成和特征排队规则(2)等待制。对于等待制，为顾客进行服务的次序可以采用下列各种规则：①先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。③随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。④优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。191.2排队系统的组成和特征排队规则(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。201.2排队系统的组成和特征排队规则(3)混合制①队长有限。②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。211.2排队系统的组成和特征排队规则(3)混合制①队长有限。②等待时间有限。③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。221.2排队系统的组成和特征排队规则（续）从允许排队的空间看队列可以排在具体的处所，也可以是抽象的。排队空间可以有限，也可以无限。从排队的队列数目看，可以是单列，也可以是多列。在多列的情形，各列间的顾客有的可以互相转移，有的不能。有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服务为止。231.2排队系统的组成和特征服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。从数量上说，服务台有单服务台和多服务台之分。在有多个服务台的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。241.2排队系统的组成和特征服务机构(服务台情况)服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从构成形式上看，服务台有：①单队——单服务台式；如(a)图②单队——多服务台并联式；如(c)图③多队——多服务台并联式；如(b)图④单队——多服务台串联式；如(d)图⑤单队——多服务台并串联混合式；⑥多队——多服务台并串联混合式等等。服务台的各种排列方式25单队列——S个服务台并联的排队系统S个队列——S个服务台的并联排队系统1.2排队系统的组成和特征26单队——多个服务台的串联排队系统多队——多服务台混联、网络系统1.2排队系统的组成和特征271.2排队系统的组成和特征服务机构(服务台情况)(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。服务时间可分为确定型和随机型。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。服务时间的分布通常假定是平稳的。281.3排队模型的分类排队模型分类方法——D.G.Kendall，1953构成排队模型的三个主要特征指标(1)相继顾客到达间隔时间的分布；(2)服务时间的分布；(3)服务台的个数。根据这三个特征对排队模型进行分类的Kendall记号：X/Y/ZX：表示相继到达间隔时间的分布；Y：表示服务时间的分布；Z：并列的服务台的数目。291.3排队模型的分类表示相继到达间隔时间和服务时间的各种分布符号M——负指数分布(M是Markov的字头，因为负指数分布具有无记忆性，即Markov性)D——确定型(deterministic)Ek——k阶爱尔朗(erlang)分布GI——一般相互独立(generalindependent)的时间间隔的分布G——一般(general)服务时间的分布301.3排队模型的分类Kendall符号的扩充X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是：A：系统容量限制N，或称等待空间容量。如系统有N个等待位子，则0N∞。当N=0时，说明系统不允许等待，即为损失制。N=∞时为等待制系统，此时∞般省略不写。N为有限整数时，表示为混合制系统。B：顾客源数目m。分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。C：服务规则，如先到先服务(FCFS)，后到后服务(LCFS)，优先权服务(PR)等。311.3排队模型的分类Kendall符号的扩充X/Y/Z/A/B/C某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。约定：如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。例如：某排队问题为M／M／S／∞／∞／FCFS／，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。321.4排队问题的求解首先需要确定属于哪种排队模型，其中顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定确定用以判断系统运行优劣的基本数量指标，求出这些数量指标的概率分布或特征数331.4排队问题的求解用于描述排队系统运行状况的基本数量指标(1)队长：系统中的顾客数，是排队等待的顾客数与正在接受服务的顾客数之和，期望值记作Ls；排队长（队列长）：系统中排队等待服务的顾客数，期望值记作Lq；队长和排队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差