文档介绍：第四章排队论
排队论(Queuing Theory),又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说,它是在研究各种排队系统概率规律性的基础上,解决相应排队系统的最优设计和最优控制问题。
排队是我们在日常生活和生产中经常遇到的现象。例如,上、下班搭乘公共汽车;顾客到商店购买物品;病员到医院看病;旅客到售票处购买车票;学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外,还有大量的所谓“无形”排队现象,如几个顾客打电话到出租汽车站要求派车,如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待,他们分散在不同地方,却形成了一个无形队列在等待派车。排队的不一定是人,也可以是物:
例如,通讯卫星与地面若干待传递的信息;生产线上的原料、半成品等待加工;因故障停止运转的机器等待工人修理;码头的船只等待装卸货物;要降落的飞机因跑道不空而在空中盘旋等等。
显然,上述各种问题虽互不相同,但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图6-1至图6-5。
不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图6-1至图6-5。

图6-1 单服务台排队系统
图6-2 单队列——S个服务台并联的排队系统
图6-3 S个队列——S个服务台的并联排队系统
图6-4 单队——多个服务台的串联排队系统
图6-5 多队——多服务台混联、网络系统
一般的排队系统,都可由下面图6-6加以描述。
图6-6 随机服务系统
通常称由图6-6表示的系统为一随机聚散服务系统,任一排队系统都是一个随机聚散服务系统。这里,“聚”表示顾客的到达,“散”表示顾客的离去。所谓随机性则是排队系统的一个普遍特点,是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的,或者说是随机的。一般来说,排队论所研究的排队系统中,顾客到来的时刻和服务台提供服务的时间长短都是随机的,因此这样的服务系统被称为随机服务系统。
面对拥挤现象,人们总是希望尽量设法减少排队,通常的做法是增加服务设施。但是增加的数量越多,人力、物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,这样对顾客会带来不良影响。于是,顾客排队时间的长短与服务设施规模的大小,就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾,这就是随机服务系统理论
——排队论所要研究解决的问题。
排队论是1909年由丹麦工程师爱尔朗()在研究电活系统时创立的,几十年来排队论的应用领域越来越广泛,理论也日渐完善。特别是自二十世纪60年代以来,由于计算机的飞速发展,更为排队论的应用开拓了宽阔的前景。
第一节基本概念
一、排队系统的描述
(一)系统特征和基本排队过程
实际的排队系统虽然千差万别,但是它们
有以下的共同特征:
(1)有请求服务的人或物——顾客;
(2)有为顾客服务的人或物,即服务员或服务台;
(3)顾客到达系统的时刻是随机的,为每一位顾客提供服务的时间是随机的,因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长,而另外一些时候服务员(台)又空闲无事。
(二)排队系统的基本组成部分
通常,排队系统都有输入过程、服务规则和服务台等3个组成部分:
,—个输入过程。
(1)顾客总体数,又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的,也可以是无限的。例如,到售票处购票的顾客总数可以认为是无限的,而某个工厂因故障待修的机床则是有限的。
(2)顾客到达方式。这是描述顾客是怎样来到系统的,他们是单个到达,还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客,那么这种顾客则是成批到达的。
(3)顾客流的概率分布,或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时,首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K