运筹学 第6章 课件

《运筹学 第6章 课件》由会员分享，可在线阅读，更多相关《运筹学 第6章 课件（137页珍藏版）》请在金锄头文库上搜索。

1、运筹学课件 第六章 排队论制作：北京理工大学 吴祈宗等1第六章 排队论本章内容重点w基本概念w输入过程和服务时间分布w泊松输入指数服务排队模型w其他模型选介w排队系统的优化目标与最优化问 题2排队论(Queuing Theory)， 又称随机服务系统理论(Random Service System Theory),是一门 研究拥挤现象(排队、等待)的科学 。具体地说，它是在研究各种排队 系统概率规律性的基础上，解决相 应排队系统的最优设计和最优控制 问题。前 言3排队是我们在日常生活和生产 中经常遇到的现象:w上、下班搭乘公共汽车； w顾客到商店购买物品； w病员到医院看病； w旅客到售票处购

2、买车票； w学生去食堂就餐等就常常出现排队 和等待现象。 w排队的不一定是人，也可以是物：前 言4w通信卫星与地面若干待传递的信 息； w生产线上的原料、半成品等待加 工； w因故障停止运转的机器等待工人 修理； w码头的船只等待装卸货物； w要降落的飞机因跑道不空而在空 中盘旋等等。前 言5w排队问题的共同特征w有要求得到某种服务的人或物。排 队论里把要求服务的对象统称为“顾 客”w有提供服务的人或机构。把提供服 务的人或机构称为“服务台”或“服 务员”w顾客的到达、服务的时间至少有一 个是随机的，服从某种分布。前 言6不同的顾客与服务组成了各式各样 的服务系统。顾客为了得到某种服务而到 达

3、系统、若不能立即获得服务而又允许排 队等待，则加入等待队伍，待获得服务后 离开系统，见图6-1至图6-5。图6-1 单服务台排队系统前 言7图6-2 单队列S个服务台并联的排队系统图6-3 S个队列S个服务台的并联排队系统前 言8图6-4 单队多个服务台的串联排队系统图6-5 多队多服务台混联、网络系统前 言9图6-6 随机服务系统前 言一般的排队系统，都可由下 面图6-6加以描述。10面对拥挤现象，顾客排队时 间的长短与服务设施规模的大小， 就构成了设计随机服务系统中的一 对矛盾。如何做到既保证一定的服务 质量指标，又使服务设施费用经济 合理，恰当地解决顾客排队时间与 服务设施费用大小这对矛

4、盾，这就 是排队论所要研究解决的问题之一 。前 言11排队论是1909年由丹麦工程师 爱尔朗(A.KErlang)在研究电活系 统时创立的，几十年来排队论的应用 领域越来越广泛，理论也日渐完善。 特别是自二十世纪60年代以来，由于 计算机的飞速发展，更为排队论的应 用开拓了宽阔的前景。前 言12一 、排队系统的描述（一）系统特征和基本排队过程任何一个排队问题的基本排队 过程都可以用图6-6表示。从图6-6 可知，每个顾客由顾客源按一定方 式到达服务系统，首先加入队列排 队等待接受服务，然后服务台按一 定规则从队列中选择顾客进行服务 ，获得服务的顾客立即离开。1.基 本 概 念13（二）排队系统

5、的基本组成部分通常，排队系统都有输入过程、 服务规则和服务台等3个组成部分：1输入过程这是指要求服务的 顾客是按怎样的规律到达排队系统的过程 ，有时也把它称为顾客流一般可以从3 个方面来描述个输入过程。 1.基 本 概 念141.基 本 概 念(1) 顾客总体数(又称顾客源 、输入源)。这是指顾客的来源。 顾客源可以是有限的，也可以是无 限的。例如，到售票处购票的顾客 总数可以认为是无限的，而某个工 厂因故障待修的机床则是有限的。15(2)顾客到达方式。描述顾 客是怎样来到系统的，他们是单 个到达，还是成批到达。病人到 医院看病是顾客单个到达的例子 。在库存问题中如将生产器材进 货或产品入库看

6、作是顾客，那么 这种顾客则是成批到达的。1.基 本 概 念161.基 本 概 念(3)顾客流的概率分布，或称 相继顾客到达的时间间隔的分布。 这是求解排队系统有关运行指标问 题时，首先需要确定的指标。这也 可以理解为在一定的时间间隔内到 达K个顾客(K=1、2、)的概率是多 大。顾客流的概率分布一般有定长 分布、二项分布、泊松流(最简单流 )、爱尔朗分布等若干种。172.服务规则。这是指服务台 从队列中选取顾客进行服务的顺序 。一般可以分为损失制、等待制和 混合制等3大类。(1)损失制。如果顾客到达排 队系统时，所有服务台都已被占用 ，那么他们就自动离开系统永不再 来。1.基 本 概 念18(

7、2)等待制。当顾客来到系统时， 所有服务台都不空，顾客加入排队行 列等待服务。等待制中，服务台在选 择顾客进行服务时，常有如下四种规 则：1）先到先服务。按顾客到达的 先后顺序对顾客进行服务，这是最普 遍的情形。2）后到先服务。仓库中迭放的 钢材，后迭放上去的都先被领走，就 属于这种情况。1.基 本 概 念193）随机服务。即当服务台空 闲时，不按照排队序列而随意指定 某个顾客去接受服务，如电话交换 台接通呼叫电话就是一例。4）优先权服务。如老人、儿 童先进车站；危重病员先就诊；遇 到重要数据需要处理计算机立即中 断其他数据的处理等，均属于此种 服务规则。1.基 本 概 念20(3)混合制等待

8、制与损失制 相结合的一种服务规则，一般是指 允许排队，但又不允许队列无限长 下去。具体说来，大致有三种：1）队长有限。当排队等待服 务的顾客人数超过规定数量时，后 来的顾客就自动离去，另求服务， 即系统的等待空间是有限的。1.基 本 概 念212） 等待时间有限。顾客在系统 中的等待时间不超过某一给定的长度T ，当等待时间超过T时，顾客将自动离 去，并不再回来。如易损坏的电子元 器件的库存问题，超过一定存储时间 的元器件被自动认为失效。又如顾客 到饭馆就餐，等了一定时间后不愿再 等而自动离去另找饭店用餐。1.基 本 概 念223） 逗留时间有限。例如用高射 炮射击敌机，当敌机飞越高射炮射击有

9、效区域的时间为t时，若在这个时间内 未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可 看成是混合制的特殊情形，如记s为系 统中服务台的个数，则当K=s时，混合 制即成为损失制；当K=时，混合制即 成为等待制。1.基 本 概 念233服务台情况。服务台可以从以下3 方面来描述：(1) 服务台数量及构成形式1）单队单服务台式；2）单队多服务台并联式；3）多队多服务台并联式；4）单队多服务台串联式；5）单队多服务台并串联混合式,多队多服务台并串联混合式等等 。1.基 本 概 念24(2) 服务方式。这是指在某一时 刻接受服务的顾客数，它有单个服务 和成批服务两种。(3) 服务时间的分布。

10、在多数情 况下，对每一个顾客的服务时间是一 随机变量，其概率分布有定长分布、 负指数分布、K级爱尔朗分布、一般分 布(所有顾客的服务时间都是独立同分 布的)等等。1.基 本 概 念25（三）排队系统的描述符号与分类为了区别各种排队系统，根据输 入过程、排队规则和服务机制的变化对 排队模型进行描述或分类，DG Kendall提出了一种目前在排队论中被 广泛采用的“Kendall记号”，完整的 表达方式通常用到6个符号并取如下固 定格式： A/B/C/D/E/F各符号的意义为：1.基 本 概 念26A表示顾客相继到达间隔时间分布，常用下列符号： M表示到达过程为泊松过程或负指数分布； D表示定长输

11、入； Ek表示k阶爱尔朗分布； G表示一般相互独立的随机分布 。1.基 本 概 念271.基 本 概 念B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。 M表示服务过程为泊松过程或负指数分布； D表示定长分布； Ek表示k阶爱尔朗分布； G表示一般相互独立的随机分布。28C表示服务台(员)个数：“1”则表示单个服务台，“s”(s 1)表示多个服务台。 D表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 00为一常数，表示单位时 间内到达顾客的平均数，又称为顾客 的平均到达率。对于泊松流，不难证明其相继 顾客到达时间间隔i，i=1,2,是相 互独立同分布的，其分布函

12、数为负指 数分布： 2.输入过程和服务时间分布503.爱尔朗输入. 这是指相继顾客到达 时间间隔相互独立，具有相同的分布，其 分布密度为其中k为非负整数。可以证明，在参数为的泊松输人中，对 任意的j与k,设第j与第j+k个顾客之间的到 达间隔为 。则随机变 量Tk的分布必遵从参数为的爱尔朗分布， 其分布密度为：2.输入过程和服务时间分布51例某排队系统有并联的k个服务台，顾客流为泊松流，规定第i, K+i, 2K+i 个顾 客排入第i号台 ( i = 1,2,K )，则第K台所获 得的顾客流，即为爱尔朗输入流，其他各台 ，从它的第一个顾客到达以后开始所获得的 流也为爱尔朗输入流。此外，爱尔朗分

13、布中，当K1时将化为 负指数分布。2.输入过程和服务时间分布524.一般独立输入，即相继顾客到达 时间间隔相互独立、同分布，分布函数 F(t)是任意分布，因此，上面所述的所有 输入都是一般独立分布的特例。5.成批到达的输入。这时排队系统 每次到达的顾客不一定是一个，而可能是 一批，每批顾客的数目n是一个随机变量 。其分布为：到达时间间隔可能是上述几类输入中的 一种。2.输入过程和服务时间分布（6-8）53二、服务时间分布1定长分布。每一个顾客的服务 时间都是常数，此时服务时间t的分 布函数为：2.输入过程和服务时间分布542负指数分布。即各个顾客的 服务时间相互独立，具有相同的负指 数分布：其

14、中0为常数，服务时间t 的数学 期望称为平均服务时间。显然其期望 值为2.输入过程和服务时间分布552.输入过程和服务时间分布3.爱尔朗分布. 即每个顾客的服务时 间相互独立，具有相同的爱尔朗分布。其 密度函数为其中0为一常数，此种的平均服务时间 为：K=1时爱尔朗分布化归为负指数分布当 K时，得到长度为1/的定长服务。564.一般服务分布。所有顾客的服务 时间都是相互独立具有相同分布的随机变 量，其分布函数记B(X)，前面所述的各种 服务分布都是一般服务分布的特例。5.多个服务台的服务分布。可以假 定各个服务台的服务分布参数不同或分布 类型不同。6.服务时间依赖于队长的情况。指 服务员排队的

15、人愈多，服务的速度也就愈 快。2.输入过程和服务时间分布57三、排队论研究的基本问题排队论研究的首要问题是排队系统 主要数量指标的概率规律，即研究系统的 整体性质，然后进一步研究系统的优化问 题。与这两个问题相关的还包括排队系统 的统计推断问题。(1)通过研究主要数量指标在瞬时或 平稳状态下的概率分布及其数字特征，了 解系统运行的基本特征。(2)统计推断问题，建立适当的排队 模型是排队论研究的第一步，建立模型过 程中经常会碰到如下问题：检验系统是否 达到平稳状态；检验顾客相继到达时间间 隔的相互独立性；确定服务时间的分布及 有关参数等。2.输入过程和服务时间分布58(3)系统优化问题，又称为系

16、统控制问题 或系统运营问题，其基本目的是使系统处于最 优或最合理的状态。系统优化问题包括最优设 计问题和最优运营问题，其内容很多，有最少 费用问题、服务率的控制问题、服务台的开关 策略、顾客(或服务)根据优先权的最优排序等 方面的问题。对于一般的排队系统运行情况的分析， 通常是在给定输入与服务条件下，通过求解系 统状态为n(有n个顾客)的概率Pn(t)，再进行计 算其主要的运行指标: 2.输入过程和服务时间分布591）系统中顾客数(队长)的期望值L或Ls； 2）排队等待的顾客数(排队长)的期望值 Lq； 3）顾客在系统中全部时间(逗留时间)的 期望值W或Ws；4）顾客排队等待时间的期望值Wq。排队系统中，由于顾客到达分布和服务时 间分布是多种多样的，加之服务台数。顾客源有 限无限，排队容量有限无限等的不同