第九章节排队论幻灯片

《第九章节排队论幻灯片》由会员分享，可在线阅读，更多相关《第九章节排队论幻灯片（133页珍藏版）》请在金锄头文库上搜索。

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

2、可以是物：,前 言,通讯卫星与地面若干待传递的信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘旋等等。,前 言,排队问题的共同特征 有要求得到某种服务的人或物。排队论里把要求服务的对象统称为“顾客” 有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员” 顾客的到达、服务的时间至少有一个是随机的，服从某种分布。,前 言,不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图6-1至图6-5。,图6

3、-1 单服务台排队系统,前 言,图6-2 单队列S个服务台并联的排队系统,图6-3 S个队列S个服务台的并联排队系统,前 言,图6-4 单队多个服务台的串联排队系统,图6-5 多队多服务台混联、网络系统,前 言,图6-6 随机服务系统,前 言,一般的排队系统，都可由下面图6-6加以描述。,面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。,前 言,排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在

4、研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,前 言,一 排队系统的描述 （一）系统特征和基本排队过程 任何一个排队问题的基本排队过程都可以用图6-6表示。从图6-6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。,1.基 本 概 念,1.基 本 概 念,（二）排队系统的基本组成部分 通常，排队系统都有输入过程、服务规则和服务台等3个组成部分： 1输入过程这是指要求服务的顾客是按怎样

5、的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述个输入过程。,1.基 本 概 念,(1)、顾客总体数(又称顾客源、输入源)。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。,1.基 本 概 念,(2)顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,1.基 本 概 念,(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行

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

7、进行服务，这是最普遍的情形。 后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,1.基 本 概 念,随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。,1.基 本 概 念,(3)混合制等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。,

8、1.基 本 概 念, 等待时间有限。顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,1.基 本 概 念, 逗留时间有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。,1.基 本 概 念,3服务台情况。服

9、务台可以从以下3方面来描述： (1) 服务台数量及构成形式 单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式, 多队多服务台并串联混合式等等。,1.基 本 概 念,(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。 (3) 服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。,1.基 本 概 念,（三）排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排

10、队模型进行描述或分类，DGKendall提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式： A/B/C/D/E/F 各符号的意义为：,1.基 本 概 念,A表示顾客相继到达间隔时间分布，常用下列符号： M表示到达过程为泊松过程或负指数分布； D表示定长输入； Ek表示k阶爱尔朗分布； G表示一般相互独立的随机分布。,1.基 本 概 念,B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。 M表示服务过程为泊松过程或负指数分布； D表示定长分布； Ek 表示k阶爱尔朗分布； G表示一般相互独立的随机分布。,1.基 本 概 念,C表

11、示服务台(员)个数： “1”则表示单个服务台，“s”(s1)表示多个服务台。 D表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 0K，当 K=s 时，说明系统不允许等待，即为损失制。K= 时为等待制系统，此时一般省略不写。K为有限整数时，表示为混合制系统。,1.基 本 概 念,E表示顾客源限额，分有限与无限两种，表示顾客源无限，此时一般也可省略不写。 F表示服务规则，常用下列符号： FCFS：表示先到先服务； LCFS：表示后到先服务； PR：表示优先权服务。,1.基 本 概 念,例如：某排队问题为 MMSFCFS 则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负

12、指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 可简记为： M/M/s,1.基 本 概 念,某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。,1.基 本 概 念,二、排队系统的主要数量指标 研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：,1.基 本 概 念,1.队长和排队长（队列长） 队长是指系统中的顾客数(排队等待的顾客

13、数与正在接受服务的顾客数之和)， 排队长是指系统中正在排队等待服务的顾客数。 队长和排队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。,1.基 本 概 念,2等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量。 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。 对这两个指标的研究是希望能确定其分布，或至少能知道顾客的平均等待时间和平均逗留时间。,1.基 本 概 念,3忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连

14、续忙的时间。这是个随机变量，它关系到服务员的服务强度。 与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。,1.基 本 概 念,除了上述几个基本数量指标外，还会用到其他一些重要的指标： 损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。,1.基 本 概 念,4.一些数量指标的常用记号 (1)主要数量指标 N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长； Nq(t)：时刻t系统中排队的顾客数，即排队长； T(t)：时刻t到达系统的顾客在系统中的逗留时间； Tq(t)：时刻t到达

15、系统的顾客在系统中的等待时间。,1.基 本 概 念,上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。 在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,1.基 本 概 念,L或Ls 平均队长，稳态系统任一时刻的顾客数的期望值； Lq 平均等待队长或队列长，稳态系统任一时刻等待服务的顾客数期望值； W或Ws 平均逗留时间，在任意时刻进入稳态系统的顾客逗留时间期望值； Wq 平均等待时间，

16、在任意时刻进入稳态系统的顾客等待时间期望值。,1.基 本 概 念,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。,1.基 本 概 念,(2)其他常用数量指标 s 系统中并联服务台的数目； 平均到达率； 1/ 平均到达间隔。 平均服务率； 1/ 平均服务时间。 服务强度，即每个服务台单位时间内的平均服务时间； 一般有 s ；,1.基 本 概 念,N 稳态系统任一时刻的状态(即系统中的顾客数)； U 顾客在稳态系统中的逗留时间； Q 顾客在稳态系统中的等待时间。 N，U，Q 都是随机变量。 Pn=PN=n：稳态系统任一时刻状态为n的概率；特别当 n = 0 时，Pn即P0，为稳态系统所有服务台全部空闲的概率