订单履约系统排队网络模型的研究综述

暨南大学管理学院 杨学全

1 订单履约系统的排队网络模型

订单履约系统是从销售点接受连续的订单流,经过一系列的处理，最终将指定的货物在指定的时间和地点交付给客户。制造和生产企业以及分销中心处理系统是最常见的订单履约系统。

以配送中心系统为例,订单履约包括:挑选(Picking)、包装(Packing)、装载(Shipping)三个阶段。挑选通常是通过信息检索确定货物在仓库中的位置，然后使用人工或自动传输系统将货物交付到下一个处理阶段。包装是指根据将上一阶段挑选的货物合并成为一个订单并按照订单的要求将货物封装。装载是指将包装合并好的订单货物装上交通工具并准备好运送至客户的过程。这里所说的订单履约是指企业内部的处理流程，并非指对外处理的全部过程。

排队网络模型的论述最早由J.R.Jackson在1957年提出，从最开始的单服务台单阶段系统到多服务台多阶段系统，这里我们需要排队系统的三个方面。(1)到达分布和路径机制：描述顾客到达系统的时间分布以及接受服务之后如何转移或离开系统；(2)服务规则：规定系统里的服务台如何处理排队的顾客，例如先到先服务或者带有优先权的服务规则；(3)服务系统属性：规定了系统容纳的顾客数量，服务台的服务效率以及同时服务的客户数量等方面的属性。

在订单履约系统中，我们将各个处理阶段看成是接受各个工作站的服务(工作站代表服务工人或机器数代表服务台的数量)，这样我们可以建立订单履约系统的排队网络模型，通过对模型的参数进行分析来衡量系统服务绩效，同时通过调整各个方面的属性来提高系统的效率，从而达到系统优化的目标。

2 订单履约系统排队网络模型的分类研究

描述排队类型的因素包括：相继到达间隔时间分布、服务时间分布、服务台的数目、系统容量限制、客户源数目以及服务规则。由于订单履约系统通常需要经过单类或多类服务，以此形成了排队网络，所以还需要考虑的系统因素为服务阶段数。

根据系统特征因素的不同，国内外学者对不同订单履约系统进行了建模分析，并提出各种优化安排方法。以下将系统情况按从简单到复杂的思路，对其相关文献研究做系统归类的介绍。

2.1 单阶段单服务台的订单履约系统

最简单的情况就是单阶段单服务台的订单履约系统, Neuts,Marcel F (1978)[1]使用了一种矩阵几何方法计算了GI/G/1类型(一般到达时间分布、一般服务时间分布、单服务台)系统的逗留时间分布。 Morrison,J R等人(2006)[2]将这一种矩阵几何方法应用到了数学软件的编程分析中。Sengupta (1989)在Neuts, Marcel F(1978)在这一方法的基础上，使用了一种双变量的马克洛夫过程处理方法，建立了GI/PH/1(一般到达时间分布、相位型服务时间分布、单服务台系统)的等待时间和排队长度的分布情况，这一种处理方法是对Neuts, Marcel F(1978)的矩阵几何方法的改进和演变。

刘建明等人(2010)[3]研究一种具有马尔科夫调制服务时间的单服务台排队系统，分析服务台状态的变化过程和排队系统的各性能指标。王玲(2010)[4]研究了服务时间分别服从Erlang分布和指数分布的两个不同服务台并联的可修排队系统，并考虑了服务可能发生故障的情况，求出了系统稳态平衡条件和稳态概率向量的矩阵几何解。

2.2 单阶段多服务台的订单履约系统

进一步考虑的系统情况为单阶段多服务台订单履约系统。Houdt, B V (2010)[5]对Sengupta(1989)的工作进行了扩展，验证了GI/PH/1情况下等待时间分布和排队长度等系统参数，并将研究扩展到了GI/PH/c(一般到达时间分布、相位型服务时间分布、多服务台)情况下，同时还考虑了多服务台服务能力不相同的情况。Asmussen和Moller (2001)[6]展示了一种新的计算方法，可以用于计算GI/PH/c和MAPI/PH/c情况下的系统等待时间分布，同时也考虑了服务台相同和相异的情况。 Whitt(1999)也研究了单阶段多服务台的系统问题，但是他更多的考虑了状态依赖情况的等待时间分布，即可以根据订单的到达次序得出该订单在单阶段多服务台系统中的具体的时间分布。Yao, David D W (1985)开发了一种逼近算法，用来得出单阶段排队在到达时间和服务时间非平稳情况下的等待时间分布。

禹海波(2000,2004)研究了具有马尔可夫到达过程的离散时间排队MAP/PH/3网络系统，运用矩阵几何解给出了系统平稳的充要条件和系统的稳态队长分布，并求出了具体某一顾客到达时刻系统汇的队长分布和平均等待时间。张莉(2007)以码头集装箱装卸服务为排队模型的研究对象，建立了码头多船服务的并列式排队网络，探讨了有限资源模式下服务资源均衡分配问题，并建立了具有更好适应性的一般服务时间分布的M/G/1型排队网络模型。王宏勇(2009)在M/M/c/K排队模型的基础上使用单重休假策略，提出一个拟生灭过程矩阵，利用矩阵几何解给出了系统稳态队长分布。李骥昭和刘义山(2009)研究顾客、服务员组成的排队系统中队长过程的随机比较问题，利用随机比较方法对服务系统进行分析，研究排队过程几个数量指标，对成批到达指数服务的多服务台排队系统模型进行分析，确定了顾客成批到达，服务时间及独立同分布，得到了该排队系统队长过程的随机比较以及队长函数关于时间的凹性和凸性。

2.3 多阶段单服务台的订单履约系统

Shanthikumar Sumita, You Jae Uck等人(2002)对单服务台多阶段的排队网络进行了研究。 Shanthikumar and Sumita(1988)求出了M/G/1系统的近似逗留时间分布。 You Jae Uck等人(2002)计算了到达时间和服务时间为一般分布情况下的系统逗留时间分布。

马占有(2006)建立了多级适应性休假的M／G／1型排队的较完整的理论框架。唐学德(2007)研究一类批到达排队系统，单服务台提供两个不同阶段的服务，并且考虑空竭服务单重休假和有负顾客到达的情形。李江华(2007)也研究了成批到达的具有二阶段服务的单服务员可修排队系统，并在此基础上考虑了系统瞬态和稳态的排队指标和可靠性指标。

2.4 多阶段多服务台的订单履约系统

最普遍的系统情况为多阶段多服务台的订单履约系统，但这方面研究的相关文献较少。Mandelbaum et al.(1998)提出了一种多服务台多阶段排队的逼近算法，但是该算法只局限于指数型的到达和服务时间分布情况下的系统。 Kim, Hyun Ho(2009)建立了一种新的模型用于求解多阶段多服务台排队在到达和服务时间分布为一般分布情况下的系统逗留时间分布，这个模型借鉴了Asmussen 和 Mller (2001)的双变量马克洛夫过程处理方法和You Jae Uck等人(2002)的无穷小概率向量初始化方法。

沈玉波(2004)研究了任意多个服务台排队网络的稳定性，以及在优先服务原则下，三服务台重入型网络和任意多个服务台重入型网络的扩散近似。

3 订单履约系统排队网络模型的研究展望

通过阅读文献和分析比较，我们可以对订单履约系统排队网络模型的研究有总体的了解，并在此基础上提出新的研究思路。首先，从本文第二部分的订单履约系统的分类研究中，我们可以看到，订单履约系统根据其系统特征因素的复杂程度，从单阶段单服务台系统，到单阶段多服务台系统，再到多阶段单服务台系统，最终到多阶段多服务系统，前面三种类型的系统研究已经相当充分，但是最普遍情况的多阶段多服务台系统由于问题的复杂程度高，至今已有的相关研究成果较少，所以未来订单履约系统的研究将会趋向于多阶段多服务台系统方面。

此外，对于状态依赖情况以及到达和服务时间间隔为非稳定时变分布的情况的系统效率分析，这方面的研究少之又少。由于履约系统效率的指标越来越着重于客户满意度，而订单客户更加关注个别订单而非总体系统的履约效率，所以状态依赖情况方面的研究将会成为一个新的热点。由于现实情况中系统状态因素不是固定不变，非稳定时变分布的到达和服务时间分布更加符合现实情况，所以这方面的研究也将逐渐得到重视。

最后，由于生产系统在实际运转中的复杂性，考虑的因素将会不断地变化和增加，单纯依赖数学分析将不能完全适应发展的要求，未来的研究将更多的借助计算机模拟和仿真技术，数学分析与计算机仿真的结合将会是未来研究该问题的重要手段和方法。

4 结语

本文对订单履约系统排队网络模型方面已有的研究和文献进行分析，并提出后续研究工作的展望。

首先，本文介绍了订单履约系统的基本概念，对该系统构建排队网络模型的思路进行了阐述。然后，在订单履约系统排队网络模型方面，本文根据系统特征因素的不同，将订单履约系统根据其系统特征因素的复杂程度分为单阶段单服务台系统、单阶段多服务台系统、多阶段单服务台系统以及到多阶段多服务系统，对各种情况的相关文献研究做系统归类的分析和介绍。最终在订单履约系统排队网络模型的研究工作方面，对多阶段多服务台系统研究、非稳定时变分布系统以及系统仿真技术与数学分析相结合这三个方面提出了新的展望。

[1] Neuts M F. Structured stochastic matrices of M/G/1 type and their applications[M].CRC,1989.

[2] Morrison J R, Bortnick B, Martin D P. Performance Evaluation of Serial Photolithography Clusters: Queueing Models[C]. Throughput and Workload Sequencing,2006.

[3] 刘建明,王瑞,张良,等.Markov调制服务时间的单服务台排队近似分析[J].计算机仿真JSJZ,2010(01).

[4] 王玲,岳德权,李海英,等.两个不同服务台的M/(Ek,M)/2可修排队系统的矩阵几何解[J].运筹与管理YCGL,2010(04).

[5] Houdt B V. A Phase-Type Representation for the Queue Length Distribution of a Semi-Markovian Queue[C].2010.

[6] Asmussen S, M!ller J. Calculation of the Steady State Waiting Time Distribution in GI/PH/c and MAP/PH/c Queues[J].Queueing Systems,2001,37(1).