下载掌阅APP，畅读海量书库
立即打开
排队是我们在日常生活中经常遇到的现象，如顾客到商店买物品、病人到医院看病就常常要排队。一般说来，当某个时刻要求服务的数量超过服务机构的容量时，就会出现排队现象。这种现象远不只在个人日常生活中出现，要求服务的可以是人，也可以是物。例如在计算机网络系统中，要求传输数据的是各个网络结点，这里的服务机构是网络传输机构，而要求服务的就是等待传输一数据的网络结点。此外，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都属于排队现象。在各种排队系统中，顾客到达的时刻与接受服务的时间都是不确定的，随着不同时机与条件而变化，因此排队系统在某一时刻的状态也是随机的，排队现象几乎是不可避免的。
排队系统的关键元素是顾客和服务台。顾客可以指到达设施并请求服务的任何事物；服务台可以指能够提供服务的任何资源。排队系统是指物、人及信息等流量元素在流动过程中，由于服务台不足而不能及时为每个顾客服务，产生需要排队等待服务（加工）的一类系统。所以，排队是这些元素在流动、处理过程中常见的现象。这类系统的应用范围也可以扩大到一些大系统中物流问题的研究，如等待装运的物料与运输车辆之间、等待包装的商品与包装设备之间、等待入库的成品与堆垛机之间等，都是排队系统的实例。简单的排队系统可以用数学方法来求解，但复杂的排队系统用数学方法求解就显得困难，而仿真求解可用于各种结构、各种类型的排队系统。
排队系统虽然有各种形式，其复杂程度也有很大不同，但是，排队系统仿真建模却有其共同特点。首先，它们的建模步骤都是相同的。其次，排队系统仿真时钟是跳跃的。这是由于顾客的到来或离开系统的时间在排队系统中都是随机的。在有些时刻，系统中没有事件发生，系统状态没有任何变化，此时系统不必一秒一秒地变化，而是直接跳到下一个状态点；而在另外一个时刻，则有一个或多个事件发生，这些时刻称为特定时刻，系统状态也会随之变化。所以在排队系统的仿真时，仿真时钟只停留在事件发生的时刻上。此外，排队系统有共同及相似的事件类型与处理子程序，到来与离开事件及其处理子程序是所有排队系统共有的，其他事件及相应子程序则因不同类型的排队系统而有不同的内容。
排队系统的简单形式如图3-1所示，系统本身包括了顾客、排队列和服务台三部分。顾客源中的顾客不断到达该系统，并形成队列等待服务，直到服务结束离开，或重返顾客源，或永久离开该系统。排队系统是一个顾客不断的到来、排队及服务与离去的动态过程。
图3-1 排队系统的简单形式描述
这类系统中，最主要的实体就是顾客与服务台（或称服务员）。而在动态随机服务的过程中，还会发生许多客观的现象，为了对排队系统有一个清晰确切的描述，需要对其对应的有关概念分别作一介绍。
1.顾客与顾客源
“顾客”一词在这里是指任何一种需要系统对其服务的实体。顾客可以是人，也可以是零件、机器等物。
顾客源又称为顾客总体，是指潜在的顾客总数。它分为有限与无限两类。有限顾客源中的顾客个数是确切或有限的，如一个维修工人负责维修三台机器，则这三台机器就是一个有限的总体。
在具有较大潜在顾客的系统中，顾客源一般假定为无限的，既不能用确切的或有限的个数或没有办法来预知可能到来的顾客总体。如进入超市的顾客或要求电信局提供通话服务的顾客，即可假定为无限总体，而事实上这些顾客总体虽然很大但仍是有限的。定义其为无限主要是为了简化模型。
之所以区分有限顾客源与无限顾客源，主要是因为这两类系统中，顾客到达率（即每单位时间到达顾客的平均数）的计算是不同的。无限顾客源模型中，到达率不受已经进入系统等待或正接受服务的顾客数的影响。而对于有限顾客源模型，到达率往往取决于正在服务或正在等待服务的顾客数。
2.到达模式
到达模式是指顾客按照怎样的规律到达系统，它一般用顾客相继到达的时间间隔来描述。根据时间间隔的确定与否，到达模式可分为确定性到达与随机性到达。
确定性到达模式指顾客有规则地按照一定的间隔时间到达。这些间隔时间是预先确定的或者是固定的。等距到达模式就是一个常见的确定性到达模式，它表示每隔一个固定的时间段就有一个顾客到达的模式。
随机性到达模式指顾客相继到达的时间间隔是随机的、不确定的。它一般用概率分布来描述，常见的随机性到达模式有以下几种：
（1）泊松到达模式
泊松分布是一种很重要的概率分布，出现在许多典型的系统中，如商店顾客的到来、机器到达维修点等均近似于泊松到达模式。
（2）爱尔朗到达模式
这种到达模式常用于典型的电话系统。
1）一般独立到达模式。也称任意分布的到达模式，指到达间隔时间相互独立，分布函数是任意分布的到达模式。这种分布往往可以用一个离散的概率分布加以描述。
2）超指数到达模式。主要用于概率分布的标准差大于平均值的情况下。
3）成批到达模式。与到达时间间隔的分布无关，只是在每一到达时刻到达的顾客个数不是一个，而是一批。
3.服务机构
服务机构是指同一时刻有多少服务台可以提供服务，服务台之间的布置关系是什么样的。服务机构不同，则排队系统的结构也不相同。根据服务机构与队列的形成形式不同，常见且比较基本的排队系统的结构一般有以下几种：单队列单服务台结构、多队列单服务台结构、多个服务台串联且每个服务台前有一个队列的结构、多个服务台并联且共同拥有一个队列的机构、多个服务台并联且每个服务台前有一个队列的结构。一个较为复杂的排队系统其结构往往是由以上几种基本结构组合而成的。
服务机构有两个重要的属性，分别为服务时间和排队规则。
（1）服务时间
服务台为顾客服务的时间可以是确定的，也可以是随机的。后者更为常见，即服务时间往往不是一个常量，而是受许多因素影响不断变化的，这样对这些服务过程的描述就要借助于概率函数。总的来说，服务时间的分布有以下几种。
1）定长分布。这是最简单的情形，所有顾客被服务的时间均为某一常数。
2）指数分布。当服务时间完全随机的时候，可以用指数分布来表示它。
3）爱尔朗分布。它用来描述服务时间的标准差小于平均值的情况。
4）超指数分布。与爱尔朗分布相对应，用来描述服务时间的标准差大于平均值的情况。
5）一般服务分布。用于服务时间是相互独立但具有相同分布的随机情况，上述分布均是一般分布的特例。
6）正态分布。在服务时间近似于常数的情况下，多种随机因素的影响使得服务时间围绕此常数值上下波动，一般用正态分布来描述服务时间。
7）服务时间依赖于队长的情况。即排队顾客越多，服务速度越快，服务时间越短。
（2）排队规则
排队规则是指顾客在队列中的逻辑次序，以及确定服务员有空时哪一个顾客被选择去服务的规则，即顾客按什么样的次序与规则接受服务。
常见的排队规则有以下几类。
1）损失制。若顾客来到时，系统的所有服务机构均非空，则顾客自动离去，不再回来。
2）等待制。顾客来多时，系统所有的服务台均非空，则顾客就形成队列等待服务，常用的规则如下。
①先进先出（FIFO）：即按到达次序接受服务，先到先服务。
②后进先出（LIFO）：与先进先出服务相反，后到先服务。
③随机服务（SIRO）：服务台空闲时，从等待队列中任选一个顾客进行服务，队列中每一个顾客被选中的概率相等。
④按优先级服务（PR）：当顾客有着不同的接受服务优先级时，有两种情况：一是服务台空闲时，队列中优先级最高的顾客先接受服务；二是当有一个优先级高于当前顾客的顾客到来时，按这样的原则处理。
⑤最短处理时间先服务（SPT）：服务台空闲时，首先选择需要最短服务时间的顾客来进行服务。
3）混合制。它是损失制和等待制的综合类型，具体包括以下几种规则。
①限制队长的排队规则：设系统存在最大允许队长 N ，顾客到达时，若队长小于 N ，则加入排队，否则自动离去。
②限制等待时间的排队规则：设顾客排队等待的最长时间为 T ，则当顾客排队等待时间大于 T 时，顾客自动离去。
③限制逗留时间的排队规则：逗留时间包括等待时间与服务时间。若逗留时间大于最长允许逗留时间，则顾客自动离去。
1.单服务台排队系统
单服务台结构是排队系统中的最简单的结构形式，在该类系统中有一级服务台，这一级中也只有一个服务台。它的结构如图3-2所示。
图3-2 单服务台排队系统结构
2.单级多服务台排队系统
单级多服务台结构也是经常遇到的一类排队系统形式，它又可分为所有服务台只排一个队以及每个服务台都有排队的两种不同情况，分别如图3-3所示。这里每个服务台的服务时间可以有相同分布或参数，也可以有不同参数甚至不同的分布。在第一种排队形式中，无论哪个服务台空闲则有顾客进入服务台，当两个或两个以上服务台空闲时，则可按规则选择进入其中的一个服务台。在第二种排队形式中，首先确定该顾客选择哪个服务台，然后根据选择的服务台是“忙”或“闲”决定是接受并开始服务，还是在该服务台前的队列中等待服务。
a)所有服务台只排一个队 b)每个服务台都有排队
图3-3 单级多服务台排队系统结构
3.多级多服务台排队系统
多级多服务台排队系统是排队系统的一类常见形式。图3-4表示了一个典型的多级多服务台排队系统，服务台共有3级，每级分别由2台、3台和1台组成，每级服务台前有一排队，顾客进入系统后逐级进入服务台，逐级服务。如没有空闲的服务台则逐级排队等待，当最后一级服务结束后顾客离开系统。
图3-4 多级多服务台排队系统结构
排队系统中，除了损失制，排队现象是不可避免的。这是由顾客到达的速率大于服务台进行服务的速率造成的。但是，排队越长则意味着系统服务质量越差，或者说系统效率越低。而盲目增加服务台，虽然队长可以减少，但却有可能造成服务台太多的空闲时间，设备利用率太低。排队系统研究的实质就是要解决上述问题，即合理地解决顾客等待时间与服务台空闲时间的矛盾，使得系统服务质量与设备利用率都达到较高的标准。
排队系统常用的性能指标有如下几个。
1.服务台的利用率 ρ
ρ= 平均服务时间/平均到达时间间隔= λ / μ
其中， λ 为平均到达速率， μ 为平均服务速率（即单位时间内被服务的顾客数）。
通常情况下， ρ< 1。这是其他性能指标存在的前提条件。
2.平均等待时间 W q
其中， D i 为第 i 个顾客的等待时间； n 为已接受服务的顾客数。
3.平均逗留时间 W
其中， W i 为第 i 个顾客在系统中的逗留时间，它等于该顾客排队等待时间 D i 和接受服务时间 S i 之和。
4.平均队长 L q
其中， L q ( t )为 t 时刻的队列长度； T 为系统运行时间。
5.系统中平均顾客数 L
其中， L ( t )为 t 时刻系统中的顾客数； S ( t )为 t 时刻系统中正在接受服务的顾客数。
6.忙期（闲期）
忙期是指服务台全部处于非空闲状态的时间段，否则成为非忙期。而闲期指服务台全部处于空闲状态的时间段。对于单服务台来说，忙期与闲期交替出现。
除以上常见的性能指标外，具体的排队系统还可以根据系统本身的要求，采用其他体现系统性能的指标，如最长队列，顾客在系统中最大的逗留时间等。
一个拥有一个出纳台的小杂货铺，顾客相隔1～8min随机到达出纳台，每个到达时间间隔的可能取值具有相同的发生概率，如表3-1所示。服务时间在1～6min间变化见表3-2。我们是通过仿真100个顾客的到达和接受服务来分析该系统。
表3-1 到达时间间隔分布
表3-2 服务时间分布
为了产生到达出纳台的时间，需要一组均匀分布的随机数，这些随机数满足下列条件：
1）这些随机数在0～1之间均匀分布。
2）相邻的随机数是相互独立的。
由于表3-1中的概率值精度为三位，那么三位的随机数就可以满足要求。必须列出99个随机数以便产生到达间隔时间。为什么仅需要99个数呢？因为第一个顾客是假定在0时到达的，所以只需要为100个顾客产生99个到达时间间隔。同样，对于表3-2，两位的随机数足够了。
表3-1和表3-2的最右边两栏是用来生成随机到达和随机服务时间的，每个表的第三栏包含了该分布的累计概率。最右边一栏包含了随机数字的分配。在表3-1中，首先分配的随机数字是001～125，这里三位数有1000个（001～000）。到达间隔的时间为1min的概率是0.125，所以在1000个随机数字中有125个被分配到这种情况。99名顾客的到达间隔时间的产生是由表3-3列出99个三位数字值并将其与表3-1的随机数字分配比较得到的。
到达间隔时间的确定如表3-3所示。注意，第一个随机数字是064。为了得到相应的到达间隔时间，进入表的第四栏并从该表的第一栏读取1min。另一方面，我们看到0.064在累积概率0.001～0.125之间，作为产生的时间也得到1min。
表3-3 到达时间间隔的确定
前18名和第100名顾客的服务时间见表3-4。这些服务时间是根据上述的方法同时借助于表3-2产生的。
表3-4 服务时间的生成
（续）
第一个顾客的服务时间是4min，因为随机数字84处于61～85之间；或者，换句话说，因为导出的概率0.84落在累计概率0.61～0.85之间。
手工仿真的本质是仿真表格。这些仿真表格是为了解决遇到的问题而专门设计的，采用的方法是：增加栏目以回答所提出的问题。第一步是填写第一个顾客所在的单元以初始化表格：第一个顾客假定在时刻0到达，服务马上开始并在时刻4结束，第一个顾客在系统中逗留4min。在第一个顾客以后，表中后续的各行都基于前一顾客的到达间隔时间、服务时间以及服务结束时间的随机数。例如，第二个顾客在时刻1到这，但服务不是马上而是直到时刻4才开始，因为服务台（出纳员）在该时刻之前一直繁忙。第二个顾客在队列中要等待3min，服务时间为2min。这样，第二个顾客在系统中停留5min。跳到第五个顾客，服务结束于时刻16，但是第六个顾客要在时刻18才到达，那时服务才开始。这样，服务台（出纳员）就要空2min。这一过程继续到100个顾客。最右边增加的两栏用来收集性能统计量度，比如每个顾客在系统中的时间以及服务台从前一顾客离去后的空闲时间（如果有的话）等。为了计算总统计量，表中列出了服务时间、顾客在系统中花费的时间、服务台空闲的时间以及顾客在队列中等待的时间的总数。
从表3-5中的仿真得到如下一些结果：
1）顾客的平均等待时间是1.74min，依据以下方法计算：
2）顾客必须在队列中等待的概率是0.46，依据以下方法计算：
3）服务台空闲的概率是0.24，依据以下方法计算：
服务台繁忙的概率就是0.24的补，即0.76。
表3-5 单通道排队系统的仿真表格
（续）
4）平均服务时间是3.17min，依据以下方法计算：
这个结果可以和服务时间的期望值相比较，服务时间分布的均值用以下公式计算
对表3-2的分布应用期望值公式，得到
期望服务时间=1min×0.10+2min×0.20+3min×0.30+4min×0.25+5min×0.10+6min×0.05=3.2min
期望服务时间要略高于仿真中的平均服务时间。仿真时间越长，平均值将会越接近E(S)。
5）平均到达时间间隔是4.19min，依据以下方法计算：
因为第一个顾客是在0时刻到达的，所以分母减去了1。可以通过求离散均匀分布的均值将这个结果和期望到达时间间隔做比较。离散均匀分布的端点是a=1min、b=8min，其均值为
到达时间间隔的期望值要略高于平均值。仿真时间越长，所得出的期望值就会越接近理论的平均值E(A)。
6）有等待的顾客的平均等待时间是3.22min，依据以下方法计算：
7）顾客在系统中花费的平均时间是4.91min。这个值可以由两种方法获得，第一种方法通过下列关系进行计算：
第二种方法也会得到同样的结果，基于以下关系的成立：
顾客在系统中花费的平均时间=顾客在队列中等待的平均时间+顾客接受服务的平均时间，根据结果1和结果4可以得到：
顾客在系统中花费的平均时间=1.74min+3.17min=4.91min
决策者会对这一类结果满意。但如果增加仿真时间，会使结果更加准确。这样的结果已经能给许多实验性的推断提供依据。大约半数的顾客必须等待，但是平均等待时间并不太长。服务台没有不适当的空闲时间。关于本结果更可信的说法可能取决于在等待的成本和增加服务台的成本之间取得平衡。