第六章-排队论模型ppt课件.ppt

1 排队论简介： 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是运筹学的一个主要分支，是一门研究拥挤现象(排队、等待)的科学具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题主要包含以下三个方面的研究内容： (1)性态问题，即研究各种排队系统的概率规律性，如队长、等待时间、忙期等要素满足的分布有瞬态和稳态两种情况 (2)最优化问题，包括最优设计下的静态最优和现有排队系统的最优运营下的动态最优 (3)排队系统的统计推断，即判断一个给定的排队系统符合何种模型，以便进一步根据排队理论进行分析研究 前前 言言2 起源于起源于19091909年在丹麦哥本哈根电子公司工作的工程年在丹麦哥本哈根电子公司工作的工程师师A. K. A. K. Erlang(A.KErlang(A.K. .爱尔朗爱尔朗) )对通话拥挤问题的研究工作，对通话拥挤问题的研究工作，其开创性论文其开创性论文-概率论和通讯理论则标志此理论的诞生概率论和通讯理论则标志此理论的诞生表明了排队论的发展最早是与，通信中的问题相联系的，表明了排队论的发展最早是与，通信中的问题相联系的，并到现在也还是排队论的传统的应用领域。

近年来在计算机通并到现在也还是排队论的传统的应用领域近年来在计算机通讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存管理等等各领域中均得到广泛的应用管理等等各领域中均得到广泛的应用 排队论历史： 排排队队是是我我们们在在日日常常生生活活和和生生产产中中经经常常遇遇到到的的现现象象例例如如：搭搭乘乘公公共共汽汽车车；顾顾客客到到商商店店购购买买物物品品；病病员员到到医医院院看看病病；旅旅客客到到售售票票处处购购买买车车票票；学学生生去去食食堂堂就就餐餐等等就就常常常常出出现现排排队队和和等等待待现现象象除除了了上上述述有有形形的的排排队队之之外外，还还有有大大量量的的所所谓谓“无无形形”排排队队现现象象，如如几几个个顾顾客客打打电话到到出出租租汽汽车车站站要要求求派派车车，如如果果出出租租汽汽车车站站无无足足够够车车辆辆、则则部部分分顾顾客客只只得得在在各各自自的的要要车车处处等等待待，他他们们分分散散在在不不同同地地方方，却却形形成成了了一一个个无无形形队队列列在在等等待待派派车车排排队队的的不不一一定定是是人人，也也可可以以是是物物：例例如如：通通讯讯卫卫星星与与地地面面若若干干待待传传递递的的信信息息；生生产产线线上上的的原原料料、半半成成品品等等待待加加工工；因因故故障障停停止止运运转转的的机机器器等等待待工工人人修修理理；码码头头的的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。

船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等 排队论具体事例： 3 上述事例中的各种问题虽互不相同，但却都上述事例中的各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或有要求得到某种服务的人或物和提供服务的人或机构排队论里把要求服务的对象统称为机构排队论里把要求服务的对象统称为“顾客顾客”, ,而把提供服务的人或机构称为而把提供服务的人或机构称为“服务台服务台”或或“服务员服务员”不同的顾客与服务组成了各式各样的不同的顾客与服务组成了各式各样的服务系统顾客为了得到某种服务而到达系统、服务系统顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统等待队伍，待获得服务后离开系统4模型模型1 1 单服务台排队模型单服务台排队模型排队模型及类型排队模型及类型 根据顾客到达和服务台数，排队过程可用下列模型表示：模型模型2 2 单队列多服务台并联的排队模型单队列多服务台并联的排队模型5模型模型3 3 多队列多服务台的并联排队模型多队列多服务台的并联排队模型模型模型4 4 单队多个服务台的串联排队模型单队多个服务台的串联排队模型6模型模型5 5 多队列多服务台混联网络模型多队列多服务台混联网络模型纵观上述排队模型，实际上都可由下面模型加以统一描述：纵观上述排队模型，实际上都可由下面模型加以统一描述： 称该统一模型为随机聚散服务系统。

称该统一模型为随机聚散服务系统由于由于顾客到来的时刻和服务台提顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此供服务的时间长短都是随机的，因此任一排队系统都是一个随机聚散任一排队系统都是一个随机聚散服务系统服务系统 “聚聚”表示顾客的到达表示顾客的到达, ,“散散”表示顾客的离去表示顾客的离去7 面对拥挤现象，人们总是希望尽量设法减少排队，面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施，但是增加的数量越多，人通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响客会带来不良影响 顾客排队时间的长短与服务设施规模的大小，就构顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾成了设计随机服务系统中的一对矛盾 如何做到既保证一定的服务质量指标，又使服务设如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。

这就是随机服务系统理论费用大小这对矛盾这就是随机服务系统理论排队排队论所要研究解决的问题论所要研究解决的问题8 一、排队系统的组成与特征一、排队系统的组成与特征 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构如下图所服务机构如下图所示：示： 排队系统的基本概念排队系统的基本概念91、输入过程 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况： 1 1）顾客源可能是有限的，也可能是无限的顾客源可能是有限的，也可能是无限的 2 2）顾客是成批到达或是单个到达顾客是成批到达或是单个到达 3 3）顾客到达间隔时间可能是随机的或确定的顾客到达间隔时间可能是随机的或确定的 4 4）顾客到达可能是相互独立或关联的所谓独立）顾客到达可能是相互独立或关联的所谓独立就是以前顾客的到达对以后顾客的到达无影响就是以前顾客的到达对以后顾客的到达无影响 5 5）输入过程可以是平稳的，也可以是非平稳的输入过程可以是平稳的，也可以是非平稳的输入过程平稳的是指顾客相继到达的间隔时间分布和输入过程平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。

间相关，非平稳的处理比较困难10 这是指服务台从队列中选取顾客进行服务的顺这是指服务台从队列中选取顾客进行服务的顺序可以分为序可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类 (1)(1)损失制这是指如果顾客到达排队系统时，这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来动离开系统永不再来 典型例子是，如拔号后出现忙音，顾客不典型例子是，如拔号后出现忙音，顾客不愿等待而自动挂断，如要再打，就需重新拔愿等待而自动挂断，如要再打，就需重新拔号，这种服务规则即为损失制号，这种服务规则即为损失制 2 2、排队规则、排队规则11 (2)(2)等等待待制制指指当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都不空，顾客加入排队行列等待服务都不空，顾客加入排队行列等待服务 例如，排队等待售票，故障设备等待维修等例如，排队等待售票，故障设备等待维修等 等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如下四种规则：如下四种规则： 先先到到先先服服务务（FCFS FCFS ）。

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

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

时，混合制即成为等待制163 3、服务台、服务台 服务台可以从以下3方面来描述： (1) 服务台数量及构成形式服务台数量及构成形式从数量上说，服务台有单服务台和多服务台之分从构成形式上看，服务台有：单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及多队列多服务台并串联混合式等等 如之前的分类模型图所示如之前的分类模型图所示17 (2) 服务方式服务方式这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种如公共汽车一次就可装载一批乘客就属于成批服务 (3) 服务时间的分布服务时间的分布一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所。