运筹学排队论.ppt

《运筹学排队论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十四章排队论QueuingTheory.基本概念（掌握）输入过程和服务时间分布（掌握）泊松到达、负指数服务排队模型（掌握）其他模型（了解）排队系统的优化目标与最优化问题（了解）本章内容重点排队是我们日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要

2、车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：前言例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。前言面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。前言于是，顾客排队时间的长短与

3、服务设施规模的大小，就构成了随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论——排队论所要研究解决的问题。排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。前言排队论(QueuingTheory)，又称随机服务系统理论(R

4、andomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。前言显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。前言图1单服务台排队系统前言顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则

5、加入等待队伍，待获得服务后离开系统，见图1至图5。图2单队列——S个服务台并联的排队系统图3S个队列——S个服务台的并联排队系统前言图4单队——多个服务台的串联排队系统图5多队——多服务台混联、网络系统前言图6-6随机服务系统前言一般的排队系统，都可由下面图6加以描述。通常称由图6表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间

6、往往是事先无法确切知道的，或者说是随机的）。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。前言1.基本概念一排队系统的描述（一）系统特征和基本排队过程实际的排队系统虽然千差万别，但是它们有以下的共同特征：(1)有请求服务的人或物——顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客

7、排队较长，而另外一些时候服务员(台)又空闲无事。任何一个排队问题的基本排队过程都可以用图6表示。从图6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。1.基本概念（二）排队系统的基本组成部分通常，排队系统都有输入过程、服务规则和服务台等3个组成部分：1．输入过程．这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述—个输入过程。(1)顾客总体数，又称顾客源

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