訂單履約系統排隊網絡模型的研究綜述

暨南大學管理學院 楊學全

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).