串联排队系统平均等待时间的近似分析

侯佳辰，赵宁，刘文奇，侍颖

（1.昆明理工大学 理学院，云南 昆明 650500；2.昆明理工大学 数据科学研究中心，云南 昆明 650500；3.广东财经大学 国际商学院，广东 广州 510320）

0 引言

串联排队系统是生产服务系统中常见的一类排队网络，由两个或多个服务器串联而成，顾客到达系统后依次在各个服务器接受服务，所有服务完成后离开系统［1］。具有两个站的串联排队系统是排队网络的基本组成单元，任意复杂的排队网络可以分解成若干个具有两个服务器的串联排队系统，因此研究两个站的串联排队系统对分析复杂的排队网络具有重要的意义［2］。

20 世纪 50 年代 Jackson［3］提出如果串联排队系统的到达过程是泊松过程，服务时间服从指数分布，每个服务站可以看作是独立的M/M/1排队系统。Friedman［4］发现如果串联排队系统中每个服务器的服务时间是常数，则顾客在系统中的平均等待时间只与瓶颈站的服务时间有关，与其他服务时间无关。Wu和Zhao［5］通过模拟发现在串联排队系统中，上游服务站可能增大也可能减少下游服务站的等待时间，取决于到达过程的时间间隔和上游服务器的服务时间的平方变异系数。

由于串联排队系统各个站之间相互影响，如果系统不满足马尔可夫性，下游服务站的到达过程通常很难精确求解，因此通常采用近似方法分析平均等待时间［6-7］。Whitt［8］指出 Bell实验室提出的QNA方法（Queueing network analyzer）适用于到达过程间隔和服务时间不服从指数分布的串联排队系统，并通过计算机模拟对该方法的准确性进行评价。Harrison和Nguyen［9］利用排队系统到达时间间隔和服务时间的一阶矩和二阶矩，基于布朗运动提出了QNET方法（Queueing network）。Wu和Mcginnis［10］通过模拟发现串联排队系统固有比具有近似线性的特征，基于固有比提出了串联排队系统平均等待时间的近似方法，并验证了该方法优于QNA和QNET。Pinedo和Wolff［11］发现M/M/1→/M/1串联排队系统在两个站服务时间独立或不独立的情况下，系统的等待时间不相等。吴登磊等［12］提出采用指标比的方法近似分析M/G/1→/G/1系统的平均等待时间。Guo和Li［13］研究了 GI/G/1→/G/1 串联排队系统，该系统由两个单一服务器串联而成，系统的到达过程是更新过程，两个站的服务时间服从一般分布，文献［13］分析了系统的队长、忙期、离去过程等性能指标的随机波动程度。

以上关于串联排队系统平均等待时间的研究主要局限于系统的二阶近似，即仅考虑到达时间间隔和服务时间的一阶矩和二阶矩。通常随机变量的分布与一阶矩、二阶矩和三阶矩有关，即使两个随机变量的一阶矩和二阶矩相等，其三阶矩也可能不同，因此为了提高串联排队系统的等待时间近似的准确性，有必要考虑系统到达时间间隔和服务时间的三阶矩［14］。

本文将对GI/G/1→/G/1串联排队系统的平均等待时间采用三阶近似的方法进行分析。该系统不满足马尔可夫性，导致其一般服务时间和到达时间间隔很难用解析的方法进行分析［12］，而 MAP（Markovian arrival process）和 PH分布（Phase type distribution）具有马尔可夫性，便于理论分析［15］，本文将根据系统的到达时间间隔和服务时间的三阶矩将该系统近似为MAP/PH/1→/PH/1排队系统，构建相应的马尔可夫过程，通过矩阵几何解［16］的方法研究系统的平均等待时间等数量指标。

1 系统描述

本文研究两个站的串联排队系统，如图1所示，该系统由两个站组成，依次记为站1和站2，每个站仅有一个服务器，系统的到达过程是更新过程，两个站的服务时间均服从一般分布。系统缓冲区无限大，服从先到先服务的规则，被服务者依次经过两个站完成服务。

图1 两个站的串联排队系统Fig.1 A tandem queueing system of two stations

2 第一个站近似分析

由于GI/G/1→/G/1系统第二个站的缓冲区无限大，第一个站的输出过程不受第二个站的影响，因此第一个站的等待时间只与第一个站的到达过程和服务过程有关。第一个站可以看作是独立的GI/G/1排队系统，其中相邻顾客的到达时间间隔为随机变量X1，服务时间为S1。为了分析第一个站的GI/G/1排队系统，下面将其近似为MAP/PH/1的排队系统。

2.1 第一个站服务时间的近似

其中e为所有元素都为1的列向量。

其中（4）式中的参数 λY，λX1，λX2，pX可根据 Osoga⁃mi和 Harchol-Balter［17］提出的 PH 分布的近似方法，如果已知分布G的前三阶矩，通过PH分布的近似方法（见表1）中第二步的参数1-9，代入第三步中的参数10，即可将分布G转化为PH分布。

2.2 第一个站到达过程的近似

（5）式构造的MAP的到达时间间隔XMAP1的i阶矩为：

XMAP1的前三阶矩必然与X1的前三阶矩相等，即：

2.3 第一个站平均等待时间的近似

由2.1节和2.2节，站1的GI/G/1排队系统近似为MAP/PH/1排队系统，MAP/PH/1排队系统对应的马尔可夫过程为Z(t)={(L(t)，I(t)，J(t))，t≥0}，其中 L(t)表示 t时刻系统中的顾客数，I(t)表示t时刻到达过程MAP的状态，J(t)表示t时刻PH分布的状态，Z(t)的状态 空 间 为 Z={(0，i)：i=1，2，…，m} ∪ {(l，i，j)：l=1，2，…，i=1，2，…，m，j=1，2，…，n}。

马尔可夫过程Z(t)的Q矩阵为：

假设Z(t)的稳态概率分布为Π=(x0，x1，…)，其中x0为 1×m向量，xi为 1×mn 向量(i≥1)，表示系统里有i个顾客的概率向量。Π由ΠQ=0和Πe=1唯一确定。根据文献［15］，xi为下列矩阵几何结构：

其中R满足下式：

通过求解方程组（11），可以得到x0和x1：

GI/G/1排队系统的近似稳态概率分布为Π=(x0，x1，…)。由 GI/G/1 排队系统的近似稳态概率分布，可得如下性能指标：

第一个站的平均顾客数：E(L)=x1e+2x2e+3x3e+…=x1(I-R)-2e；

第一个站的平均逗留时间：E(T)=E(L)/λ=x1(I-R)-2e/λ；

第一个站的平均等待时间：QT1=E(L)/λ-E(SPH)=x1(I-R)-2e/λ-E(S1)。

3 第二个站近似分析

由于GI/G/1→/G/1系统第二个站的输入过程是第一个站的输出过程，如果第一个站的输出过程确定，则第二个站可以看作是单一服务站的GI/G/1排队系统，其中相邻顾客的到达时间间隔为随机变量X2，服务时间为S2。为了分析第二个站的GI/G/1排队系统，首先需要对第二个站的到达过程进行近似分析。

第二个站到达时间间隔为第一个站离去时间间隔。第一个站的状态分为两类：繁忙和空闲，其中繁忙的概率为ρ1，空闲的概率为1-ρ1。当第一个站繁忙时，相邻顾客的离去时间间隔为第一个站的服务时间间隔，即S1，其概率密度函数记为f(t)；当第一个站空闲时，相邻顾客的离去时间间隔为第一个站的服务时间间隔与第一个站的到达时间间隔之和，即X1+S1，其概率密度函数记为g(t)。因此，第二个站到达时间间隔X2的概率密度函数d(t)为：

X2的拉普拉斯变换为：

对 X͂2(s)求 i阶导（i=1，2，3）：

4 数值实验

下面通过数值实验介绍如何使用本文提出的近似方法，并将该近似方法求得的平均等待时间的近似值与计算机仿真得到的模拟值进行比较，验证该近似方法的有效性。

4.1 串联排队系统实例分析

假设GI/G/1→/G/1串联排队系统中第一个站到达时间间隔X1、第一个服务器的服务时间S1和第二个服务器的服务时间S2都服从Gamma分布：

（1） 第一个站到达过程的近似

（2） 第一个站服务时间的近似

（3） 第一个站平均等待时间的近似

由2.3节的矩阵几何解的方法可得第一个站的平均等待时间为：QT1=2.663。

对该串联排队系统进行计算机仿真可得平均等待时间的模拟值为：QT′1=2.599。

（4） 第二个站到达过程的近似

（5） 第二个站服务时间的近似

（6） 第二个站平均等待时间的近似

利用矩阵几何解方法计算得到第二个站的平均等待时间：QT2=37.632。

对该串联排队系统进行计算机仿真可得到平均等待时间的仿真数值为：QT′2=37.625。

4.2 不同串联排队系统平均等待时间的误差分析

本文提出的近似分析方法对各种具有两个站的串联排队系统都适用，下面分别对M/U/1→/G/1系 统 、M/G/1→/G/1系 统 和GI/G/1→/G/1系统的平均等待时间进行误差分析。

表2中两个站的平均等待时间的相对误差均小于5%；表3中相对误差均小于2%；表4中的相对误差比表2和表3的误差大，但在ρ≥0.5时，相对误差均小于5%。通常ρ较小时，平均等待时间较短，顾客对系统的等待时间不敏感，本文提出的方法在ρ较大的情况下能较准确地估计两个站的串联排队系统的平均等待时间。

表3 关于M/G/1→/G/1的平均等待时间相对误差Table 3 Relative error of mean waiting time for M/G/1→/G/1

表4 关于GI/G/1→/G/1的平均等待时间相对误差Table 4 Relative error of mean waiting time for GI/G/1→/G/1

4.3 近似分析方法的比较

为了验证本文提出方法的有效性，将本文提出的方法与文献［8］的QNA方法以及文献［9］的QNET方法进行比较。

考虑如下两个系统：

表5 不同方法处理系统1的平均等待时间相对百分比误差比较Table 5 Comparison of the relative percentage error of mean waiting time in different methods for handling system 1

表6 不同方法处理系统2的平均等待时间相对百分比误差比较Table 6 Comparison of the relative percentage error of mean waiting time in different methods for handling system 2

表5显示，当ρ=0.3，…，0.9，本文提出的方法误差最小。表5中QNA方法、QNET方法以及本文方法的平均相对误差分别为9.020%，4.467%和2.999%，本文提出的方法相比QNA方法和QNET方法有明显改善。表6中QNA方法、QNET方法以及本文方法的平均相对误差分别为0.349%，1.229%和0.409%，QNA方法和本文方法的误差比较接近，优于QNET方法．综合表5和表6可得本文提出的近似方法效果较好。

5 结论

本文采用三阶近似的方法将GI/G/1→/G/1串联排队系统近似为MAP/PH/1→/PH/1排队系统，得到一般串联排队系统的近似稳态概率分布，从而求解其相关数量指标。数据实验结果显示本文提出的近似方法近似效果较好。后续研究可以考虑采用四阶近似的方法，以提高近似的精确度；或者探究具有故障和阻塞的串联排队系统的近似分析方法［18］。