第08章 排队论 运筹学

《第08章 排队论 运筹学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章排队论1本章内容重点排队论基本概念基本问题与求解思路泊松输入——指数服务排队模型其他模型选介排队系统的优化2排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。前言3排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景

2、。前言41.排队论基本概念排队是我们在日常生活和生产中经常遇到的现象:上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。5排队的不一定是人，也可以是物：通讯卫星与地面待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。61.1排队系统特征与基本过程1)排队问题的共同特征①有要求某种服务的人或物。排队论里把要求服务的对象统称为“顾客”②有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员”③顾客的到达、服务的

3、时间至少有一个是随机的，服从某种分布。72)基本排队过程任何一个排队问题的基本排队过程都可以用图8-1表示：每个顾客由顾客源按照一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务后的顾客立即离开。8一般排队系统都可由下图（图8-1）描述图8-1随机服务系统排队系统示意图9面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。10通常，排队系统都有

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

5、程131)输入过程③顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。流可以理解为在一定的时间间隔内到达k个顾客(k=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。14指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。①损失制。如果顾客到达排队系统时，所有服务台都已被占用，那么他们就自动离开系统永不再来。2)服务规则15②等待制。当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时，常

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

7、后来的顾客就自动离去，另求服务，即系统的容量是有限的。2)服务规则18等待时间有限。顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。2)服务规则（混合制-续）19逗留时间有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，就不可能再被击落了。注意