10第十章 排队论

第十章排队论1本章内容重点基本概念输入过程和服务时间分布泊松输入——指数服务排队模型其他模型选介210第十章排队论前言排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。310第十章排队论前言排队是我们在日常生活和生产中经常遇到的现象:上、下班搭乘公共汽车；顾客到商店购买物品；病人到医院看病；旅客到售票处购买车票；学生去食堂就餐等常常出现排队和等待现象。排队的不一定是人，也可以是物：410第十章排队论前言通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。510第十章排队论前言排队问题的共同特征有要求得到某种服务的人或物。排队论里把要求服务的对象统称为“顾客”有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员”顾客的到达、服务的时间至少有一个是随机的，服从某种分布。610第十章排队论前言不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。710第十章排队论前言图1单服务台排队系统810第十章排队论前言图2单队列——S个服务台并联的排队系统910第十章排队论前言图3S个队列——S个服务台的并联排队系统1010第十章排队论前言图4单队——多个服务台的串联排队系统1110第十章排队论前言图5多队——多服务台混联、网络系统1210第十章排队论前言一般的排队系统，都可由下图加以描述1310第十章排队论前言面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。服务实施过少或服务效率过低，加剧排队增加服务设施会导致服务成本上升与系统空闲矛盾1410第十章排队论前言排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。1510第十章排队论1基本概念-----排队系统的描述

系统特征和基本排队过程任何一个排队问题的基本排队过程都可以用图6表示。从图6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。1610第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分通常，排队系统都有 输入过程 服务规则 服务台等3个组成部分.1710第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述—个输入过程。1810第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:1输入过程顾客总体数(又称顾客源、输入源)顾客到达方式顾客流的概率分布，或称相继顾客到达的时间间隔的分布这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。1910第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:1输入过程顾客总体数(又称顾客源、输入源)顾客到达方式顾客流的概率分布，或称相继顾客到达的时间间隔的分布描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。2010第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:1输入过程顾客总体数(又称顾客源、输入源)顾客到达方式顾客流的概率分布，或称相继顾客到达的时间间隔的分布可以理解为在一定的时间间隔内到达K个顾客(K=1、2、..)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。举例2110第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:2服务规则指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。2210第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:2服务规则损失制等待制混合制如果顾客到达排队系统时，所有服务台都已被占用，那么他们就自动离开系统永不再来。如拨打电话占线后挂断电话。2310第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:2服务规则损失制等待制混合制当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：先来先服务、后来先服务、随机服务、优先权服务2410第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:2服务规则损失制等待制混合制等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限、等待时间有限、逗留时间有限2510第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:3服务台情况服务台数量及构成形式服务方式服务时间的分布①单队——单服务台式；②单队——多服务台并联式；③多队——多服务台并联式；④单队——多服务台串联式；⑤单队——多服务台并串联混合式；⑥多队——多服务台并串联混合式…2610第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:3服务台情况服务台数量及构成形式服务方式服务时间的分布指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。2710第十章排队论1基本概念-----排队系统的描述排队系统的基本组成部分:3服务台情况服务台数量及构成形式服务方式服务时间的分布在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。2810第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，D．G．Kendall提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：X/Y/Z/A/B/C

各符号的意义为：2910第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类X—顾客相继到达间隔时间分布，常用下列符号：M——表示到达过程为泊松过程或负指数分布；D——表示定长输入；Ek——表示k阶爱尔朗分布；G——表示一般相互独立的随机分布。3010第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类Y—服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M——表示服务过程为泊松过程或负指数分布；D——表示定长分布；Ek——表示k阶爱尔朗分布；G——表示一般相互独立的随机分布。3110第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类Z—表示服务台(员)个数：“1”则表示单服务台，“s”(s＞1)表示多服务台。A—系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则0<K<∞，当K=s时，说明系统不允许等待，即为损失制。K=∞时为等待制系统，此时∞一般省略不写。K为有限整数时，表示为混合制系统。3210第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类B—表示顾客源限额，分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。C—表示服务规则，常用下列符号：FCFS：表示先到先服务；LCFS：表示后到先服务；PR：表示优先权服务。3310第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类例如：某排队问题为

M／M／S／∞／∞／FCFS

则表示顾客相继到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。可简记为：M/M/s3410第十章排队论1基本概念-----排队系统的描述排队系统的描述符号与分类 某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务台的等待制系统。3510第十章排队论1基本概念-----排队系统的主要数量指标队长和排队长（队列长）队长-是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)，排队长-是指系统中正在排队等待服务的顾客数。队长和排队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。3610第十章排队论1基本概念-----排队系统的主要数量指标等待时间和逗留时间等待时间指从顾客到达时刻起到开始接受服务止这段时间，是随机变量。逗留时间指从顾客到达时刻起到接受服务完成止这段时间，也是随机变量。对这两个指标的研究是希望能确定其分布，或至少能知道顾客的平均等待时间和平均逗留时间。3710第十章排队论1基本概念-----排队系统的主要数量指标忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。3810第十章排队论1基本概念-----排队系统的主要数量指标其它指标除了上述几个基本数量指标外，还会用到其他一些重要的指标：损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。3910第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号N(t)：时刻t系统中的顾客数(系统的状态)，即队长；Nq(t)：时刻t系统中排队的顾客数，即排队长；T(t)：时刻t到达系统的顾客在系统中的逗留时间；Tq(t)：时刻t到达系统的顾客在系统中的等待时间。4010第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。4110第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号L或Ls——平均队长，稳态系统任一时刻的顾客数的期望值；Lq——平均等待队长或队列长，稳态系统任一时刻等待服务的顾客数期望值；W或Ws——平均逗留时间，在任意时刻进入稳态系统的顾客逗留时间期望值；Wq——平均等待时间，在任意时刻进入稳态系统的顾客等待时间期望值。这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。4210第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号s——系统中并联服务台的数目；λ——平均到达率；1/λ——平均到达间隔。μ

——平均服务率；1/μ——平均服务时间。ρ——服务强度，即每个服务台单位时间内的平均服务时间；

一般有ρ=λ/(sμ)4310第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号N——稳态系统任一时刻的状态(系统中的顾客数)；N是随机变量。Pn=P{N=n}：稳态系统任一时刻状态为n的概率；特别当n=0时，Pn即P0，为稳态系统所有服务台全部空闲的概率。4410第十章排队论1基本概念-----排队系统的主要数量指标一些数量指标的常用记号

对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：λe——有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值），不同于λ

对于等待制的排队系统，有λe＝λ4510第十章排队论1基本概念-----输入过程和服务时间分布输入过程由前所述，输入过程是描述各种类型的顾客以怎样的规律到达系统，可以用相继两顾客到达时间间隔ξ或时间段t内到达的顾客数来描述系统输入特征。主要输入过程有：定长输入指顾客有规则地等距到达，每隔时间α到达一个顾客。这时相继顾客到达间隔ξ的分布函数F(t)为：4610第十章排队论1基本概念-----输入过程和服务时间分布输入过程泊松(poisson)输入又称最简流(普阿松流),满足下面3个条件称为最简流。平稳性。输入过程是平稳的，指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。4710第十章排队论1基本概念-----输入过程和服务时间分布输入过程无后效性。指在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的。4810第十章排队论1基本概念-----输入过程和服务时间分布输入过程单个性又称普通性。指在充分小的时段内最多到达一个顾客。4910第十章排队论1基本概念-----输入过程和服务时间分布输入过程泊松(poisson)输入因为泊松流实际应用最广，也最容易处理，因而研究得也较多．可以证明，对于泊松流，在长度为t的时间内到达n个顾客的概率服从泊松分布，均值λt，方差λt，即λ—单位时间内平均到达的顾客数。5010第十章排队论1基本概念-----输入过程和服务时间分布输入过程泊松(poisson)输入对一段时间内到达顾客数目进行统计和分析不方便，实际中往往对顾客相继到达时间进行统计和分析，若顾客到达服从泊松分布，可以证明，其相继到达时间间隔服从均值为1/λ，方差为1/λ2的负指数分布，其分布函数和密度为：5110第十章排队论1基本概念-----输入过程和服务时间分布输入过程一般独立输入 相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例5210第十章排队论1基本概念-----输入过程和服务时间分布输入过程一般独立输入 排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为：5310第十章排队论1基本概念-----输入过程和服务时间分布服务时间分布定长分布负指数分布爱尔郎分布一般独立分布多个服务台的服务分布5410第十章排队论1基本概念-----输入过程和服务时间分布服务时间分布负指数分布服务时间满足参数为μ的负指数分布，其分布密度和分布函数为：1/μ为平均服务时间，μ为单位时间平均服务人数。5510第十章排队论2M/M/s等待制排队模型单服务台模型单服务台等待制模型M/M/1/∞指：顾客的相继到达时间服从参数为λ的负指数分布，服务台个数1，服务时间V服从参数为μ的负指数分布，系统空间无限，允许永远排队。5610第十章排队论2M/M/s等待制排队模型单服务台模型服务强度：λ单位时间到达的顾客数μ单位时间服务完的顾客数平均队长L,平均排队长Lq：平均逗留时间W,平均等待时间Wq：平衡状态下，系统中顾客为n的概率：5710第十章排队论2M/M/s等待制排队模型单服务台模型平均忙期：λ单位时间到达的顾客数μ单位时间服务完的顾客数平均闲期：5810第十章排队论2M/M/s等待制排队模型例：一个铁路列车编组站，待编列车到达时间间隔服从负指数分布，平均到达2列/小时；服务台是编组站，编组时间服从负指数分布，平均20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平稳状态下系统中列车的平均数；每一列车的平均停留时间；等待编组的列车的平均数；每列车平均等待编组时间。如果列车因站中的2股道均被占用而停在站外或前方站时，每列车的费用为a元/小时，求每天由于列车在站外等待而造成的损失。5910第十章排队论2M/M/s等待制排队模型解：λ=2μ=3ρ=2/3<1可达平稳状态系统中列车的平均数：列车的平均停留时间：等待编组的列车的平均数：每列车平均等待编组时间：6010第十章排队论2M/M/s等待制排队模型解：λ=2μ=3ρ=2/3<1可达平稳状态列车的平均停留时间：每列车平均延误时间：每天由于列车延误费用：6110第十章排队论2M/M/s等待制排队模型例：某理发店只有一个理发师，来理发的顾客到达过程为Poisson流，平均4人/小时；理发时间服从负指数分布，平均需要6分钟。求（1）理发店空闲的概率；（2）店内恰有3各顾客的概率；（3）店内至少有一个顾客的概率；（4）店内的平均顾客数；（5）每位顾客在店内的平均逗留时间；（6）等待服务的平均顾客数；（7）每位顾客平均等待服务时间；（8）顾客在店内等待时间超过10分钟的概率。6210第十章排队论2M/M/s等待制排队模型解：λ=4μ=10ρ=4/10<0.4可达平稳状态店内空闲的概率：店内恰有3个顾客的概率：店内至少有一个顾客的概率：店内的平均顾客数：6310第十章排队论2M/M/s等待制排队模型解：λ=4μ=10ρ=4/10<0.4可达平稳状态每位顾客平均逗留时间：等待服务的平均顾客数：顾客平均等待时间：顾客逗留超过10分钟的概率：课本P316，顾客在系统中的逗留时间服从参数为μ-λ的负指数分布，即P(T>t)=e-(μ-λ)t,t>=06410第十章排队论2M/M/s等待制排队模型多服务台模型多服务台等待制模型M/M/s/∞指：顾客单个到达，相继到达间隔服从参数为λ的负指数分布，每个服务台的服务时间相互独立，且服从参数为μ的负指数分布。顾客到达时有空闲的服务台可以马上接收服务，否则排成一个队列等待，等待空间无限。6510第十章排队论2M/M/s等待制排队模型多服务台模型服务强度：平均队长L,平均排队长Lq：平均逗留时间W,平均等待时间Wq：平衡状态下，系统中顾客为n的概率：6610第十章排队论2M/M/s等待制排队模型例：考虑一个医院急诊室管理的问题。据统计，急诊病人相继到达的时间间隔服从负指数分布，平均半小时一个；医生处理一个病人的时间业服从负指数分布，平均20分钟。该急诊室已有一个医生，考虑是否需要增加一个医生。6710第十章排队论2M/M/s等待制排队模型解：本问题为M/M/S排队问题，参数为λ=2μ=3ρ=2/3，s=1,2运用前述单服务台（s=1），多服务台(s=2)计算得到下表的对比结果63%94%63%94%75%6810第十章排队论2M/M/s等待制排队模型例：一个大型露天矿山，考虑修建矿石卸位的个数，问题是一个还是两个。估计运矿车将按Poisson流到达，平均每小时15辆；卸矿石时间服从负指数分布，平均3分钟一辆。又知每辆运送卡车售价8万元，修建一个卸位投资14万。6910第十章排队论2M/M/s等待制排队模型解：用M/M/S排队模型分析λ=15μ=20ρ=0.75，s=1,2比较指标1个卸位2个卸位平均卡车数L30.87平均等待时间W12min3.5min增加了14万的投资，节约了（3-0.87）辆车=17.04万，建造2个卸位合理7010第十章排队论M/M/s型系统和s个M/M/1型系统的比较某售票处有3个窗口，顾客到达服从Poisson过程，平均每分钟0.9人，售票时间服从负指数分布，平均每分钟0.4人（1）顾客到达后排成1对，依次向空闲的窗口购票;（2）顾客到达后在每个窗口各排一对，进入队列后不能换对，比较两种方式的效率。7110第十章排队论M/M/s型系统和s个M/M/1型系统的比较窗口1窗口2窗口3窗口1窗口2窗口3μ=0.4μ=0.4μ=0.4λ=0.9s=3μ=0.4μ=0.4μ=0.4λ=0.9λ=0.3λ=0.3λ=0.37210第十章排队论M/M/s型系统和s个M/M/1型系统的比较指标M/M/33个M/M/1服务台空闲概率0.07480.25（每个子系统）顾客必须等待概率0.570.75平均排队长1.72.25（每个子系统）平均队长3.959（整个系统）平均逗留时间4.3910平均等待时间1.897.57310第十章排队论3M/M/s混合制排队模型单服务台模型单服务台混合制模型M/M/1/K指：顾客单个到达，相继到达间隔服从参数为λ的负指数分布，服务台1个，服务时间V服从参数为μ的负指数分布，系统空间为K。7410第十章排队论3M/M/s混合制排队模型单服务台模型-系统指标7510第十章排队论例某修理站只有一名修理工，站内最多停放4台待修机器，设待修机器按泊松流到达修理站，平均每分钟到达1台，修理时间服从负指数分布，平均1.25分钟修理1台，求系统有关指标。解：该系统为M/M/1/4排队系统，其中7610第十章排队论3M/M/s混合制排队模型多服务台模型多服务台混合制模型M/M/s/K指：顾客相继到达间隔服从参数为λ的负指数分布，服务台s个，每个服务台服务时间相互独立，且服务时间V服从参数为μ的负指数分布，系统空间为K。7710第十章排队论3排队系统的优化从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是服务费用，它是服务水平的递增函数；另一个是顾客等待的机会损失(费用)，它是服务水平的递减函数。两者的总和呈一条U形曲线。费用服务水平等待费用服务费用总费用7810第十章排队论3排队系统的