第10章 排队论.doc

第10章 排队论.doc第十章* 排队论
排队论(queuing theory)是一门应用十分广泛的运筹学分支,它在各种存在等待情形的环境中都有非常成功的应用。尽管人们有时可能并不太在意等待时间的长短,但在许多商务活动中我们必须给顾客的等待时间以充分的重视。绝大多数大型零售店的设计其实就是平衡顾客方便度和企业运营效率的产物,这很好地解释了为什么一个超级市场可能会有十几个收银通道,尽管在大多数时间里可能只有两三个在运作。零售商不敢让顾客在队伍中等待太长的时间,因为时间对顾客来说可能是十分宝贵的,如果等待时间过长,他们完全有可能转向自己的竞争者。
在管理科学或运筹学中,等待的队伍被称为队列(queue),排队论作为运筹学的一个重要分支在过去的几十年里得到了长足的发展,代表特定环境的模型的数量稳步增加。作为最早的定量优化方法之一,排队论的起源可以追溯到1909年爱尔朗(A. K. Erlang, a Danish telephone engineer)发表的一篇论文,从那时起爱尔朗的名字就与概率排队模型紧密联系了在一起,该论文的发表为后来排队论的发展奠定了坚实的基础。
排队模型的目的就是要规划一种为顾客提供服务的方式以实现一定的运营效率,它并不象前面已经遇到的一些模型(如线性规划模型、存贮模型)那样追逐一个最小成本或最大收益目标。具体来讲,排队模型的目的就是要确定排队系统的各项特征,如平均等待时间、平均队长等;或者是构建一个服务系统以满足特定的顾客服务水平。这些平均值是系统对顾客服务水平的标志,在后续的成本分析中将发挥重要的作用。
§1排队系统综述
在日常生活和生产中,人们会经常碰到各种各样的排队系统,如道路红绿灯系统、超市的收银系统、电话通讯系统等。一些排队系统的构成十分明显,而另一些排队系统的构成可能很模糊。如从广州往北京打电话,由于受广州与北京之间信道通过能力的限制,同一时间通话的人数是有限的;因此,当要求通话人数超过这一限制时,就不得不等待,虽然打电话的人分散在全市的各个角落,彼此互不见面,但他们与长话台一起构成一个服务系统,他们在长话台前形成一个无形的队伍,其实这种无形的队伍与超市收银系统中的有形队伍都可以构成排队系统中的队列。
在排队系统中总是存在一组服务设施(service facility),有许多顾客(customer)随机地来到该系统要求得到服务,服务完毕后即自动离去。如果顾客到达时有服务设施空闲,则到达的顾客即刻得到服务,否则顾客将排队等待或离去。通常我们会自然地认为顾客就是来到服务系统准备接受服务的人,然而在排队系统中顾客不该受到任何限制,可以是人,也可以是物。汽车修理厂等待维修的汽车、机场等待降落的飞机都可以构成排队系统中的顾客。在排队系统中,服务设施同样可以是人、物或者人和物的集合。
如果顾客按固定的时间间隔到达服务系统,服务设施用在每个顾客身上的服务时间也是固定的,就象工厂流水线的生产那样有固定的节拍,那么这类服务系统的设计是十分简便的。但在绝大多数的服务系统中,顾客的到达是随机的,顾客的服务时间也是随机的,这就意味着排队论有着广泛的应用前景。
排队系统的基本构成
一个排队系统由输入、队列、服务台和输出四部分构成,可以用图10-1来加以描述。
输出
输入
顾客
总体
队列
服务台
图10-1 排队系统构成示意图

输入描述的是顾客出现在排队系统中的方式,人们通常用某种带有任意参数和适当简化假设的随机过程来表示它。输入过程又由如下一些元素构成:
(1)顾客总体
顾客总体可以是一个有限的集合,也可以是一个无限的集合;但只要顾客总体所包含的元素数量充分大,就可以把顾客总体有限的情况近似看成是顾客总体无限的情况来处理。上游河水流入水库可以认为顾客总体是无限的,而工厂里等待修理的机器设备显然是有限的顾客总体。
(2)顾客到达的时点
虽然顾客的到达可能是单个发生的,也可以是成批发生的,但在排队系统中总是假设在同一时点上只能有一个顾客到达,同时到达的一批顾客只能看成是一个顾客。
(3)顾客到达的相关性
顾客到达可以是相互独立的,也可以是相关联的。所谓独立即先前顾客的到达对后续顾客的到达没有影响,否则就是相关的。
(4)顾客到达的时间间隔
顾客到达的时间间隔可以是确定的,也可以是随机的。如在流水线上装配的各部件必须按确定的时间间隔到达装配点,定点运行的列车、班机的到达也都是确定的;但商场购物的顾客、医院诊病的病人、通过路口的车辆的到达都是随机的。对于随机的情形,我们必须了解单位时间的顾客到达数或相继到达的时间间隔的概率分布。
(5)顾客到达的平稳性
平稳性是指顾客到达的时间间隔分布及其特征参数(数学期望、方差等)不随时间的变化而变化。
最简单的到达过程是符合泊松(Poi