运筹学第三版排队论课件幻灯片资料.ppt

n单击此处编辑母版副标题样式1单击此处编辑母版标题样式排队论排队论排队论(queuing theory)(queuing theory) 研究内容包括三个部分：v (1) 排队系统的性态问题v (2) 排队系统的最优化问题v (3) 排队系统的统计推断问题解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理，研究设计改进措施等统计推断，即判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究最优化，又分静态最优和动态最优，前者指最优设计，后者指现有排队系统的最优运营性态问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等n单击此处编辑母版副标题样式2单击此处编辑母版标题样式排队论v第1节 基本概念v第2节 到达间隔的分布和服务时间的分布v第3节 单服务台负指数分布排队系统的分析v第4节 多服务台负指数分布排队系统的分析v第5节 一般服务时间M/G/1模型v第6节 经济分析系统的最优化v第7节 分析排队系统的随机模拟法第1节 基 本 概 念 v1.1 排队过程的一般表示v1.2 排队系统的组织和特征v1.3 排队模型的分类v1.4 排队问题的求解1.1 排队过程的一般表示v各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。

v排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的排队过程的一般模型1.1 排队过程的一般表示到达的顾客要求服务内容服务机构1.不能运转的机器2.修理技工3.病人4. 呼唤5.文件稿6.提货单7.到达机场上空的飞机8.驶入港口的货船9.上游河水进入水库10.进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装(卸)货装(卸)放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库 管理员跑道货码头 (泊位)水闸管理员我方高射炮形形色色的排队系统 实际的排队系统虽然千差万别，但是它们有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事1.2 排队系统的组成和特征 1.2 排队系统的组成和特征 v排队系统由三个基本部分组成： 输入过程 排队规则 服务机构1.2 排队系统的组成和特征 输入过程v输入即指顾客到达排队系统。

输入过程是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流v一般可以从以下几个方面来描述个输入过程(1) 顾客的总体数，又称顾客源、输入源这是指顾客的来源 顾客源可以是有限的，也可以是无限的 例如，到售票处购票的顾客总数可以认为是无限的；上游河水流入 水库可以认为顾客总体是无限的 例如，某个工厂因故障待修的机床则是有限的1.2 排队系统的组成和特征 输入过程(2) 顾客到来的方式这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达 病人到医院看病是顾客单个到达的例子 在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的1.2 排队系统的组成和特征 输入过程(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布这是求解排队系统有关运行指标问题时，首先需要确定的指标这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大 顾客相继到达的间隔时间可以是确定型的，也可以是随机型的例如：在流水线上装配的各部件必须按确定的时间间隔到达装配点，定点运行的列车、班机的到达也都是确定的；例如：物流配送等待的顾客、办理出关手续的顾客、通过路口的车辆的到达都是随机的。

1.2 排队系统的组成和特征 输入过程 对于随机的情形，必须了解单位时间的顾客到达数或相继到达的时间间隔的概率分布 顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种1.2 排队系统的组成和特征 输入过程(4) 顾客的到达可以是相互独立的5) 输入过程可以是平稳的，或称对时间是齐次的，即描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的1.2 排队系统的组成和特征 排队规则 v这是指服务台从队列中选取顾客进行服务的顺序一般可以分为损失制、等待制和混合制等3大类v(1)损失制这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来 例如：拔号后出现忙音，顾客不愿等待而自动挂断，如要再打，就需重新拔号，这种服务规则即为损失制 1.2 排队系统的组成和特征 排队规则 (2)等待制这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务 例如：排队等待售票，故障设备等待维修等 对于等待制，为顾客进行服务的次序可以采用下列各种规则：先到先服务(FCFS)后到先服务(LCFS)随机服务(RS)有优先权的服务1.2 排队系统的组成和特征 排队规则 (2)等待制（续）。

先到先服务按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形 后到先服务 例如：仓库中迭放的钢材，后迭放上去的都先被领走 随机服务即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务 例如：交换台接通呼叫 优先权服务 例如：老人、儿童先进车站； 危重病员先就诊； 遇到重要数据需要处理计算机立即中断其他数据的处理等1.2 排队系统的组成和特征 排队规则 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去具体说来，大致有三种： 队长有限 等待时间有限 逗留时间有限1.2 排队系统的组成和特征 排队规则 (3)混合制 队长有限当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的 具体地，最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来 例如：水库的库容是有限的，旅馆的床位是有限的1.2 排队系统的组成和特征 排队规则 (3)混合制 队长有限 等待时间有限即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。

例如：易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效 例如：顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐1.2 排队系统的组成和特征 排队规则 (3)混合制 队长有限 等待时间有限 逗留时间(等待时间与服务时间之和)有限 例如：用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制1.2 排队系统的组成和特征 排队规则 （续）v从允许排队的空间看队列可以排在具体的处所，也可以是抽象的排队空间可以有限，也可以无限v从排队的队列数目看，可以是单列，也可以是多列在多列的情形，各列间的顾客有的可以互相转移，有的不能有的排队顾客因等候时间过长而中途退出，有的不能退出，必须坚持到被服务为止1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式服务机构可以没有服务员，也可以有一个或多个服务员(服务台、通道、窗口等)。

从数量上说，服务台有单服务台和多服务台之分在有多个服务台的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。

从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 多队多服务台并串联混合式等等服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)服务台可以从以下3方面来描述：(1) 服务台数量及构成形式从构成形式上看，服务台有： 单队单服务台式；如(a)图 单队多服务台并联式；如(c)图 多队多服务台并联式；如(b)图 单队多服务台串联式；如(d)图 单队多服务台并串联混合式； 多队多服务台并串联混合式等等服务台的各种排列方式1.2 排队系统的组成和特征 服务机构 (服务台情况)(2) 服务方式这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种如公共汽车一次就可装载一批乘客就属于成批服务3) 服务时间的分布服务时间可分为确定型和随机型一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等v服务时间的分布通常假定是平稳的 指时间间隔分布及其特征参数（数学期望、方差等）不随时间的变化而变化。

1.3 排队模型的分类 排队模型分类方法D.G.Kendall，1953构成排队模型的三个主要特征指标o(1) 相继顾客到达间隔时间的分布；o(2) 服务时间的分布；o(3) 服务台的个数根据这三个特征对排队模型进行分类的Kendall记号： X/Y/ZoX：表示相继到达间隔时间的分布；oY：表示服务时间的分布；oZ：并列的服务台的数目1.3 排队模型的分类 表示相继到达间隔时间和服务时间的各种分布符号表示相继到达间隔时间和服务时间的各种分布符号vM负指数分布(M是Markov的字头，因为负指数分布具有无记忆性，即Markov性)vD确定型(deterministic)vEkk阶爱尔朗(erlang)分布vGI 一般相互独立(general independent)的时间间隔的分布vG 一般(general)服务时间的分布1.3 排队模型的分类vKendall符号的扩充 X/Y/Z/A/B/C其中前三项的意义不变，后三项的意义分别是：oA：系统容量限制N，或称等待空间容量如系统有N个等待位子，则 0 N 0是常数，则称X 服从参数为 的泊松分布其均值为 方差为 第2节 到达间隔的分布和服务时间的分布若随机变量若随机变量t t 取具有概率密度函数为取具有概率密度函数为。