第七章排队论
排队是在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车，顾客到商店购买物品，病员到医院看病等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如水库的存储调节，车站、码头等交通枢纽的车船堵塞和疏导等。排队的不一定是人，也可以是物，例如，通信卫星与地面若干待传递的信息，生产线上的原料、半成品等待加工，要降落的飞机因跑道被占用而在空中盘旋等。上述各种问题虽互不相同，却都有要求得到某种服务的人或物和提供服务的人或机构。这样就构成了各种各样的服务系统，把要求服务的对象统称为“顾客”，而把提供服务的人或机构成为“服务台”或“服务员”。由于顾客到达和服务的随机性，可以说排队是不可避免的。
如果增添服务设备、就要增加投资或发生空闲浪费；如果服务设备太少，排队现象就会严重，对顾客个人与社会都带来不利影响。因此，管理人员必须考虑如何在两者之间取得平衡，这就是排队论所要研究的问题。
排队论(Queuing Theory)又称随即服务系统理论(Random Service System Theory)，是研究排队系统的数学理论和方法，是运筹学的一个重要分支。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。
第一节排队论的基本概念
任何一个排队问题的基本排队过程都可以用图7-1表示。每个顾客由顾客源按一定的方式到达服务系统，首先加入排队队列等待接受服务，服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。
图7-1 排队系统
任意排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达，“散”表示顾客的离去，所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，到达时间间隔和服务时间两个量中至少有一个是随机的，因此，排队论又称为随机服务系统理论。
7.1.1排队系统的基本组成
通常，排队系统由输入过程、排队规则和服务机构三个部分组成。
(1)输入过程
输入过程是指要求服务的顾客按怎样的规律到达排队系统的过程，有时也称之为顾客流。一般可以从三个方面来描述一个输入过程：
①顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。如到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。
②顾客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。大学生到图书馆借书是单个到达的例子，而购买的材料入库则可以看成是成批到达。
③顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流和负指数分布等。
(2)排队规则
排队分为有限排队和无限排队两类。前者是指系统的空间是有限的，当系统被沾满时，后面再来的顾客将不能进入系统；后者是指系统中的顾客数可以是无限的，队列可以排到无限长，顾客到达后均可进入系统排队或接受服务。具体又分为以下三种。
①等待制。指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离去。如排队等待售票，故障设备等待维修等。等待制中，服务台选择顾客进行服务时通常有如下四种规则：
A.先到先服务(First Come First Serve，FCFS)。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。
B.后到先服务(Last Come First Serve，LCFS)。仓库中存放的钢材，后放上去的先被领走，重大消息优先刊登，都属于这种情形。
C.随机服务(Service in Random Order，SIRO)。当服务台空闲时，不按排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫就是一例。
D.有优先权的服务(Priority，PR)。如老人、小孩先进车站，重病号先就诊，遇到重要数据需要立即中断其他数据的处理等，均属于这种规则。
②损失制。指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。如电话拨号后出现忙音，顾客不愿等待而挂断电话，如要再打则需重新拨号。
③混合制。这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。大体有以下三种：
A.队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。
B.等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度，当等待时间超过时间时，顾客将自动离去，并且不再回来。
C.逗留时间(等待时间与服务时间之和)有限。
(3)服务台
服务台可以从以下三个方面来描述：
①服务机构数量及构成形式。从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等，如图7-2到图7-5所示。
②服务方式。指在某一时刻接受服务的顾客数，有单个服务和成批服务两种。
③服务时间的分布。在多数情况下，对某一个顾客的服务时间是一种随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等。
7.1.2排队系统的主要数量指标、记号和符号
(1)排队系统的主要数量指标
研究排队系统的主要目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状态。描述一个排队系统运行状况的主要数量指标有：
①队长和队列长(排队长)。队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)；队列长是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量。队长的分布是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而确定合理的等待空间。
②等待时间和逗留时间。从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。等待时间是个随机变量，也是顾客最关心的指标，因为顾客通常是希望等待时间越短越好。从顾客到达时刻起到他接受完服务止这段时间称为逗留时间，也是随机变量，顾客同样非常关心。
③忙期和闲期。忙期是指从顾客到达空闲着的服务机构起，到服务再次称为空闲止的这段时间，服务机构连续忙的时间。这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度。与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。
除了上述几个基本数量指标外，还会用到其他一些重要指标。如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的指标。
(2)排队系统中的常用记号
：时刻系统中的顾客数(又称为系统的状态)，即队长
：时刻系统中排队的顾客数，即队列长
：时刻到达系统的顾客在系统中的逗留时间
：时刻到达系统的顾客在系统中的等待时间
上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量，直接求出它们的瞬时分布一般是很困难的。一般地，排队系统在运行了一段时间后，都会趋于一个平稳状态，在平稳状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。所谓的系统状态是指系统中顾客数，如果系统中有个顾客就说系统的状态是。因此，我们在本章中将主要讨论统计平衡性质。
：平均队长，即稳态系统任一时刻顾客数的期望值
：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值
：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值
：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值
这四项主要性能指标的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。他们是顾客与服务系统的管理者都非常关注的。
：顾客到达的平均速率，即单位时间内平均到达的顾客数
1/：平均到达时间间隔
：平均服务速率，即单位时间内服务完毕离去的顾客数
1/：平均服务时间
：系统中服务台的个数
：服务强度，即每个服务台单位时间内的平均服务时间，一般有=/(/)
：稳态系统任一时刻的状态(即系统中所有顾客数)
：任一顾客在稳态系统中的逗留时间
：任一顾客在稳态系统中的等待时间
：稳态系统任一时刻状态为的概率；特别当=0时，，即稳态系统所有服务台全部空闲的概率；
：有效平均到达率，即期望每单位时间内来到系统(包括未进入系统)的概率。
(3)排队系统的符号表示
为了区别各种排队系统，根据输入过程、排队规则和服务机构的变化对排队模型进行描述或分类，可给出很多模型。1953年肯道尔(Kendall)提出一个分类方法，称为Kendall符号，其形式是：。在1971年一次关于排队论符号标准化国际会议上，将Kendall符号扩充为以下标准形式：或[]：[]。
各符号的意义为：
X：表示顾客相继到达时间间隔的概率分布，可取M、D、Ek、G等，其中：
M——表示到达过程为泊松过程或负指数分布；
D——表示定长输入；
E——表示K阶爱尔朗(Erlang)分布；
G——表示一般相互独立的随机分布。
Y：表示服务时间分布，所用符号与X相同。
Z：表示服务台个数，取正整数。1表示单个服务台，(x＞1)表示有多个服务台。
A：表示系统中顾客容量限额，或称等待空间容量。若系统中有K个等待位子(0＜K＜∞)
B：表示顾客源限额，可取正整数或∞，即有限与无线两种。
C：表示服务规则，如FCFS、LCFS等。
例如：。表示顾客到达的时间间隔是负指数分布，服务时间时负指数分布，一个服务台，排队系统和顾客源的容量都是无限，实行先到先服务的一个服务系统。
