第六章 排队论模型.ppt

12 排队论简介: 排队论(Queuing Theory) ,又称随机服务系统理论(Random Service System Theory), 是运筹学的一个主要分支,是一门研究拥挤现象(排队、等待)的科学。具体地说,它是在研究各种排队系统概率规律性的基础上,解决相应排队系统的最优设计和最优控制问题。主要包含以下三个方面的研究内容: (1) 性态问题,即研究各种排队系统的概率规律性,如队长、等待时间、忙期等要素满足的分布。有瞬态和稳态两种情况。(2) 最优化问题,包括最优设计下的静态最优和现有排队系统的最优运营下的动态最优。(3) 排队系统的统计推断,即判断一个给定的排队系统符合何种模型,以便进一步根据排队理论进行分析研究。前言 3 起源于 1909 年在丹麦哥本哈根电子公司工作的电话工程师 A. K. Erlang( .爱尔朗)对电话通话拥挤问题的研究工作, 其开创性论文--- 概率论和电话通讯理论则标志此理论的诞生。表明了排队论的发展最早是与电话,通信中的问题相联系的, 并到现在也还是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存管理等等各领域中均得到广泛的应用。排队论历史: 排队是我们在日常生活和生产中经常遇到的现象。例如:搭乘公共汽车;顾客到商店购买物品;病员到医院看病;旅客到售票处购买车票; 学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外, 还有大量的所谓“无形”排队现象,如几个顾客打电话到出租汽车站要求派车,如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待, 他们分散在不同地方,却形成了一个无形队列在等待派车。排队的不一定是人,也可以是物:例如:通讯卫星与地面若干待传递的信息;生产线上的原料、半成品等待加工;因故障停止运转的机器等待工人修理;码头的船只等待装卸货物;要降落的飞机因跑道不空而在空中盘旋等等。排队论具体事例: 4 上述事例中的各种问题虽互不相同,但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍, 待获得服务后离开系统。 5 模型 1 单服务台排队模型排队模型及类型根据顾客到达和服务台数,排队过程可用下列模型表示: 模型 2 单队列多服务台并联的排队模型 6 模型 3 多队列多服务台的并联排队模型模型 4 单队多个服务台的串联排队模型 7 模型 5 多队列多服务台混联网络模型纵观上述排队模型,实际上都可由下面模型加以统一描述: 称该统一模型为随机聚散服务系统。由于顾客到来的时刻和服务台提供服务的时间长短都是随机的,因此任一排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达,“散”表示顾客的离去。 8 面对拥挤现象,人们总是希望尽量设法减少排队, 通常的做法是增加服务设施,但是增加的数量越多, 人力、物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,这样对顾客会带来不良影响。顾客排队时间的长短与服务设施规模的大小,就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。 9 一、排队系统的组成与特征排队系统一般有三个基本组成部分: ; ; 。如下图所示: 排队系统的基本概念 10 1、输入过程输入即为顾客的到达,可有下列情况: 1)顾客源可能是有限的,也可能是无限的。 2)顾客是成批到达或是单个到达。 3)顾客到达间隔时间可能是随机的或确定的。 4)顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5)输入过程可以是平稳的,也可以是非平稳的。输入过程平稳的是指顾客相继到达的间隔时间分布和参数(均值、方差)与时间无关;非平稳的则是与时间相关,非平稳的处理比较困难。