运筹学-第8章-排队论.docVIP

第八章排队论

排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。在排队论中把效劳系统中这些效劳的客体称为顾客。由于系统中顾客的到来以及顾客在系统中接受效劳的时间等均是随机的，因此排队现象是不可防止的。

对于随机效劳系统，假设扩大系统设备，会提高效劳质量，但会增加系统费用。假设减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了效劳质量，甚至会失去顾客而增加时机本钱。因此，对于管理人员来说，解决排队系统中的问题是：在效劳质量的提高和本钱的降低之间取得平衡，找到最适当的解。

排队论是优化理论的重要分支。排队论是1909年由丹麦工程师爱尔郎〔A.K.Erlang〕在研究系统时首先提出，之后被广泛应用于各种随机效劳系统。

第一节排队论的根本概念及所研究的问题

一、根本概念

〔一〕排队系统的组成

一般的排队系统有三个根本组成局部：顾客的到达〔输入过程〕、排队规那么和效劳机构，如图8—1所示。

顾客到达

顾客到达

排队

接受效劳

效劳后顾客离去

排队系统

图8—1

1．输入过程

输入过程指顾客按什么样的规律到达。包括如下三个方面的内容：

〔1〕顾客总体〔顾客源〕指可能到达效劳机构的顾客总数。顾客总体数可能是有限的，也可能是无限。如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。

〔2〕顾客到达的类型指顾客的到达是单个的还是成批的；

〔3〕顾客相继到达的时间间隔分布即该时间间隔分布是确定的〔定期运行的班车、航班等〕还是随机的，假设是随机的，顾客相继到达的时间间隔服从什么分布〔一般为负指数分布〕；

2．排队规那么

排队规那么指顾客接受效劳的规那么〔先后次序〕，有以下几种情况。

〔1〕即时制〔损失制〕当顾客来到时，效劳台全被占用，顾客随即离去，不排队等候。这种排队规那么会损失许多顾客，因此又称为损失制。

〔2〕等待制当顾客来到时，假设效劳台全被占用，那么顾客排队等候效劳。在等待制中，又可按顾客效劳的先后次序的规那么分为：先到先效劳〔FCFS，如自由卖票窗口等待卖票的顾客〕、先到后效劳〔FCLS，如仓库存放物品〕、随机效劳〔SIRO，交换台效劳对话务的接通处理〕和优先权效劳〔PR，如加急信件的处理〕。

3．效劳机构

效劳机构有以下几个特征参数，效劳台数量、效劳时间分布、多效劳台时效劳台是串联还是并联。效劳台数量一般分为单台还是多台，顾客在系统中接受效劳的时间是个随即变量，通常服从负指数分布或爱尔朗分布。

〔二〕排队系统的分类

早期，Kendall提出按排队系统的三个最为主要的特征分类，这三个特征是：

X——相继顾客到达的时间间隔分布；

Y——效劳时间分布；

Z——效劳台个数；

并用如下形式的符号描述排队系统，即：X∕Y∕Z

1971年，国际会议对排队系统的符号进行了标准化，即X∕Y∕Z∕A∕B∕C

其中：A——系统容量限制，即系统中允许的最大顾客数；

B——顾客源数目；

C——效劳规那么〔FCFS、FCLS、SIRO、PR〕。

例如M∕M∕1∕1∕∞∕FCFS表示相继顾客到达时间间隔和效劳时间服从负指数分布，单台，容量为1，顾客源无限，先到先效劳的排队系统；M∕D∕1∕4∕∞∕FCFS表示相继顾客到达时间间隔服从负指数分布，效劳时间为定长，单台，容量为4，顾客源无限，先到先效劳的排队系统；当省去后三项时表示X∕Y∕Z∕∞∕∞∕FCFS；

二、排队系统所研究的问题

排队问题的研究大体分为三类。

〔一〕系统性状的研究〔即参数指标的研究〕

指通过研究系统的数量指标了解系统的根本特征。这些指标如下。

〔1〕对长LS——系统中的平均顾客数，包括排队的顾客和正在接受效劳的顾客。

〔2〕排队长Lq——系统中排队等待效劳的平均顾客数；

〔3〕逗留时间WS——一位顾客在系统中的平均逗留时间，包括排队时间和接受效劳时间；

〔4〕等待时间Wq——一位顾客排队等待的平均时间；

〔5〕系统中没有顾客的概率P0——即所有效劳设施都空闲的概率；

〔6〕系统中有n个顾客的概率Pn；

〔7〕顾客到达系统时，必须排队等待的概率PW；

〔8〕忙期——从顾客到达空闲效劳机构起到效劳机构再次空闲止的时间长度；

〔9〕顾客损失率；

〔二〕统计问题的研究

所谓统计问题是指对效劳系统统计数据的处理，如顾客相继到达的间隔时间是否独立而且同分布，属于何种分布；效劳时间服从何种分布；效劳时间与相继到达时间是否独立等。

〔三〕最优化问题

1．系统的最优设计

在输入及效劳参数给定的条件下，确定系统的参数。如在M∕M∕C系统中，在的到达率及效劳率的情况下，如何设置效劳台数C，使得系统的某种指标到