周 健，曹瑞霞，汪 雄

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

分段堆場(chǎng)預(yù)測(cè)調(diào)度研究

周 健，曹瑞霞，汪 雄

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

1 引言

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

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

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

2 問(wèn)題描述與解決方法

2.1 問(wèn)題描述

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

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

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

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

2.2 解決方法

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

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

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

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

步驟如下：

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

為監(jiān)控訓(xùn)練過(guò)程，使之不發(fā)生“過(guò)擬合”和評(píng)價(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ù)變化范圍，因此需要對(duì)樣本進(jìn)行歸一化處理。

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

通過(guò)對(duì)影響進(jìn)出場(chǎng)段數(shù)的因素分析，本文選取天氣、設(shè)備、船東檢驗(yàn)這3個(gè)因素作為神經(jīng)網(wǎng)絡(luò)的輸入，日進(jìn)出場(chǎng)段數(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ù)測(cè)。隱含層節(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)來(lái)確定。本文通過(guò)神經(jīng)網(wǎng)絡(luò)訓(xùn)練來(lái)確定隱含層的節(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ò)三種樣本誤差和相關(guān)系數(shù)的對(duì)比，確定最佳的隱含層節(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í)過(guò)程的穩(wěn)定性受學(xué)習(xí)率的影響，為保證學(xué)習(xí)過(guò)程的收斂性，本文選取較小的學(xué)習(xí)率；由于在神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練過(guò)程中，對(duì)有限的樣本進(jìn)行反復(fù)訓(xùn)練可能會(huì)造成網(wǎng)絡(luò)的過(guò)擬合現(xiàn)象，因此在實(shí)際模型訓(xùn)練中采用設(shè)定最大迭代次數(shù)和訓(xùn)練目標(biāo)來(lái)避免。

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

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

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

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

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

為了求得分段移動(dòng)路徑上的臨時(shí)分段數(shù)，將堆場(chǎng)中的作業(yè)場(chǎng)地和道路用節(jié)點(diǎn)表示，建立分段堆場(chǎng)節(jié)點(diǎn)狀態(tài)模型。堆場(chǎng)中作業(yè)場(chǎng)地(m，n，h)表示對(duì)應(yīng)的節(jié)點(diǎn)。道路用一個(gè)名為V0的節(jié)點(diǎn)表示，其狀態(tài)始終為0。每個(gè)節(jié)點(diǎn)有上下左右四個(gè)方向，路徑必然經(jīng)過(guò)節(jié)點(diǎn)的其中兩個(gè)方向。若節(jié)點(diǎn)狀態(tài)為1，則其四個(gè)方向的路權(quán)為0.5，否則為0。因此，在分段進(jìn)出堆場(chǎng)的路徑上，每經(jīng)過(guò)一個(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ī)則，可以將任意堆場(chǎng)轉(zhuǎn)換為節(jié)點(diǎn)狀態(tài)模型。由此，分段進(jìn)、出堆場(chǎng)時(shí)，依照某路徑從起始位置到達(dá)目標(biāo)位置過(guò)程中需經(jīng)過(guò)的臨時(shí)分段數(shù)，可通過(guò)計(jì)算節(jié)點(diǎn)狀態(tài)模型中對(duì)應(yīng)路徑上分段起始位置節(jié)點(diǎn)與目標(biāo)位置節(jié)點(diǎn)間的距離，并將其數(shù)值取整數(shù)后得到。

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

3.4 場(chǎng)地更新機(jī)制

作業(yè)場(chǎng)地的狀態(tài)隨分段進(jìn)出堆場(chǎng)發(fā)生變化。若安排一個(gè)進(jìn)場(chǎng)分段，則對(duì)應(yīng)的停放場(chǎng)地的狀態(tài)將由0變?yōu)?，若是出場(chǎng)分段從堆場(chǎng)中出來(lái)，則放置該分段的場(chǎng)地狀態(tài)由1變?yōu)?。臨時(shí)移動(dòng)的分段因?yàn)槠湟瞥龆褕?chǎng)后又需重新放回原位置，故其狀態(tài)不變。

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

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

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

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

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

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

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

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

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

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

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

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

S0：?jiǎn)蝹€(gè)作業(yè)場(chǎng)地的面積；

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

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

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

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

定義決策變量如下：

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

4 模型求解

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

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

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

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

圖5 階段分解方法

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

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

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

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

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

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

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

以下通過(guò)上海某大型船廠記錄的半年內(nèi)每天的天氣情況、設(shè)備好壞、船東檢驗(yàn)與否和進(jìn)出場(chǎng)段數(shù)等信息來(lái)預(yù)測(cè)未來(lái)一周內(nèi)進(jìn)出場(chǎng)段數(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ù)對(duì)比

從表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ù)測(cè)模型取11個(gè)隱含層節(jié)點(diǎn)。

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

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

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

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

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

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

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

表3 調(diào)度方案

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

（1）算法比較分析

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

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

（2）模型可解性分析

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

（3）預(yù)測(cè)對(duì)堆場(chǎng)調(diào)度的重要性分析

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

6 結(jié)論

本文通過(guò)對(duì)船舶分段堆場(chǎng)實(shí)際情況的了解，作出合理的進(jìn)出場(chǎng)段數(shù)預(yù)測(cè)，改善不確定環(huán)境下的調(diào)度計(jì)劃執(zhí)行度，并綜合考慮了初始利用率、計(jì)劃分段個(gè)數(shù)、堆場(chǎng)尺寸等因素，通過(guò)建模并采用分支定界法及啟發(fā)式算法對(duì)其進(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è)堆場(chǎng)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]陶寧蓉，蔣祖華，毛祖杰，等.船體分段堆場(chǎng)調(diào)度模型與算法研究[J].機(jī)械設(shè)計(jì)與研究，2011（12）：261-264.

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

[15]李巧云，王冰，王曉明.隨機(jī)機(jī)器故障下單機(jī)預(yù)測(cè)調(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

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

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

國(guó)家自然科學(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