《数学建模之排队论教学内容课件》由会员分享，可在线阅读，更多相关《数学建模之排队论教学内容课件（94页珍藏版）》请在金锄头文库上搜索。
1、12 排排队队论论（queuing),也也称称随随机机服服务务系系统统理理论论，是是运筹学的一个主要分支。运筹学的一个主要分支。 1909年年，丹丹麦麦哥哥本本哈哈根根电电子子公公司司电电话话工工程程师师A. K. Erlang的的开开创创性性论论文文“概概率率论论和和电电话话通通讯讯理理论论”标标志志此此理理论论的的诞诞生生。排排队队论论的的发发展展最最早早是是与与电电话话，通通信信中中的的问问题题相相联联系系的的，并并到到现现在在是是排排队队论论的的传传统统的的应应用用领领域域。近近年年来来在在计计算算机机通通讯讯网网络络系系统统、交交通通运运输输、医医疗疗卫卫生生系系统统、库库存存管管理
2、理、作作战战指指挥挥等等各各领领域中均得到应用。域中均得到应用。38 排队论排队论8-1 前言前言8-2 基基 本本 概概 念念8-3 输入过程和服务时间分布输入过程和服务时间分布8-4 泊松输入泊松输入指数服务排队模型指数服务排队模型8-5 M/M/1 无限源系统无限源系统8-6 系统容量有限的排队系统系统容量有限的排队系统8-7 顾客源有限的排队系统顾客源有限的排队系统4排排队队是是我我们们在在日日常常生生活活和和生生产产中中经经常遇到的现象。常遇到的现象。 例如，上、下班搭乘公共汽车；例如，上、下班搭乘公共汽车； 顾客到商店购买物品；顾客到商店购买物品； 病员到医院看病；病员到医院看病；
3、 旅客到售票处购买车票；旅客到售票处购买车票； 学学生生去去食食堂堂就就餐餐等等就就常常常常出出现现排排队队和和等等待待现象。现象。前前 言言5 除除了了上上述述有有形形的的排排队队之之外外，还还有有大大量量的所谓的所谓“无形无形”排队现象。排队现象。 如如几几个个顾顾客客打打电电话话到到出出租租汽汽车车站站要要求求派派车车，如如果果出出租租汽汽车车站站无无足足够够车车辆辆、则则部部分分顾顾客客只只得得在在各各自自的的要要车车处处等等待待，他他们们分分散散在在不不同同地地方方，却却形形成成了了一一个个无无形形队列在等待派车。队列在等待派车。 前前 言言6 排队的不一定是人，也可以是物：排队的不
4、一定是人，也可以是物： 例例如如，通通讯讯卫卫星星与与地地面面若若干干待待传传递递的的信息；信息；生产线上原料、半成品等待加工；生产线上原料、半成品等待加工；因因故故障障停停止止运运转转的的机机器器等等待待修修理理；码码头头的船只等待装卸货物；的船只等待装卸货物； 要要降降落落的的飞飞机机因因跑跑道道不不空空而而在在空空中中盘盘旋等等。旋等等。前前 言言7 上上述述各各种种问问题题虽虽互互不不相相同同，但但却却都都有有要要求求得得到到某某种种服服务务的的人人或或物物和和提提供供服服务务的的人或机构。人或机构。排排队队论论里里把把要要求求服服务务的的对对象象统统称称为为“顾顾客客”, ,提提供供
5、服服务务的的人人或或机机构构称称为为“服服务务台台”或或“服务员服务员”。前前 言言8 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图8-1至图8-5。图图8-1 8-1 单服务台排队系统单服务台排队系统前前 言言9图图8-2 8-2 单队列单队列S S个服务台并联的排队系统个服务台并联的排队系统图图8-3 S8-3 S个队列个队列S S个服务台的并联排队系统个服务台的并联排队系统前前 言言10图图8-4 8-4 单队单队多个服务台的串联排队系统多个服务台的串联排队系统图图8-5 8-5
6、多队多队多服务台混联网络系统多服务台混联网络系统前前 言言11图图8-6 8-6 随机服务系统随机服务系统前前 言言一一般般的的排排队队系系统统，都都可可由由下下面图加以描述。面图加以描述。通常称由图通常称由图8-68-6表示的系统为一随机聚散服务系统。表示的系统为一随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚聚”表示顾客的到达，表示顾客的到达，“散散”表示顾客的离去表示顾客的离去。12 面面对对拥拥挤挤现现象象，人人们们总总是是希希望望尽尽量量设设法法减少排队，通常的做法是增加服务设施。减少排队，通常的做法是增加服务设施。 但但是是增增加
7、加的的数数量量越越多多，人人力力、物物力力的的支支出就越大，甚至会出现空闲浪费。出就越大，甚至会出现空闲浪费。 如如果果服服务务设设施施太太少少，顾顾客客排排队队等等待待的的时时间就会很长，这样对顾客会带来不良影响。间就会很长，这样对顾客会带来不良影响。前前 言言13 顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大大小小，就就构构成成了了设设计计随随机机服服务务系系统统中中的的一一对对矛盾。矛盾。 如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客排队时间与服务设施费用大小这对矛
8、盾。客排队时间与服务设施费用大小这对矛盾。 这这就就是是随随机机服服务务系系统统理理论论排排队队论论所所要研究解决的问题。要研究解决的问题。前前 言言14 一、排队系统的组成与特征一、排队系统的组成与特征 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。服务机构。8-2 8-2 排队系统的基本概念排队系统的基本概念15 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况： 1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。顾客是成
9、批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（输入过程可以是平稳的（stationarystationary）或说）或说是对时间齐次的（是对时间齐次的（Homogeneous in timeHomogeneous in time），也可以），也可以是非平稳的。输入过程平稳的指顾客相继到达的间是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布
10、和参数（均值、方差）与时间无关；非隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。平稳的则是与时间相关，非平稳的处理比较困难。1. 1. 输入过程输入过程16这是指服务台从队列中选取顾客进行服务的顺序。这是指服务台从队列中选取顾客进行服务的顺序。 可以分为可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类。大类。 (1)(1)损损失失制制。这这是是指指如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用，那那么么他他们们就就自动离开系统永不再来。自动离开系统永不再来。 典典型型例例子子是是
11、，如如电电话话拔拔号号后后出出现现忙忙音音，顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电话话，如如要要再再打打，就就需需重重新新拔号，这种服务规则即为损失制。拔号，这种服务规则即为损失制。 2 2. . 排队规则排队规则17 (2)(2)等等待待制制。指指当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都不空，顾客加入排队行列等待服务。都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。例如，排队等待售票，故障设备等待维修等。 等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有有如下四种规则：如下四种规则： 先先到到先先服服务务（F
12、CFS FCFS ）。按按顾顾客客到到达达的的先先后后顺顺序对顾客进行服务，这是最普遍的情形。序对顾客进行服务，这是最普遍的情形。 后后到到先先服服务务（LCFSLCFS）。仓仓库库中中迭迭放放的的钢钢材材，后迭放上去的都先被领走，就属于这种情况。后迭放上去的都先被领走，就属于这种情况。 2 2. . 排队规则排队规则18 随随机机服服务务（RAND） 。即即当当服服务务台台空空闲闲时时，不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务，如如电电话话交交换换台台接接通通呼呼叫叫电电话话就就是一例。是一例。 优优先先权权服服务务（PR）。如如老老人人、儿儿童童
13、先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等，均属于此种服务规则。均属于此种服务规则。 2 2. . 排队规则排队规则19 (3)(3)混混合合制制这这是是等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队队，但但又又不不允允许许队队列列无限长下去。具体说来，大致有三种：无限长下去。具体说来，大致有三种： 队队长长有有限限。当当排排队队等等待待服服务务顾顾客客人人数数超超过过规定数量时，后来顾客就自动离去，另求服务。规定数量时，后来顾客就自动
14、离去，另求服务。如水库的库容、旅馆的床位等都是有限的如水库的库容、旅馆的床位等都是有限的。 2 2. . 排队规则排队规则20 等等待待时时间间有有限限。即即顾顾客客在在系系统统中中的的等等待待时时间间不不超超过过某某一一给给定定的的长长度度T T，当当等等待待时时间超过间超过T T时，顾客自动离去，不再回来。时，顾客自动离去，不再回来。 如如易易损损坏坏的的电电子子元元器器件件的的库库存存问问题题，超过一定存储时间被自动认为失效。超过一定存储时间被自动认为失效。 又又如如顾顾客客到到饭饭馆馆就就餐餐，等等了了一一定定时时间间后后不愿再等而自动离去另找饭店用餐。不愿再等而自动离去另找饭店用餐。
15、 2 2. . 排队规则排队规则21 逗逗留留时时间间( (等等待待时时间间与与服服务务时时间间之之和和) )有限。有限。 例例如如用用高高射射炮炮射射击击敌敌机机，当当敌敌机机飞飞越越高高射射炮炮射射击击有有效效区区域域的的时时间间为为t t时时，若若在在这这个个时时间间内未被击落，也就不可能再被击落了。内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是不难注意到，损失制和等待制可看成是混合制的特殊情形，如记混合制的特殊情形，如记c c为系统中服务台的为系统中服务台的个数，则当个数，则当K=cK=c 时，混合制即成为损失制；时，混合制即成为损失制；当当K=K=时，混合制即
16、成为等待制。时，混合制即成为等待制。 2 2. . 排队规则排队规则223 3. . 服务机构服务机构 1 1）服服务务机机构构可可以以是是单单服服务务员员和和多多服服务务员员服服务务，这这种种服服务务形形式式与与队队列列规规则则联联合合后后形形成成了了多多种种不不同同队队列列，不不同同形形式式的的排排队队服服务务机机构构。如如前前图图8-18-1到到8-8-5 5： 2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。 3)3)服务时间分为确定型和随机型。服务时间分为确定型和随机型。 4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。23 上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数 D.G.KendallD.G.Kendall，19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号( (适用于并列服务台适用于并列服务台) )即：即：X/Y/Z:d/e/fX/Y/
