分段堆場預測調度研究

周 健，曹瑞霞，汪 雄

同濟大學 機械工程學院 工業工程系，上海 201804

分段堆場預測調度研究

周 健，曹瑞霞，汪 雄

同濟大學 機械工程學院 工業工程系，上海 201804

1 引言

船舶分段堆場是船企不可或缺的重要資源，是分段脫胎后進行后處理的堆放或暫存的場所。由于受一些因素的影響，比如天氣、設備、船東檢驗等，分段脫胎后與后續工序之間的周轉流動并非“即時無縫”連接，導致脫胎的分段不能及時送往船塢搭載，造成大量的庫存積壓、道路堵塞、各種潛在的質量問題等，從而大大增加了對堆場資源的需求，同時，人為預測的進出場段數并沒有考慮這些因素的影響，也導致了實際執行的調度計劃與所排計劃偏差較大。實際上，堆場不堪負荷，已成為限制船廠物流系統正常運轉的瓶頸。另外，由于不合理的調度機制和缺乏有效的管理信息系統，分段處于無序堆放狀態，給生產管理帶來很多問題。因此，對船舶分段堆場的調度進行研究并通過預測制定合理的堆場調度計劃已迫在眉睫。

面向船舶制造的分段堆場調度屬于二維空間平面調度問題，但此類問題類似于集裝箱堆場調度問題。針對集裝箱的翻箱量問題，有學者通過建立最小生成樹模型，并運用動態規劃方法和啟發式算法求解模型確定最小翻箱量[1-5]。文獻[6]考慮集裝箱碼放順序的全序關系，設計單箱碼放算法求解動態碼放模型。文獻[7]以最小化翻箱率為目標，建立兩階段優化模型，研究集中到達和分散到達兩種進場模式下的優化效果，并進行仿真模擬。文獻[8]運用啟發式算法討論了考慮集裝箱重量等級的翻箱量最小化問題。文獻[9]建立考慮集裝箱重量的出口箱區堆存模型并利用搜索技術求解該模型。文獻[10]以圖搜索和模式識別技術為基礎建立了出口箱混合順序作業堆場貝優化模型。集裝箱堆場調度中箱位分配和翻箱量類似于船舶堆場中的分段停放位置和臨時移動分段數量，但兩者的堆放規則不同，前者屬于分層堆放，而后者是平面堆放。目前國內外專門針對這類問題的研究較少，Changkyu等以臨時分段移動量最少為目標建立優化模型，提出遺傳算法和改進動態啟發式算法對模型進行求解[11-12]。蔣祖華等通過設定特定的調度規則，并運用啟發式調度算法求解堆場調度模型[13]。然而這些方法都是在假定堆場場地固化（場地上用于騰空擺放分段的設施缺乏柔性）的生產環境中進行，從而限定分段在堆場中的移動路徑，導致分段必須筆直地進出堆場，大大增加了臨時分段移動量。針對預測調度問題，文獻[14]對不確定環境下的Job Shop調度，分析生產干擾及其擴散效應的隨機性特征，提出了一種基于設備整體效能（OEE）的具有魯棒性的預測調度實現方法。文獻[15]研究基于一定概率分布對機器故障的預測描述，利用插入時間冗余的預測調度方法使初始調度方案具有一定的抗干擾能力，使未來實現調度與預測調度盡量保持一致性。

本文用BP神經網絡對未來一個周期內的進出場段數進行預測，并以分段移動度最小為優化目標，運用分支定界法和啟發式規則對分段在堆場中的調度問題進行建模。合理安排分段進出堆場順序，確定分段在堆場中的最優停放位置，規劃其進、出堆場的移動路徑，從而優化堆場資源的利用率，提高堆場周轉率。并結合某船廠實際數據對模型進行了實例驗證。

2 問題描述與解決方法

2.1 問題描述

由于受到一些外在因素的影響，實際進出場段數與理論段數之間存在偏差，必將導致調度計劃的執行力減弱。因此提前對未來一個周期內的進出場段數進行預測顯得十分必要。

分段按其在堆場中的作業類型可分為進場分段、出場分段。進場分段是脫胎后，要移進堆場進行后續處理或暫存的分段；出場分段是指在堆場中完成了后續處理或暫存，運往船塢搭載等后續工位的分段。臨時分段是指對分段進入或移出堆場過程造成阻礙的分段。在調度過程中需要先將臨時分段移至道路或臨時場地上，等計劃分段到達目的位置后，再將其移回原處。分段移動度指平板車在堆場中搬運進、出場分段到目的地整個過程的移動難度。在搬運過程中，若平板車遇到1個臨時分段，則移動度增加α。為了區別相同臨時移動分段數的路徑而定義系數 β，β是指平板車經過1個場地的移動難度。由于平板車搬運一個分段的成本遠高于經過一個場地的成本。因此，α?β，本文取α=1，β=0.000 1。分段進、出堆場的移動路徑并不唯一，不同的移動路徑具有不等的分段移動度。

考慮到分段堆場的實際情況及便于堆場調度問題的研究，假設為：（1）分段按計劃時間進、出堆場，不存在提前、延期和占先；（2）分段進出堆場的道路確定且唯一；（3）堆場由若干大小相等的正方形場地組成；（4）分段用最小包絡矩形近似；（5）一個作業場地只能放一個分段；（6）各裝卸設備正常運行；（7）臨時分段只能移動到道路或與其相鄰的四個臨時場地上，而且完成分段移動后，臨時分段須移回原處。要解決的問題有：（1）確定進場分段在堆場中合適的停放位置；（2）確定分段進出堆場的最佳移動路徑。船舶分段堆場調度如圖1所示。

圖1 船舶分段堆場調度示意圖

2.2 解決方法

本文以船廠過去半年的實際進出場段數為樣本，綜合考慮天氣情況、設備好壞、船東檢驗與否等實際因素，對未來一個周期內的進出場段數做出預測。同時以分段移動度最小建立目標函數。對于調度周期內的進場分段，首先結合優化目標，利用分支定界法為其安排停放位置，然后規劃其在堆場中的移動路徑。對于出場分段，則只需根據其在堆場中的停放位置規劃出場路徑即可。確定分段的移動路徑需經過兩個步驟：（1）根據啟發式規則求出具有最少臨時分段數的路徑（可能不唯一）。（2）利用臨時場地比較這些可行路徑，具有最小分段移動度的為最優路徑。分段堆場調度流程如圖2所示。

圖2 分段堆場調度流程圖

3 建立分段堆場調度模型

3.1 神經網絡預測模型

步驟如下：

步驟1訓練樣本的確定與處理

為監控訓練過程，使之不發生“過擬合”和評價建立的網絡模型的性能和泛化能力，把樣本集按70%、15%、15%的比例分為訓練樣本、驗證樣本和檢驗樣本。

另外，由于神經網絡的多數學習算法不能適應很寬的數據變化范圍，因此需要對樣本進行歸一化處理。

步驟2神經網絡的輸入輸出

通過對影響進出場段數的因素分析，本文選取天氣、設備、船東檢驗這3個因素作為神經網絡的輸入，日進出場段數作為輸出，即神經網絡的輸入層擁有3個節點，其輸出層擁有1個節點。

步驟3隱含層及隱含層節點數的確定

現有理論證明一個三層BP神經網絡能以任意精度逼近任何非線性函數，故本文選用一個三層BP模型用于預測。隱含層節點數的確定是神經網絡設計中非常重要的一環，隱含層節點數往往根據經驗設計所得經驗和自己進行實驗來確定。本文通過神經網絡訓練來確定隱含層的節點數：首先根據經驗公式（1）確定隱含層節點數目的范圍，設計一個隱含層神經元數目可變的BP網絡，通過三種樣本誤差和相關系數的對比，確定最佳的隱含層節點個數。

其中，n1為隱含層節點數目，n為輸入層節點數目，m為輸出層節點數目，a為0～10之間的任意常數。

步驟4訓練函數及訓練參數的確定

由于Levenberg-Marquardt算法具有收斂速度快，所占內存小和訓練結果好的優點，本文選用訓練函數trainlm；系統學習過程的穩定性受學習率的影響，為保證學習過程的收斂性，本文選取較小的學習率；由于在神經網絡模型訓練過程中，對有限的樣本進行反復訓練可能會造成網絡的過擬合現象，因此在實際模型訓練中采用設定最大迭代次數和訓練目標來避免。

步驟5訓練網絡，構建面向船廠進出場段數的預測模型。

3.2 建立堆場狀態矩陣

為了表示分段在堆場中的停放位置以及堆場中場地的狀態，建立如圖3所示的堆場狀態矩陣。堆場狀態矩陣是一個0-1矩陣，1表示場地上停放著一個且僅有一個分段，0表示場地上沒有分段。圖3表示一個5行9列的堆場，將位于第m行，第n列的作業場地命名為(m，n，h)，其中h是狀態值，若該場地放有分段則其h為1，否則為0。

圖3 堆場狀態矩陣

3.3 堆場節點狀態模型

為了求得分段移動路徑上的臨時分段數，將堆場中的作業場地和道路用節點表示，建立分段堆場節點狀態模型。堆場中作業場地(m，n，h)表示對應的節點。道路用一個名為V0的節點表示，其狀態始終為0。每個節點有上下左右四個方向，路徑必然經過節點的其中兩個方向。若節點狀態為1，則其四個方向的路權為0.5，否則為0。因此，在分段進出堆場的路徑上，每經過一個狀態為1的節點，分段起始位置節點與目標位置節點間的距離就增加1。據此定義，節點間的距離如圖4（a）所示。圖4（b）表示相連節點的狀態模型，即將相鄰節點之間的路權相加。其中將兩個狀態為0的節點之間的距離定為0.001是為了區別不同的0節點。根據以上規則，可以將任意堆場轉換為節點狀態模型。由此，分段進、出堆場時，依照某路徑從起始位置到達目標位置過程中需經過的臨時分段數，可通過計算節點狀態模型中對應路徑上分段起始位置節點與目標位置節點間的距離，并將其數值取整數后得到。

圖4 節點間的距離圖

3.4 場地更新機制

作業場地的狀態隨分段進出堆場發生變化。若安排一個進場分段，則對應的停放場地的狀態將由0變為1，若是出場分段從堆場中出來，則放置該分段的場地狀態由1變為0。臨時移動的分段因為其移出堆場后又需重新放回原位置，故其狀態不變。

3.5 分段堆場調度模型

堆場作業計劃以分段移動度最小為優化目標，對于出場分段，可以將道路看作起始點（即當作已確定位置的進場分段處理），從道路處開始尋最優路徑來簡化模型。參數設定如下：

A=(A1，A2，…，Ai，…，An)為T周期內待調度計劃分段集，i=1，2，…，n；

(L，W)：堆場的尺寸；

(Li，Wi)：分段Ai的投影參數；

Ri=(ri1，ri2，…，rij，…，rim)為分段 Ai的具有最少臨時分段數的路徑集，j=1，2，…，m；

dij：路徑rij經過的場地數量；

Grij=(grij1，grij2，…，grijk，…，grijz)為 rij對應的臨時移動分段集，k=1，2，…，z；

hrijk：臨時分段grijk需經過的場地數；

t0：T周期的開始時間；

tT：T周期的結束時間；

ti：Ai出場時間；

S0：單個作業場地的面積；

tijk：grijk的在場時間，其中臨時分段的在場時間指該分段停留在堆場中所對應的時間；臨時分段grijk本有四個相連場地（上，下，左，右），rij經過了其中兩個場地，定義另外兩個場地為(O1，O2)，稱為臨時場地，其中位于堆場邊上的分段的臨時場地集為（O1）或空集；

Wi：分段Ai開始調度時，堆場狀態矩陣中“0”的個數；

(xv，yv)：T周期內在場分段Sv在堆場中的停放位置（xv，yv分別為堆場的行與列）；

i，j，v，a，b，d均為整數；

定義決策變量如下：

在堆場節點狀態模型中，根據啟發式規則求出的分段可行路徑并不唯一。通過引入臨時場地用于停放臨時分段，本文根據目標函數（2）逐個計算并確定每個分段的可行路徑集中具有最小分段移動度的路徑，并得出該方案產生的最小總移動難度。然后運用遺傳操作在所有方案中選出總移動度最小的方案來安排堆場計劃；約束條件（3）限制分段的出場時間要在T周期內；約束條件（4）保證分段Ai出場時，需移動的臨時分段的在場時間要晚于分段的計劃開始時間；約束條件（5）表示作業場地能容下放置的分段；約束條件（6）到（9）限定一個作業場地只能放一個分段；約束條件（10）說明相鄰的調度分段之間的堆場狀態必定不同。

4 模型求解

船舶堆場調度模型求解如下：

（1）應用BP神經網絡預測T周期內進出場段數。

（2）根據堆場狀態矩陣建立堆場節點狀態模型。

其中后階段節點Vij與前階段節點Vmn為相連節點，d(Vij，Vmn)表示兩節點間的距離。運行過程中將所得節點的屬性值放入open表中，把已完成搜索的節點的屬性值放入close表中，刪除open表中屬性值已大于close表屬性值的節點，若有新完成搜索的節點的屬性值小于close的值，則替代原先的屬性值。

圖5 階段分解方法

（4）分別記錄這些路徑所需經過的臨時分段以及這些分段的相鄰場地的狀態，求出θ的值，然后根據公式（2）確定具有最小分段移動度的路徑，并記錄路徑。

（5）按照時間順序依次安排分段堆場計劃。每安排完一個分段，則堆場狀態矩陣更新一次，其對應的堆場節點狀態模型也相應更新一次。

（6）根據公式（2）計算方案產生的分段移動度。

（7）遍歷每一種方案：對于一種方案，依時間順序，一次安排一個分段的堆場計劃，將各個已經安排好計劃的分段產生的臨時分段移動量累加，每安排一個分段的堆場計劃就將累加值和待比較方案產生的臨時分段移動總量比較一次，如果累加值比待比較方案產生的臨時分段移動總量小，則繼續安排后續分段的堆場計劃，否則淘汰該方案；如果該方案的堆場計劃已經安排完，產生的臨時分段移動量累加值小于待比較方案，則將該方案作為新的待比較方案；如果該方案的堆場計劃已經安排完，產生的臨時分段移動量累加值等于待比較方案，則計算該方案下平板車在堆場中的移動距離，將其和待比較方案的平板車在堆場中的移動距離進行比較，若比待比較方案小，則將該方案作為新的待比較方案，否則淘汰該方案。

（8）所有方案都遍歷完后，最后的待比較方案即為最優方案。依據此方案來安排堆場計劃。

5 實例驗證與結果分析

5.1 實例驗證

以下通過上海某大型船廠記錄的半年內每天的天氣情況、設備好壞、船東檢驗與否和進出場段數等信息來預測未來一周內進出場段數。

由經驗公式（1）知隱含層節點數在2～12之間，因此設計一個隱含層數目可變的BP神經網絡，其結果如表1所示。

表1 隱含層節點數對比

從表1中可以看出，在保證訓練誤差0.005 0的情況下，當隱含層節點數取11時，其驗證樣本和檢驗樣本的誤差和相關系數最好，因此，本文的神經網絡預測模型取11個隱含層節點。

預測結果：未來一周內總的進出場段數為55，其中有37個進場分段（從B82依次命名到B118），18個出場分段，若在一周內某進場分段進場后又要從堆場中出來，則其作為出場分段時，所在位置表示為未定的V00。按時間順序排列的一周內堆場計劃如表2所示。

接下來，為驗證所建調度模型及算法的可行性與正確性，利用Visual Studio2010軟件，在處理器為1.2 GHz，內存為2 GB的計算機上對模型進行求解。實驗包括以下輸入參數：（1）堆場尺寸及當前的使用狀況，即初始狀態；（2）一個周期內，進出場分段的數量、順序及計劃時間。

圖6所示堆場有81個作業場地，其中58個場地被占用，Bn為放置在場地上的分段名。

通過算法程序確定進場分段在堆場中的停放位置以及進出場分段從停放位置到道路V0的路徑，得到一種較優的堆場調度方案如表3所示。在表3中，每條移動路徑的第一個位置節點分別是堆場狀態矩陣的行與列）為進出場分段的停放位置。

在實際生產中，分段堆場調度主要是依據調度員的經驗進行調度，不僅需要花費大量人力、物力以及時間，且每次只能安排當天要調度的分段，無法考慮到后續的堆場作業計劃。利用本文所研究的方法，可以一次安排一周及以上的計劃，并且運行算法程序可得到較優的調度方案，充分利用堆場資源，提高作業效率。

表2 一周內堆場計劃

圖6 堆場的初始狀態

表3 調度方案

5.2 數值實驗分析

（1）算法比較分析

每個分段進場堆場都需要確定從道路到目標位置間的最短路徑。分段進出場路徑的選擇造成了堆場調度問題復雜性的增強。對于路徑的求解可以通過迪克斯特拉算法來優化，Dijkstra算法是典型最短路算法，主要特點是以起始點為中心向外層擴展，直到擴展到終點為止，但其遍歷節點的特性增大了算法的耗時。本文將堆場所有節點通過畫菱形的方式歸入不同的階段集，將整個路徑選擇過程劃分為幾個階段子過程，從而簡化路徑選擇過程。利用C#軟件，在處理器為1.2 GHz，內存為2 GB的計算機上實現迪克斯特拉算法求解分段移動路徑。并將迪克斯特拉算法與改進啟發式規則進行對比，結果如表4所示。可看出：隨著堆場規格的增大，兩種算法的耗時都逐漸地提高，但后者的運行時間明顯小于前者，并且堆場尺寸越小，本文算法較Dijkstra算法的優越性就更突出。原因是在確定最優路徑的過程中，后者不需遍歷所有節點，一般在第3或4階段就能找到最優路徑。

表4 算法比較分析（單個分段）

（2）模型可解性分析

在船舶堆場調度問題中，增大堆場的尺寸、增加待調度分段的數量或者降低堆場的初始狀態的利用率（即增大初始狀態中空場地的個數），都將會提高算法求解的難度，算法耗時也會相應變長。其中堆場的尺寸主要是對啟發式算法求解分段的進出場路徑產生影響，而后兩個因素則增加了進場分段在堆場中的放置位置的可行方案數，從而增大求解空間。對于9列9行的81個作業場地的堆場來說，當分段存在的調度方案數超過93 673 816種時，程序運算時間超過半小時。因此本模型可解的規模有限，適用于中小規模堆場調度問題的優化求解，對于大規模堆場調度問題，可考慮結合問題分解策略，將原問題分解轉化成多個中小規模的調度子問題后進行求解。

（3）預測對堆場調度的重要性分析

實際調度中，由于受到擾動因素的影響，系統將被迫進行多次重調度，全局問題將按重調度次數分割為多個局部優化問題，從而影響并降低了調度系統的績效。通過BP神經網絡預測可事先預知未來調度過程中的影響因素，并可事前控制和調整調度計劃，從而減輕干擾因素對調度系統造成的影響。實例中，假設全局問題被2次擾動事件先后分割成3個局部調度問題，而由這3個局部調度所得的臨時分段移動量分別為13、11和1，其總和25超過了由全局調度所得初始方案的分段移動量21，降低了系統的績效。

6 結論

本文通過對船舶分段堆場實際情況的了解，作出合理的進出場段數預測，改善不確定環境下的調度計劃執行度，并綜合考慮了初始利用率、計劃分段個數、堆場尺寸等因素，通過建模并采用分支定界法及啟發式算法對其進行求解。仿真實驗結果驗證了方法的有效性和實用性。

[1]Kirn K H，Park Y M，Ryll K R.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research，2000，124（1）：89-101.

[2]Zhang Canrong，Chen Weiwei，Shi Leyuan，et al.A note on deriving decision rules to locate export containers in containeryards[J].European JournalofOperationalResearch，2010，205：483-485.

[3]Zhang Weiying，Lin Yan，Ji Zhuoshang，et al.Optimization model of constrainers loading operation in export constrainers terminal[J].Journal of Wuhan University of Technology，2006，30（2）：314-317.

[4]Lee Yusin，Chao Shih-liang.A neighborhood search heuristic for pre-marshalling export containers[J].European Journal of Operational Research，2009，196（2）：468-475.

[5]Chung Chia-Shin，Flynn J，Kirca O.A branch and bound algorithm to minimize the total tardiness for m-machine permutation flow shop problems[J].European Journal of Operational Research，2006，174：1-10.

[6]Jiang Nan，Qian Mai，Qu Hong-tao，et al.Model and algorithm ofcontaineryard operation plans[J].Journalofthe China Railway Society，2009，31（5）：8-16.

[7]郝聚民，紀卓尚，林焰.混合順序作業堆場BAY優化模型[J].大連理工大學學報，2000，40（1）：102-105.

[8]Yun W Y，Choi Y S.A simulation model for container-terminal operation analysis using an object oriented approach[J].International Journal of Production Economies，1999，59（3）：311-329.

[9]Zhang Chuqian，Liu Jiyin，Wan Yat-wah，et al.Storage apace allocation in containerterminals[J].Transportation Research Part B，2003，37（10）：429-442.

[10]Kim K H，Won S H，Lim J K，et al.An architectural design of control software for automated container terminals[J]. Computer& Industrial Engineering，2004，46（4）：741-754.

[11]Park C，Seo J.Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers& Industrial Engineering，2009，57：1062-1071.

[12]Park C，Seo J.Comparing heuristic algorithms of the planarstorage location assignmentproblem[J].Transportation Research Part，2010，46：171-185.

[13]陶寧蓉，蔣祖華，毛祖杰，等.船體分段堆場調度模型與算法研究[J].機械設計與研究，2011（12）：261-264.

[14]陳雨，陳新，陳新度.不確定環境下的多Agent魯棒性預測調度研究[J].中國機械工程，2009，16（7）：1937-1942.

[15]李巧云，王冰，王曉明.隨機機器故障下單機預測調度方法[J].系統工程理論與實踐，2011，31（12）.

ZHOU Jian,CAO Ruixia,WANG Xiong

Department of Industrial Engineering,School of Mechanical Engineering,Tongji University,Shanghai 201804,China

The shipbuilding yards scheduling is overly dependent on artificial prediction and scheduling and lack of effective scheduling approach in practical production.The BP neural network is proposed to predict the number of sections which are shipped in and out in one period.Then a mathematical model is defined as the assignment and paths of the inbound and outbound objects to the shipping yard with aim of minimizing the degree of movement of blocks.Then a branch and bound algorithm is formulated to select the optimal parking positions of blocks.And a heuristic algorithm is also proposed to confirm the optimal moving paths of blocks in the yards.Application data are obtained from a shipyard to validate the model,and the result shows that the proposed algorithm is effective to solve the shipbuilding yards scheduling problem.

heuristic regular;shipbuilding yard;predictable scheduling;branch and bound algorithm

針對船舶分段移動計劃主要依靠人為預測及人工調度的現狀，提出BP神經網絡來預測一個周期內進出場分段的數量，并研究建立以分段移動度最小為目標的優化模型，模型綜合考慮了分段在堆場中的停放位置及進、出場路徑。通過分支定界法選擇分段在堆場中停放位置的最優方案，并構建啟發式規則來確定分段在堆場中的最優進、出場路徑，從而實現對模型的求解。以某船廠實際數據為例，對模型在堆場調度問題中的應用進行了實例驗證，結果表明，所研究方法可求解得出較優的堆場作業計劃，并實現堆場資源的高效利用。

啟發式規則；分段堆場；預測調度；分支定界法

A

TP393

10.3778/j.issn.1002-8331.1306-0038

ZHOU Jian,CAO Ruixia,WANG Xiong.Shipbuilding yards predictable scheduling approach.Computer Engineering and Applications,2013,49（23）：221-227.

國家自然科學基金（No.70872076）；上海市博士后基金項目（No.11R21416500）。

周健（1975—），男，博士，副教授，研究領域為工業工程；曹瑞霞（1988—），女，碩士研究生，研究領域為工業工程；汪雄（1989—），男，碩士研究生，研究領域為工業工程。E-mail：caoruixia1228@163.com

2013-06-07

2013-08-19

1002-8331（2013）23-0221-07