周 健，曹瑞霞，汪 雄

同濟大學 機械工程學院 工業(yè)工程系，上海 201804

分段堆場預測調(diào)度研究

周 健，曹瑞霞，汪 雄

同濟大學 機械工程學院 工業(yè)工程系，上海 201804

1 引言

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

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

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

2 問題描述與解決方法

2.1 問題描述

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

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

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

圖1 船舶分段堆場調(diào)度示意圖

2.2 解決方法

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

圖2 分段堆場調(diào)度流程圖

3 建立分段堆場調(diào)度模型

3.1 神經(jīng)網(wǎng)絡預測模型

步驟如下：

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

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

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

步驟2神經(jīng)網(wǎng)絡的輸入輸出

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

步驟3隱含層及隱含層節(jié)點數(shù)的確定

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

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

步驟4訓練函數(shù)及訓練參數(shù)的確定

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

步驟5訓練網(wǎng)絡，構建面向船廠進出場段數(shù)的預測模型。

3.2 建立堆場狀態(tài)矩陣

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

圖3 堆場狀態(tài)矩陣

3.3 堆場節(jié)點狀態(tài)模型

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

圖4 節(jié)點間的距離圖

3.4 場地更新機制

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

3.5 分段堆場調(diào)度模型

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

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

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

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

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

dij：路徑rij經(jīng)過的場地數(shù)量；

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

hrijk：臨時分段grijk需經(jīng)過的場地數(shù)；

t0：T周期的開始時間；

tT：T周期的結束時間；

ti：Ai出場時間；

S0：單個作業(yè)場地的面積；

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

Wi：分段Ai開始調(diào)度時，堆場狀態(tài)矩陣中“0”的個數(shù)；

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

i，j，v，a，b，d均為整數(shù)；

定義決策變量如下：

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

4 模型求解

船舶堆場調(diào)度模型求解如下：

（1）應用BP神經(jīng)網(wǎng)絡預測T周期內(nèi)進出場段數(shù)。

（2）根據(jù)堆場狀態(tài)矩陣建立堆場節(jié)點狀態(tài)模型。

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

圖5 階段分解方法

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

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

（6）根據(jù)公式（2）計算方案產(chǎn)生的分段移動度。

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

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

5 實例驗證與結果分析

5.1 實例驗證

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

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

表1 隱含層節(jié)點數(shù)對比

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

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

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

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

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

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

表2 一周內(nèi)堆場計劃

圖6 堆場的初始狀態(tài)

表3 調(diào)度方案

5.2 數(shù)值實驗分析

（1）算法比較分析

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

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

（2）模型可解性分析

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

（3）預測對堆場調(diào)度的重要性分析

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

6 結論

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

[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，F(xiàn)lynn 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]郝聚民，紀卓尚，林焰.混合順序作業(yè)堆場BAY優(yōu)化模型[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]陶寧蓉，蔣祖華，毛祖杰，等.船體分段堆場調(diào)度模型與算法研究[J].機械設計與研究，2011（12）：261-264.

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

[15]李巧云，王冰，王曉明.隨機機器故障下單機預測調(diào)度方法[J].系統(tǒng)工程理論與實踐，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

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

啟發(fā)式規(guī)則；分段堆場；預測調(diào)度；分支定界法

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—），男，博士，副教授，研究領域為工業(yè)工程；曹瑞霞（1988—），女，碩士研究生，研究領域為工業(yè)工程；汪雄（1989—），男，碩士研究生，研究領域為工業(yè)工程。E-mail：caoruixia1228@163.com

2013-06-07

2013-08-19

1002-8331（2013）23-0221-07