[科普中国]-排队网络

概述

排队网络是指多个排队系统互相联接所组成的网络，其中任何一个排队系统所服务完的顾客可加入其他的排队系统继续接受服务，或者离开整个排队网络。排队网络与排队系统的本质区别在于：在排队网络中，一个顾客一般要在多个服务台处接受服务；而在排队系统中，一个顾客只在一个服务台处接受服务。在一些严格的条件下，排队网络与排队系统在理论上没有太大的区别；但在计算方面，排队网络中求解一些问题的计算量非常大。2

一个排队网络是由多个服务机构组成的系统.排队网络中的顾客根据一定的路由机制在服务台之间转移或离开网络.顾客可能属于不同的类型，这意味着他们可能有不同的路由机制，不同的服务时间分布，或不同的服务优先级.排队网络可以分为以下三种类型：开放网络，闭网络或混合网络.在一个开放网络中，顾客从网络外部到达该网络并最终离开该网络；在一个闭网络中，顾客在不同服务机构之间转移而没有顾客的到达或离开；一个混合网络对某些类型的顾客是开放的，而对其他类型的顾客是封闭的.3

排队网络是一个比较复杂的服务系统，在此系统中经常需要讨论多个 队列的互联问题，如顾客流的分开与合并，队列的串、并联组合等.4

图8. 1 就描绘了这样一个简单的排队网络，在此排队网络中包含了四个节点，每个节点代表一个服务站（Service center)(例如计算机系统中的处理单元 (CPU或I/O设备）或者是通信系统中的某些网络节点（交换机或路由器））， 每个服务站中包括一个队列（该队列中可以有一个或多个服务员）。其中互联的线条表示顾客流。4

基本原理Q-GERT网络通过采用丰富的节点形式，描述网络中的排队问题，能表示各种定量和定性信息。具体做法：在GERT网络的基础上，将节点划分为若干部分，在各部标注一定的内容，如节点的存储和排队特征、容量及实现节点所需的流等。节点类型和工序表示法如图1所示。1

图1中，Q节点为排队节点，当容量e为有限时，可能出现：（1）被斥现象，即排队流量超过了允许容量，新参加排队的流受到排斥。被系统永久拒绝再进入排队称永久排斥；被暂时转移到其他缓冲节点等待机会再进入排队称为暂时排斥；（2）受阻现象，当排队节点发生被现象且不允许转移到其他节点时，排队节点前的工序被迫暂停工作。实际系统中，受阻原因可能是节点容量偏小或后面工序进度偏慢，Q-GERT网络的输入类型（排队流的到达规律）一般有确定型、随机型和介于二者之间的中间型等。1

基本类型通常排队网络可分为如下三种基本类型：

开环网络(Open networks):至少有一个来自外部的输入顾客流和至少一个输出到外部的输出顾客流，如图8.1所示。开环网络可用于表示一个具有来自外部的到达和从内部离开的事务处理系统。4

闭环网络(Closed networks):所有顾客永远在网络内循环流动，此时网络中顾客数目为常数。例如，将图8.1中节点1和节点2的外部线条去 掉，它就变成一个闭环网络。闭环网络可用于模拟多程序级别维持恒定情 况下的批量类型的工作负荷。4

混合网络(Mixed networks):如果所研究的排队网络对某类顾客是开放的，而对其他类顾客是关闭的。混合网络可用于同时表示计算机系统中的事务处理性和批量类型的工作负荷。4

计算分析用Q-GERT网络模型分析问题的步骤为：将实际问题用网络模型描述，明确节点特性，找出突出反映排队问题的节点；计算网络；分析评价，做出决策。求解的目的是为掌握整个网络系统排队现象的统计规律，研究系统的运行效率，估计服务质量，决定改进措施，寻找系统处于稳定的高效的工作状态。1

Q-GERT网络模型的结构多种多样，对一个系统来说，解决的问题不同时，其网络模型也不同，所求解的内容亦各有差异。一般难以用分析法求解，最有效的求解办法为计算机模拟，计算机网络流在不同时刻状态的变化情况，以及系统在每个时刻所处的状态，然后再汇总统计，分析全周期内的工作状态，求解的结果有：（1）输入节点的平均到达率。（2）Q节点，包括平均排队个数，等待的平均时间和标准差，被斥的个数，排队中最大数量和最小数量。（3）统计节点（汇节点），包括通过该节点的个数，到达节点时间，从输入到该节点消耗时间的均值和标准差，输出个数与输入个数的比率。（4）工序，包括工作效率，受阻时间，工作人员忙、闲最长时间，工作人员平均工作时间和标准差。在应用时可根据解决实际问题的要求，有选择性的计算结果。1

符号体系对排队网络的描述有一套符号体系.例如，M/ CT/1表示顾客来到的间隔时间为负指数分布(M)、服务时间为一般分布(G)、单个服务台(1)等.排队网络问题早已由电话服务系统等问题提出和发展，但难度甚大，连看来简单的G/G/1问题至今未有通用的解法.排队网络的状态一般用各服务台前各类顾客排队长度的联合分布来描述.只有当该联合分布可以分解为各个队列长度分布的乘积形式，即各队长分布相互独立时，问题才较容易解决.因此，研究具乘积形式解的排队网络类型是一个重要的理论和实践的问题.例如，杰克森网络和BCMP网络(参见“BCMP网络”)都是著名的具有乘积形式解的例子。5

排队系统构成模式排队论(Queuing Theory)，或者称为随机服务系统理论，在计算机网络和计算机系统 的性能评价中占有相当重要的地位，任何一个排队模型都由3个环节组成：顾客的到达过程、服务机构和排队规则.

到达过程通常用两个相邻顾客的到达时间间隔来描述。平均到达时间间隔的倒数表示单位时间内平均到达的个数，称为到达率。常见的到达过程形式有规则到达、泊松到达、一般相同而独立的到达、成批到达、非平稳到达和连续到达。在经典的排队论中多假设到达过程是泊松过程。6

服务机构需要明确的是服务站的个数、服务站之间的串并联结构和服务台的服务时间分布规律。服务时间的类别也有多种，平均服务时间的倒数表示单位时间内可以完成服务的平均次数，称为服务率.常见的服务时间分布有常数分布、指数分布、爱尔朗分布和一般分布，6

排队规则是指在每一个服务站等待服务的顾客按照什么样的顺序接受服务。一个服务站的每类顾客在一个时刻最多只能有一个顾客接受服务，满足这一条件的常见服务原则有：先到先服务原则（FIFO)、后到先服务原则（LIFO）、优先级原则和服务器共亨服务原则， 在排队系统研究中，队长、顾客在系统中的等待时间以及逗留时间的长短都与服务原则有关，不同服务原则直接影响系统的稳定性和顾客在系统中耗费时间的长短，所以对于排队系统而言,排队规则尤其重要。6

在排队系统中，能够反映系统结构及性能的可用于定最量分析的主要指标如表7-1所示。

特征其形式化描述需阐明以下几方面特征：

1.顾客(亦泛指待加工零件等)的种类、到来数量的特征、优先等级和规则等.。

2.服务台(亦指加工机器等)的数量和服务时间的统计分布。

3.排队规则，如是否先到先服务、顾客是否因等待和服务时间过长而中途离去等。

4.排队空间及系统中总顾客数的限制.。

5.在多服务台形成服务网络情形还有关于顾客接受多种服务的路径和规则等，研究的课题包括系统性能指标，如平均排队长度和顾客保留时间的统计分析、系统参数和结构设计以及调度优化的规则等。5

优缺点排队网络将行人所处的环境用“节点”和“边”抽象表示，将复杂情况精简，更加有利于模型的实际应用。

其缺点是：行人的移动过程很模糊，对于其中发生的碰撞，以及行人之间的相互协作问题无法体现；对于复杂的建筑和设施布局的不同带来的行人移动变化未作考虑，且“先进先出”的排队策略未必适合于行人系统。7

应用排队网络模型在生产调度、计算和通信系统优化等方面有重要应用.随机仿真试验仍是一种主要研究途径，最近发展了一些基于仿真的统计优化技术，可望达到实用的目的.5