訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型的研究綜述

暨南大學(xué)管理學(xué)院 楊學(xué)全

1 訂單履約系統(tǒng)的排隊(duì)網(wǎng)絡(luò)模型

訂單履約系統(tǒng)是從銷售點(diǎn)接受連續(xù)的訂單流,經(jīng)過一系列的處理，最終將指定的貨物在指定的時(shí)間和地點(diǎn)交付給客戶。制造和生產(chǎn)企業(yè)以及分銷中心處理系統(tǒng)是最常見的訂單履約系統(tǒng)。

以配送中心系統(tǒng)為例,訂單履約包括:挑選(Picking)、包裝(Packing)、裝載(Shipping)三個(gè)階段。挑選通常是通過信息檢索確定貨物在倉庫中的位置，然后使用人工或自動(dòng)傳輸系統(tǒng)將貨物交付到下一個(gè)處理階段。包裝是指根據(jù)將上一階段挑選的貨物合并成為一個(gè)訂單并按照訂單的要求將貨物封裝。裝載是指將包裝合并好的訂單貨物裝上交通工具并準(zhǔn)備好運(yùn)送至客戶的過程。這里所說的訂單履約是指企業(yè)內(nèi)部的處理流程，并非指對(duì)外處理的全部過程。

排隊(duì)網(wǎng)絡(luò)模型的論述最早由J.R.Jackson在1957年提出，從最開始的單服務(wù)臺(tái)單階段系統(tǒng)到多服務(wù)臺(tái)多階段系統(tǒng)，這里我們需要排隊(duì)系統(tǒng)的三個(gè)方面。(1)到達(dá)分布和路徑機(jī)制：描述顧客到達(dá)系統(tǒng)的時(shí)間分布以及接受服務(wù)之后如何轉(zhuǎn)移或離開系統(tǒng)；(2)服務(wù)規(guī)則：規(guī)定系統(tǒng)里的服務(wù)臺(tái)如何處理排隊(duì)的顧客，例如先到先服務(wù)或者帶有優(yōu)先權(quán)的服務(wù)規(guī)則；(3)服務(wù)系統(tǒng)屬性：規(guī)定了系統(tǒng)容納的顧客數(shù)量，服務(wù)臺(tái)的服務(wù)效率以及同時(shí)服務(wù)的客戶數(shù)量等方面的屬性。

在訂單履約系統(tǒng)中，我們將各個(gè)處理階段看成是接受各個(gè)工作站的服務(wù)(工作站代表服務(wù)工人或機(jī)器數(shù)代表服務(wù)臺(tái)的數(shù)量)，這樣我們可以建立訂單履約系統(tǒng)的排隊(duì)網(wǎng)絡(luò)模型，通過對(duì)模型的參數(shù)進(jìn)行分析來衡量系統(tǒng)服務(wù)績(jī)效，同時(shí)通過調(diào)整各個(gè)方面的屬性來提高系統(tǒng)的效率，從而達(dá)到系統(tǒng)優(yōu)化的目標(biāo)。

2 訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型的分類研究

描述排隊(duì)類型的因素包括：相繼到達(dá)間隔時(shí)間分布、服務(wù)時(shí)間分布、服務(wù)臺(tái)的數(shù)目、系統(tǒng)容量限制、客戶源數(shù)目以及服務(wù)規(guī)則。由于訂單履約系統(tǒng)通常需要經(jīng)過單類或多類服務(wù)，以此形成了排隊(duì)網(wǎng)絡(luò)，所以還需要考慮的系統(tǒng)因素為服務(wù)階段數(shù)。

根據(jù)系統(tǒng)特征因素的不同，國內(nèi)外學(xué)者對(duì)不同訂單履約系統(tǒng)進(jìn)行了建模分析，并提出各種優(yōu)化安排方法。以下將系統(tǒng)情況按從簡(jiǎn)單到復(fù)雜的思路，對(duì)其相關(guān)文獻(xiàn)研究做系統(tǒng)歸類的介紹。

2.1 單階段單服務(wù)臺(tái)的訂單履約系統(tǒng)

最簡(jiǎn)單的情況就是單階段單服務(wù)臺(tái)的訂單履約系統(tǒng), Neuts,Marcel F (1978)[1]使用了一種矩陣幾何方法計(jì)算了GI/G/1類型(一般到達(dá)時(shí)間分布、一般服務(wù)時(shí)間分布、單服務(wù)臺(tái))系統(tǒng)的逗留時(shí)間分布。 Morrison,J R等人(2006)[2]將這一種矩陣幾何方法應(yīng)用到了數(shù)學(xué)軟件的編程分析中。Sengupta (1989)在Neuts, Marcel F(1978)在這一方法的基礎(chǔ)上，使用了一種雙變量的馬克洛夫過程處理方法，建立了GI/PH/1(一般到達(dá)時(shí)間分布、相位型服務(wù)時(shí)間分布、單服務(wù)臺(tái)系統(tǒng))的等待時(shí)間和排隊(duì)長(zhǎng)度的分布情況，這一種處理方法是對(duì)Neuts, Marcel F(1978)的矩陣幾何方法的改進(jìn)和演變。

劉建明等人(2010)[3]研究一種具有馬爾科夫調(diào)制服務(wù)時(shí)間的單服務(wù)臺(tái)排隊(duì)系統(tǒng)，分析服務(wù)臺(tái)狀態(tài)的變化過程和排隊(duì)系統(tǒng)的各性能指標(biāo)。王玲(2010)[4]研究了服務(wù)時(shí)間分別服從Erlang分布和指數(shù)分布的兩個(gè)不同服務(wù)臺(tái)并聯(lián)的可修排隊(duì)系統(tǒng)，并考慮了服務(wù)可能發(fā)生故障的情況，求出了系統(tǒng)穩(wěn)態(tài)平衡條件和穩(wěn)態(tài)概率向量的矩陣幾何解。

2.2 單階段多服務(wù)臺(tái)的訂單履約系統(tǒng)

進(jìn)一步考慮的系統(tǒng)情況為單階段多服務(wù)臺(tái)訂單履約系統(tǒng)。Houdt, B V (2010)[5]對(duì)Sengupta(1989)的工作進(jìn)行了擴(kuò)展，驗(yàn)證了GI/PH/1情況下等待時(shí)間分布和排隊(duì)長(zhǎng)度等系統(tǒng)參數(shù)，并將研究擴(kuò)展到了GI/PH/c(一般到達(dá)時(shí)間分布、相位型服務(wù)時(shí)間分布、多服務(wù)臺(tái))情況下，同時(shí)還考慮了多服務(wù)臺(tái)服務(wù)能力不相同的情況。Asmussen和Moller (2001)[6]展示了一種新的計(jì)算方法，可以用于計(jì)算GI/PH/c和MAPI/PH/c情況下的系統(tǒng)等待時(shí)間分布，同時(shí)也考慮了服務(wù)臺(tái)相同和相異的情況。 Whitt(1999)也研究了單階段多服務(wù)臺(tái)的系統(tǒng)問題，但是他更多的考慮了狀態(tài)依賴情況的等待時(shí)間分布，即可以根據(jù)訂單的到達(dá)次序得出該訂單在單階段多服務(wù)臺(tái)系統(tǒng)中的具體的時(shí)間分布。Yao, David D W (1985)開發(fā)了一種逼近算法，用來得出單階段排隊(duì)在到達(dá)時(shí)間和服務(wù)時(shí)間非平穩(wěn)情況下的等待時(shí)間分布。

禹海波(2000,2004)研究了具有馬爾可夫到達(dá)過程的離散時(shí)間排隊(duì)MAP/PH/3網(wǎng)絡(luò)系統(tǒng)，運(yùn)用矩陣幾何解給出了系統(tǒng)平穩(wěn)的充要條件和系統(tǒng)的穩(wěn)態(tài)隊(duì)長(zhǎng)分布，并求出了具體某一顧客到達(dá)時(shí)刻系統(tǒng)匯的隊(duì)長(zhǎng)分布和平均等待時(shí)間。張莉(2007)以碼頭集裝箱裝卸服務(wù)為排隊(duì)模型的研究對(duì)象，建立了碼頭多船服務(wù)的并列式排隊(duì)網(wǎng)絡(luò)，探討了有限資源模式下服務(wù)資源均衡分配問題，并建立了具有更好適應(yīng)性的一般服務(wù)時(shí)間分布的M/G/1型排隊(duì)網(wǎng)絡(luò)模型。王宏勇(2009)在M/M/c/K排隊(duì)模型的基礎(chǔ)上使用單重休假策略，提出一個(gè)擬生滅過程矩陣，利用矩陣幾何解給出了系統(tǒng)穩(wěn)態(tài)隊(duì)長(zhǎng)分布。李驥昭和劉義山(2009)研究顧客、服務(wù)員組成的排隊(duì)系統(tǒng)中隊(duì)長(zhǎng)過程的隨機(jī)比較問題，利用隨機(jī)比較方法對(duì)服務(wù)系統(tǒng)進(jìn)行分析，研究排隊(duì)過程幾個(gè)數(shù)量指標(biāo)，對(duì)成批到達(dá)指數(shù)服務(wù)的多服務(wù)臺(tái)排隊(duì)系統(tǒng)模型進(jìn)行分析，確定了顧客成批到達(dá)，服務(wù)時(shí)間及獨(dú)立同分布，得到了該排隊(duì)系統(tǒng)隊(duì)長(zhǎng)過程的隨機(jī)比較以及隊(duì)長(zhǎng)函數(shù)關(guān)于時(shí)間的凹性和凸性。

2.3 多階段單服務(wù)臺(tái)的訂單履約系統(tǒng)

Shanthikumar Sumita, You Jae Uck等人(2002)對(duì)單服務(wù)臺(tái)多階段的排隊(duì)網(wǎng)絡(luò)進(jìn)行了研究。 Shanthikumar and Sumita(1988)求出了M/G/1系統(tǒng)的近似逗留時(shí)間分布。 You Jae Uck等人(2002)計(jì)算了到達(dá)時(shí)間和服務(wù)時(shí)間為一般分布情況下的系統(tǒng)逗留時(shí)間分布。

馬占有(2006)建立了多級(jí)適應(yīng)性休假的M／G／1型排隊(duì)的較完整的理論框架。唐學(xué)德(2007)研究一類批到達(dá)排隊(duì)系統(tǒng)，單服務(wù)臺(tái)提供兩個(gè)不同階段的服務(wù)，并且考慮空竭服務(wù)單重休假和有負(fù)顧客到達(dá)的情形。李江華(2007)也研究了成批到達(dá)的具有二階段服務(wù)的單服務(wù)員可修排隊(duì)系統(tǒng)，并在此基礎(chǔ)上考慮了系統(tǒng)瞬態(tài)和穩(wěn)態(tài)的排隊(duì)指標(biāo)和可靠性指標(biāo)。

2.4 多階段多服務(wù)臺(tái)的訂單履約系統(tǒng)

最普遍的系統(tǒng)情況為多階段多服務(wù)臺(tái)的訂單履約系統(tǒng)，但這方面研究的相關(guān)文獻(xiàn)較少。Mandelbaum et al.(1998)提出了一種多服務(wù)臺(tái)多階段排隊(duì)的逼近算法，但是該算法只局限于指數(shù)型的到達(dá)和服務(wù)時(shí)間分布情況下的系統(tǒng)。 Kim, Hyun Ho(2009)建立了一種新的模型用于求解多階段多服務(wù)臺(tái)排隊(duì)在到達(dá)和服務(wù)時(shí)間分布為一般分布情況下的系統(tǒng)逗留時(shí)間分布，這個(gè)模型借鑒了Asmussen 和 Mller (2001)的雙變量馬克洛夫過程處理方法和You Jae Uck等人(2002)的無窮小概率向量初始化方法。

沈玉波(2004)研究了任意多個(gè)服務(wù)臺(tái)排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性，以及在優(yōu)先服務(wù)原則下，三服務(wù)臺(tái)重入型網(wǎng)絡(luò)和任意多個(gè)服務(wù)臺(tái)重入型網(wǎng)絡(luò)的擴(kuò)散近似。

3 訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型的研究展望

通過閱讀文獻(xiàn)和分析比較，我們可以對(duì)訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型的研究有總體的了解，并在此基礎(chǔ)上提出新的研究思路。首先，從本文第二部分的訂單履約系統(tǒng)的分類研究中，我們可以看到，訂單履約系統(tǒng)根據(jù)其系統(tǒng)特征因素的復(fù)雜程度，從單階段單服務(wù)臺(tái)系統(tǒng)，到單階段多服務(wù)臺(tái)系統(tǒng)，再到多階段單服務(wù)臺(tái)系統(tǒng)，最終到多階段多服務(wù)系統(tǒng)，前面三種類型的系統(tǒng)研究已經(jīng)相當(dāng)充分，但是最普遍情況的多階段多服務(wù)臺(tái)系統(tǒng)由于問題的復(fù)雜程度高，至今已有的相關(guān)研究成果較少，所以未來訂單履約系統(tǒng)的研究將會(huì)趨向于多階段多服務(wù)臺(tái)系統(tǒng)方面。

此外，對(duì)于狀態(tài)依賴情況以及到達(dá)和服務(wù)時(shí)間間隔為非穩(wěn)定時(shí)變分布的情況的系統(tǒng)效率分析，這方面的研究少之又少。由于履約系統(tǒng)效率的指標(biāo)越來越著重于客戶滿意度，而訂單客戶更加關(guān)注個(gè)別訂單而非總體系統(tǒng)的履約效率，所以狀態(tài)依賴情況方面的研究將會(huì)成為一個(gè)新的熱點(diǎn)。由于現(xiàn)實(shí)情況中系統(tǒng)狀態(tài)因素不是固定不變，非穩(wěn)定時(shí)變分布的到達(dá)和服務(wù)時(shí)間分布更加符合現(xiàn)實(shí)情況，所以這方面的研究也將逐漸得到重視。

最后，由于生產(chǎn)系統(tǒng)在實(shí)際運(yùn)轉(zhuǎn)中的復(fù)雜性，考慮的因素將會(huì)不斷地變化和增加，單純依賴數(shù)學(xué)分析將不能完全適應(yīng)發(fā)展的要求，未來的研究將更多的借助計(jì)算機(jī)模擬和仿真技術(shù)，數(shù)學(xué)分析與計(jì)算機(jī)仿真的結(jié)合將會(huì)是未來研究該問題的重要手段和方法。

4 結(jié)語

本文對(duì)訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型方面已有的研究和文獻(xiàn)進(jìn)行分析，并提出后續(xù)研究工作的展望。

首先，本文介紹了訂單履約系統(tǒng)的基本概念，對(duì)該系統(tǒng)構(gòu)建排隊(duì)網(wǎng)絡(luò)模型的思路進(jìn)行了闡述。然后，在訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型方面，本文根據(jù)系統(tǒng)特征因素的不同，將訂單履約系統(tǒng)根據(jù)其系統(tǒng)特征因素的復(fù)雜程度分為單階段單服務(wù)臺(tái)系統(tǒng)、單階段多服務(wù)臺(tái)系統(tǒng)、多階段單服務(wù)臺(tái)系統(tǒng)以及到多階段多服務(wù)系統(tǒng)，對(duì)各種情況的相關(guān)文獻(xiàn)研究做系統(tǒng)歸類的分析和介紹。最終在訂單履約系統(tǒng)排隊(duì)網(wǎng)絡(luò)模型的研究工作方面，對(duì)多階段多服務(wù)臺(tái)系統(tǒng)研究、非穩(wěn)定時(shí)變分布系統(tǒng)以及系統(tǒng)仿真技術(shù)與數(shù)學(xué)分析相結(jié)合這三個(gè)方面提出了新的展望。

[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調(diào)制服務(wù)時(shí)間的單服務(wù)臺(tái)排隊(duì)近似分析[J].計(jì)算機(jī)仿真JSJZ,2010(01).

[4] 王玲,岳德權(quán),李海英,等.兩個(gè)不同服務(wù)臺(tái)的M/(Ek,M)/2可修排隊(duì)系統(tǒng)的矩陣幾何解[J].運(yùn)籌與管理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).