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

周 健，曹瑞霞，汪 雄

同濟(jì)大學(xué) 機(jī)械工程學(xué)院 工業(yè)工程系，上海 201804

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

周 健，曹瑞霞，汪 雄

同濟(jì)大學(xué) 機(jī)械工程學(xué)院 工業(yè)工程系，上海 201804

1 引言

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

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

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

2 問題描述與解決方法

2.1 問題描述

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

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

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

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

2.2 解決方法

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

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

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

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

步驟如下：

步驟1訓(xùn)練樣本的確定與處理

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

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

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

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

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

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

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

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

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

步驟5訓(xùn)練網(wǎng)絡(luò)，構(gòu)建面向船廠進(jìn)出場段數(shù)的預(yù)測模型。

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

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

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

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

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

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

3.4 場地更新機(jī)制

作業(yè)場地的狀態(tài)隨分段進(jìn)出堆場發(fā)生變化。若安排一個(gè)進(jìn)場分段，則對應(yīng)的停放場地的狀態(tài)將由0變?yōu)?，若是出場分段從堆場中出來，則放置該分段的場地狀態(tài)由1變?yōu)?。臨時(shí)移動(dòng)的分段因?yàn)槠湟瞥龆褕龊笥中柚匦路呕卦恢茫势錉顟B(tài)不變。

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

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

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

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

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

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

dij：路徑rij經(jīng)過的場地?cái)?shù)量；

Grij=(grij1，grij2，…，grijk，…，grijz)為 rij對應(yīng)的臨時(shí)移動(dòng)分段集，k=1，2，…，z；

hrijk：臨時(shí)分段grijk需經(jīng)過的場地?cái)?shù)；

t0：T周期的開始時(shí)間；

tT：T周期的結(jié)束時(shí)間；

ti：Ai出場時(shí)間；

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

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

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

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

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

定義決策變量如下：

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

4 模型求解

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

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

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

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

圖5 階段分解方法

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

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

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

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

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

5 實(shí)例驗(yàn)證與結(jié)果分析

5.1 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

表3 調(diào)度方案

5.2 數(shù)值實(shí)驗(yàn)分析

（1）算法比較分析

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

表4 算法比較分析（單個(gè)分段）

（2）模型可解性分析

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

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

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

6 結(jié)論

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

[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]郝聚民，紀(jì)卓尚，林焰.混合順序作業(yè)堆場BAY優(yōu)化模型[J].大連理工大學(xué)學(xué)報(bào)，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].機(jī)械設(shè)計(jì)與研究，2011（12）：261-264.

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

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

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

啟發(fā)式規(guī)則；分段堆場；預(yù)測調(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.

國家自然科學(xué)基金（No.70872076）；上海市博士后基金項(xiàng)目（No.11R21416500）。

周?。?975—），男，博士，副教授，研究領(lǐng)域?yàn)楣I(yè)工程；曹瑞霞（1988—），女，碩士研究生，研究領(lǐng)域?yàn)楣I(yè)工程；汪雄（1989—），男，碩士研究生，研究領(lǐng)域?yàn)楣I(yè)工程。E-mail：caoruixia1228@163.com

2013-06-07

2013-08-19

1002-8331（2013）23-0221-07