闭环Jackson网络的资源利用率分析方法及应用

杨镇铭, 赵千川

(清华大学自动化系北京国家信息科学与技术研究中心,北京 100084)

1 引言

排队论是对服务系统中排队现象进行研究的理论.排队论被广泛地应用于供应链、交通运输、生产线以及网络通信等系统的性能研究之中,在分析拥塞、瓶颈、负载等问题起到了很大的作用,对于这些系统的结构设计和参数设定上具有指导意义.

排队网络是由若干个单节点排队系统相互连接所组成的网络.在排队网络中,一个顾客在被一个节点服务完之后,可以进入其他节点的排队系统继续接受服务,也可以离开排队网络.排队网络由于包含多个节点,其计算复杂性相比单节点的排队系统更加复杂,一些相关的指标也需要用新的方法来进行计算.一个排队网络中,可能包含节点的串、并联的组合.由于在现实中的场景中,系统往往不会只包括单个的服务台节点,而是由多个服务台以某种方式连接而组成整个系统.因此,排队网络在具体的应用场景中,有着更大的实际意义.

排队网络通常可以分为开环排队网络和闭环排队网络两种.如果排队网络中存在外部的源节点和目标节点,则称为开环排队网络,否则称为闭环排队网络.即在开环排队网络中,顾客从网络的外部到达网络,经过一系列节点后离开排队网络.而对于闭环排队网络,全部顾客始终在网络内部的不同节点之间转移,网络的顾客总数不发生增减.对于类似仓库、集装箱码头这一类封闭的场景,其顾客也即车辆数通常是保持不变的,所以更适合使用闭环排队网络来进行分析.

关于排队网络,目前已经做出了很多研究.Jackson首先对满足一组特定性质的排队网络进行研究,这类排队网络后来被称为Jackson排队网络,这篇论文证明了Jackson网络中各节点会收敛到稳态分布,并且各节点的稳态分布时相互独立[1].Gordon和Newell证明了Jackson网络中各节点稳态的联合分布可以写成乘积解的形式[2].Denning使用排队网络的工具来对一具体的排队系统的运营性能进行分析[3].Buzen对于闭环Jackson网络的求解给出了一种递推计算的方法[4].曹希仁和何毓琦用摄动分析的方法对排队网络顾客的逗留时间进行分析[5].夏俐用马尔科夫决策过程对带有功率约束的串联排队系统进行建模,并对各节点的服务率进行控制和优化[6].周亚平引入了性能势的概念,并利用性能势对受控的闭环排队网络进行优化[7].

除了对排队网络的理论进行研究之外,还有很多将排队网络应用到具体的场景之中,对具体问题进行建模与分析的研究.Seidmann利用闭环排队网络对柔性制造系统进行建模与分析[8].夏俐对开环排队网络中的动态定价和服务率控制问题进行研究,并将其分解成服务率设定问题加上价格设定问题以求解[9].Agboola用排队网络对计算机集群系统的各项指标包括队长、逗留时间等进行分析[10].Hum利用马尔可夫排队网络对供应链系统进行建模和优化[11].Romero-Silva利用排队网络分析了流水线中缓冲位置对作业时间的影响[12].Zhang提出了一种基于排队网络的算法来对网约车进行建模,有效地将乘客分配给相应车辆[13].Yan利用排队论分析了制造系统中流水统的效

率[14].

对系统进行建模分析时,通常会关心系统中资源的配置情况,一般用各个设备的利用率来表示.使用模拟仿真的方法对系统进行建模,也是一种性能分析的常见方法.但仿真实验往往比较慢,而且需要多次的仿真结果才能收敛.当网络结构调整时,需要重新进行多次的仿真实验.如果使用排队网络进行建模,当满足一些条件时,可以得到资源利用率的解析解,大大减少所需时间.更关键的是,有了解析公式,可以得到资源利用率和相关参数(如顾客总数、服务时间)的关系,分析其变化趋势.而通过仿真方法,很难直接得到调整参数后的结果,还需要重新进行仿真实验.在排队网络中,各节点利用率是分析系统性能的一个重要的指标,可以用于分析各个服务台是否处于饱和工作状态,以及找出哪个节点是整个排队网络的瓶颈所在.例如在生产制造系统中,如果部分节点的利用率很高,而另一些节点的利用率很低,则意味着有部分机器处于高负荷工作状态,而另一些机器则几乎闲置,这样的系统负载不均衡,没有发挥出所有机器的效能.

本文通过对闭环Jackson网络中各节点的利用率的解析表达式进行分析,得到各节点的利用率和资源总数以及各节点的服务时间之间的关系,并计算使利用率达到饱和状态所需要投入的资源总数.并将该方法应用在一个具体的自动化码头案例上,分析其运输区域路网设计中的瓶颈以及利用率与车辆数的关系.

2 问题描述

2.1 术语符号表

对于一个包含M个节点,共有N个顾客的排队网络,相关的变量和参数定义如下:

M: 节点总数,

N: 顾客总数,

ni: 第i个节点的顾客数,i ∈{1,2,··· ,M},

λi: 第i个节点的到达率,i ∈{1,2,··· ,M},

µi: 第i个节点的服务率,i ∈{1,2,··· ,M},

ρi: 第i个节点的服务强度,ρi=λi/µi,

rij: 从第i个节点到第j个节点的路由转移概率,

Ui: 第i个节点的利用率,i ∈{1,2,··· ,M}.

2.2 闭环Jackson排队网络服务台利用率的计算

对于通常的排队网络,其分布的计算过程十分复杂,往往没有办法找到解析解,从而只能通过数值计算甚至仿真的方法来得到排队网络的分布.

而当排队网络满足某些条件时,称这类排队网络为Jackson排队网络.这类排队网络各节点的稳态分布计算形式简单,并且排队网络具有乘积形式的解.Jackson网络根据其是否具有外部源节点和目标节点而分为开环Jackson网络和闭环Jackson网络.

本文重点研究闭环Jackson网络中各节点的利用率的计算,并尝试将计算方法应用在自动化集装箱码头车辆运输效率的性能分析之中.

考虑一个包括M个节点的排队网络,如果满足:

1)网络没有外部顾客源节点和外部目标节点;

2)网络中的顾客总数为N,且N保持恒定;

3)每个节点中的服务时间服从参数为µi的指数分布,且不同节点间的服务时间是相互独立的;

则称这个满足条件的排队网络为闭环Jackson网络.在闭环Jackson排队网络中,排队网络的状态可以表示为顾客在每个节点的数量

其中ni是第i个节点的顾客数量,满足条件

本文的目标是计算出在排队网络中顾客数量的分布,表示为

当得到排队网络整体的分布之后,可以通过计算边缘分布得到每个节点的顾客数量分布p(ni=k).

各节点利用率,是结点中服务台处于服务状态的时间占总时间的比例.

为了解决这一问题,Buzen曾经给出了一种G(N)的递推计算方法[4].将N个顾客、M个节点的归一化参数G(N)用N −1个顾客以及M −1个节点的情况来递推.该方法可以比较快速地计算出G(N)的数值,将计算复杂度降低到O(MN).

此外,Gordon曾经给出了G(N)母函数的形式[15].通过母函数,可以得到G(N)另一种形式的解析表达式.本文将在此基础上,进一步得到利用率的解析表达式,分析其特性,并研究同顾客总数N以及其他参数(如平均服务时间)之间的关系.

3 闭环Jackson网络的资源利用率分析

在本节中,首先尝试得到闭环Jackson网络中利用率的解析表达式,进而对利用率进行分析,得到利用率的极限,并证明利用率的饱和性.然后以一个具体的排队网络为例,求解出其达到饱和状态需要投入的资源数量.

引理1 闭环Jackson网络中,各节点的利用率满足

则可以将ρ相等的节点合并,转换为节点数等于M −1的情况.

对于给定的节点数M,G(N)是关于顾客总数N的数列.对于数列G(N),其母函数h(x)的定义为

其中Ai满足

证毕.

所以节点利用率Ui是饱和函数.也就是说,不论转移概率矩阵和各节点的服务率如何变化,当顾客总数N增大时,利用率Ui总能进入饱和状态,这样一来就可以求出进入饱和状态所需要的顾客总数N,作为在实际系统中投入相应资源数量的参考.

下面针对一个具体的3节点闭环Jackson网络(如图1),分析其利用率的解析表达式,并计算使其达到饱和需要的顾客数量.

图1 3节点闭环Jackson网络Fig.1 Closed Jackson network with 3 nodes

U1的函数图像如图2所示;U1的导数图像如图3所示.

图2 节点1的利用率Fig.2 The utilization of node 1

图3 节点1利用率关于N的导数Fig.3 Derivative of the utilization of node 1

代入到利用率U1中,并将节点2和3的平均服务时间固定,t2=t3=10 s.改变节点1的平均服务时间,分别使t1=1 s,5 s,10 s,20 s,50 s,100 s,求得相应的达到饱和所需顾客总数记录在表1中.

表1 不同平均服务时间的饱和点Table 1 Saturation point of different mean service time

可以看到,随着服务时间的增大,达到饱和状态所需要的顾客总数先增大后减小.这是因为t1≤5的情况中,节点1不是网络的瓶颈,这时增大该节点的服务时间,可以使得各节点负载更均衡,从而投入更多的顾客才能达到饱和状态.超过5 s的情况中,节点1已经成为网络的瓶颈所在,继续增大节点1的服务时间,会使得更多的顾客拥塞在节点1处,所以达到饱和状态所需的顾客总数不断下降.

4 在自动化码头中的应用

现如今,超过90%的全球贸易是通过船舶运输[16].集装箱运输是全球货物运输的重要组成部分,集装箱年运输量在过去40年中增长了近15倍[17].集装箱码头作为集装箱船装货和卸货的节点,承担了水陆货运枢纽的职能.在一些繁忙的港口,集装箱码头每天都需要为大量的集装箱船舶提供装卸服务.近些年,集装箱船的装卸任务越来越集中于大型的区域中心集装箱港口,使得这些关键港口的负荷日益增大.2015年,全球20个最大的集装箱港的吞吐量达到了3.12亿标准箱TEU,占全球总量的45%[18].

随着无线通信、控制系统、传感器等相关技术的快速发展,现在已经可以通过自动导引车(automated guided vehicles,AGV)来实现港口的自动化[19].配备了AGV和其他自动化设施的集装箱码头被称为自动化集装箱码头(ACTs).

自动化集装箱码头的一种经典布局方式如图4[20].在卸货任务中,AGV到达指定的岸桥位置,岸桥(岸边起重机)将集装箱从船上吊起并放置在AGV上.然后AGV到达指定的堆场位置,场桥(堆场起重机)将集装箱从AGV上吊起并放置在堆场里预先分配的位置.在装货任务中,这些步骤是相反的.

图4 自动化码头布局图Fig.4 Layout of an automated container terminal

虽然与人工集装箱码头相比,自动化集装箱码头采用了更先进的技术,但如何高效地运营自动化码头仍然是一个巨大的挑战.自动化码头的运营效率很大程度上取决于调度策略,不适当的调度策略会导致严重的拥堵.已经有很多研究人员对自动化码头进行研究,并尝试提高其性能.Fazlollahtabar重点研究了调度算法,比较了几种不同的AGV调度和路由优化算法之间的优劣[21].Kim和Bae提出了一个经典的自动化码头布局,这个布局经常被后来的研究者所采用[22].Choe提出了一种动态自适应学习的调度算法[23].Hu设计了一种基于遗传算法来分配集装箱任务顺序的算法[24].Huo建立了一种混合整数规划方法来解决多AGV调度问题[25].

除了调度策略外,自动化集装箱码头运输区域的路网结构也对其运行效率有很大的影响.策略上的进步很多时候无法弥补路网结构设计上存在的缺陷.对不同路网结构的性能进行分析,有助于选择出最优的布局方式.排队网络是分析系统结构的有效并且非常常用的工具.

本文把自动化码头的路网看作是一个有向图.图5是自动化码头案例的有向图示例.1-2号节点代表岸桥;3-8号节点代表交叉路口;9-12号节点“Y”代表场桥.交叉路口、岸桥和场桥用节点表示;道路用边表示.如果边是单向的,那么代表对应的道路是单行道;而如果边是双向的,那么对应的道路应该是双向路.在本例中,这是一个包含12个节点的有向图.

在此基础上,本文将自动化码头抽象为与有向图(图5)具有相同拓扑结构的排队网络.把岸桥、场桥和交叉路口当作服务台,把AGV当作顾客,与服务台节点连接的边具有一定的路由转移概率分布,得到自动化码头排队网络示例如图6所示.

图5 自动化码头的有向图Fig.5 Directed graph of the automated container terminal

图6 自动化码头的排队网络模型Fig.6 Queueing network model

在自动化码头中投入使用的AGV数量通常在装卸任务作业期间是固定的,所以,排队网络的顾客总数是保持不变的.因此,排队网络既没有外部的顾客源节点,也没有外部的目标节点.通过前往港口现场进行实地调研时与相关工作人员的沟通,本文在建模成排队网络工程中让每个节点的服务时间呈指数分布,而且指数分布的服务时间这一假定在码头运行的文献中经常被采用[26-27].同时每一个节点的服务时间都是独立于其他节点的.所以这个排队网络是一个闭环Jackson网络.

在这个排队网络中,本文用如下方法得到路由转移概率:在仿真中采用笔者在之前的论文[21]中所用到的调度策略,让AGV完成集装箱装卸的任务,统计AGV在各节点间进行转移的次数,并将频率作为对应节点之间的转移概率.

由此,本文可以利用前述方法来对自动化码头进行建模与分析.在自动化码头运行中,岸桥和场桥的利用率是重要的指标,可以辅助分析岸桥和场桥是否处于饱和工作状态,以及找出哪个节点是整个排队网络的瓶颈所在.并利用排队网络计算出使得岸桥和场桥利用率达到饱和所需要的车辆总数.

5 结果分析

本文再将该方法运用在由实际场景的自动化码头而建模而来的排队网络,如图6中所示的排队网络.该闭环Jackson网络有12个节点,各节点的编号如图5中所标示.各节点的服务时间服从指数分布,岸桥节点的平均服务时间为40 s,场桥平均服务时间为30 s,路口的平均服务时间为10 s.节点间的转移概率,按照第4节中所述方法统计得到.

该闭环Jackson网络中节点1利用率的函数图像如图7所示.其他节点的利用率和节点1成等比例放大缩小关系,故其变化趋势一致.

图7 自动化码头排队网络模型中节点1的利用率Fig.7 The utilization of node 1 in the queueing network

闭环Jackson网络的利用率的导函数图像如图8所示.该闭环排队网络的利用率是单调递增的右饱和函数.

图8 节点1利用率关于N的导数Fig.8 Derivative of the utilization in the queueing network

求解利用率达到极限值的90%为饱和点,得到车辆总数N∗=21.37.所以使得该排队网络利用率达到饱和状态所需的车辆总数为22辆.

再进一步改变岸桥的平均服务时间,分别让其等于5 s,10 s,20 s,30 s,40 s,60 s,80 s,100 s,120 s,180 s,求得相应的达到饱和所需车辆总数记录在表2中.

表2 不同岸桥平均服务时间对应的饱和点Table 2 Saturation point of different mean service time of quay cranes

可以看到,随着岸桥平均服务时间的增大,使利用率达到饱和状态所需要的车辆总数先增大后减小.这是由岸桥节点是否为排队网络的瓶颈所在的.在岸桥平均服务时间较小时,岸桥不是排队网络的瓶颈,此时如果增大岸桥平均服务时间,达到饱和状态所需要的车辆数也随之增大.而一旦继续增加岸桥平均服务时间,会使得岸桥成为排队网络的瓶颈所在,排队网络中的车辆会主要拥塞在岸桥处,此时投入少量的车,就很容易使得利用率达到饱和状态.

本文在AnyLogic中构建的仿真环境中进行仿真实验.在仿真实验中,各节点的服务时间同样服从指数分布,其平均服务时间与排队网络中的参数一致.车辆的调度采用文献[20]中的方法.图9展示了排队网络模型节点1的利用率的计算结果,并与仿真环境得到的结果进行了比较.排队网络模型的资源利用率的结果与仿真结果具有相同的趋势,且结果非常接近.由此可以看出,利用排队网络模型对系统资源利用率分析是可以得到近似准确的结果的.而且进行仿真实验会耗费大量时间,车辆总数变化时就需要重新开始新的仿真实验才能得到结果.所以排队网络是分析自动化集装箱码头的资源配置效率的一个可行工具.

图9 排队网络建模与仿真岸桥利用率Fig.9 QC utilization by simulation and queueing network

从图9中,发现岸桥的利用率在车辆较少的情况下增长很快.但随着车辆数量的增加,岸桥利用率的增长率逐渐降低.当车辆数量达到22辆时,利用率几乎停止增长.低于22,如果想要增加岸桥的利用率,可以选择增加更多的车辆投入运营.但超过22辆车时,继续投入车辆将无法显著提高利用率,反而会造成拥堵和额外的电力消耗.

6 结论

闭环Jackson网络经常被用来对供应链、生产线以及交通系统等实际系统进行建模.在这些系统中,非常关心各个节点设备的利用率变化趋势,以及判断投入多少资源会使得网络中的设备进入饱和状态.在本文中,基于闭环Jackson网络归一化参数的母函数,得到了利用率的解析表达式.本文给出了利用率在顾客总数N趋于无穷时的极限.此外,还证明了利用率是饱和函数,即当排队网络的顾客总数足够大时,利用率的增长将趋于停滞,这是继续投入资源对系统性能的提升几乎没有帮助.借助利用率的解析表达式以及其特性,可以分析各节点利用率同顾客总数以及服务时间的变化关系,并计算不同服务时间下达到饱和状态所需的顾客总数.

此外,本文还将该方法应用在具体的自动化码头场景中,通过计算各节点的利用率判断瓶颈所在位置.当网络中车辆总数增大时,各节点利用率一开始迅速上升,而随着车辆总数进一步增大,利用率逐渐趋于饱和,增长缓慢.这说明当车辆数增长到一定程度后,继续增加运营车辆,并不会提高运行效率,反而会造成成本增加.利用排队网络对系统进行建模,对资源配置的分析结果同实际出入不大.所以排队网络模型虽然不能用来分析实时动态的策略过程,但可以作为系统资源配置的评价依据.同时使用排队相较于进行仿真实验,可以快速地得到结果,并且能够方便地对参数进行调整.对于各资源利用率而言,排队网络是非常有效而又快速的工具.