基于改進(jìn)GA的分段堆場計(jì)劃調(diào)度方法研究

張志英，計(jì)峰，曾建智

(同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海200092)

分段是船體建造的基本單位，通常一艘船由上百個(gè)分段組成。分段在舾裝、噴漆等工藝處理后需到分段堆場進(jìn)行預(yù)舾裝、檢驗(yàn)和修補(bǔ)等作業(yè)或暫存。脫胎后的分段質(zhì)量幾十至幾百噸。對(duì)進(jìn)場分段，需安排一個(gè)空的作業(yè)場地和一條可行的路徑。由于分段尺寸和質(zhì)量很大，吊車無法對(duì)其進(jìn)行垂直方向上的運(yùn)輸，因而只能在平面上通過平板車運(yùn)輸，一次僅可裝一個(gè)。運(yùn)輸?shù)缆飞先舸嬖诜侄螕醯?，?yīng)先將阻擋分段移至空地，待平板車運(yùn)輸完目標(biāo)分段后，再將阻擋分段移回原處。在實(shí)際堆場作業(yè)中，如何有效降低移動(dòng)成本顯得尤為重要。

分段堆場在生產(chǎn)運(yùn)作中受各種干擾因素影響，如分段優(yōu)先權(quán)關(guān)系變動(dòng)、分段在堆場內(nèi)作業(yè)時(shí)間變動(dòng)等，因此需要根據(jù)系統(tǒng)狀況進(jìn)行分段計(jì)劃的重調(diào)度，以確保分段調(diào)度的順利進(jìn)行。重調(diào)度既避免了實(shí)時(shí)調(diào)度中不考慮全局最優(yōu)的缺陷，又避免了預(yù)測調(diào)度中冗余時(shí)間的浪費(fèi)，是一種兼顧全局和效率的折中方案。關(guān)于重調(diào)度問題的研究主要集中在單臺(tái)機(jī)器、并行機(jī)器、流水車間和作業(yè)車間的重調(diào)度方法、重調(diào)度對(duì)動(dòng)態(tài)制造系統(tǒng)性能的影響等方面［1］。Parviz等研究了在時(shí)間沖突情況下的柔性作業(yè)車間重調(diào)度方法［2］。Sabuncuoglu等探索了機(jī)器可靠性較差條件下的柔性作業(yè)車間重調(diào)度［3］。李鐵克等研究了在機(jī)器故障情況下混合流水車間的重調(diào)度［4］。

船舶分段堆場調(diào)度問題需考慮儲(chǔ)位分配、路徑及計(jì)劃分段的調(diào)度順序等，這與車輛調(diào)度問題有相似之處。Jemai等以優(yōu)化能源為目標(biāo)，利用NSGA II算法研究了車輛調(diào)度問題［5］。Psychas等利用多星NSGA II算法對(duì)多目標(biāo)的車輛調(diào)度問題進(jìn)行求解［6］。Spliet等利用二階段啟發(fā)式算法對(duì)能力約束的車輛重調(diào)度問題進(jìn)行了求解［7］。

國內(nèi)外針對(duì)船舶分段堆場調(diào)度問題的研究較少。Changkyu等以臨時(shí)分段移動(dòng)量最少為目標(biāo)建立優(yōu)化模型，提出遺傳算法和改進(jìn)動(dòng)態(tài)啟發(fā)式算法對(duì)模型進(jìn)行求解［8-9］。然而這些方法都限定分段必須按直線進(jìn)出堆場，增加了臨時(shí)分段移動(dòng)量?？紤]到提升堆場柔性的必要性，申鋼等以臨時(shí)分段移動(dòng)量最小為目標(biāo)建立最短路模型，提出分支定界法和啟發(fā)式規(guī)則來確定分段移動(dòng)路徑和停放位置［10］。徐建祥等提出臨時(shí)場地用于暫時(shí)停放臨時(shí)移動(dòng)分段，利用遺傳算法確定分段在堆場中停放位置的最優(yōu)方案，并構(gòu)建啟發(fā)式規(guī)則來確定分段在堆場中的最優(yōu)進(jìn)、出場路徑［11］。

本文綜合考慮隨機(jī)擾動(dòng)、分段質(zhì)量、場地柔性及堆場形狀等影響因素，以總移動(dòng)成本最小為優(yōu)化目標(biāo)，運(yùn)用改進(jìn)遺傳算法和啟發(fā)式規(guī)則對(duì)分段堆場調(diào)度問題進(jìn)行建模。合理安排分段進(jìn)出堆場順序，確定分段在堆場中的最優(yōu)停放位置，規(guī)劃其進(jìn)、出堆場的路徑，從而優(yōu)化堆場資源的利用率，提高堆場周轉(zhuǎn)率。結(jié)合某大型船廠實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行驗(yàn)證，得出存在隨機(jī)擾動(dòng)下的調(diào)度方案，結(jié)果表明該方案更符合船廠堆場調(diào)度的實(shí)際情況。

1 問題描述與解決方法

1.1 問題描述

堆場是分段脫胎后進(jìn)行后處理或暫存的作業(yè)場所。堆場計(jì)劃分段可分為進(jìn)場分段和出場分段。分段在進(jìn)入或移出堆場的過程中，如有分段堵塞通道，則需將擋道分段先移至別處，等分段到達(dá)目的位置后，擋道分段可回歸原位、重新選位和移至臨時(shí)暫存場所。重新選位和移至臨時(shí)暫存場所雖一定程度上降低了移動(dòng)成本，但前者給分段的定位和查尋帶來不便，后者則占用更多場地資源。分段移動(dòng)成本主要在平板車的油耗和損耗。分段質(zhì)量是影響平板車油耗和損耗的關(guān)鍵因素。平板車運(yùn)輸分段分3個(gè)過程:裝載、運(yùn)輸分段至目的地、卸載。不考慮駕駛員操作水平，天氣等因素，同質(zhì)量分段運(yùn)輸同等距離所需油耗幾乎相等。分段路徑不唯一，造成不等的分段移動(dòng)成本。

在復(fù)雜多變的船舶堆場生產(chǎn)環(huán)境下，各種擾動(dòng)的隨機(jī)發(fā)生導(dǎo)致了堆場運(yùn)作的不確定性。本文主要討論分段延期出場、緊急插單和分段優(yōu)先權(quán)關(guān)系變動(dòng)這3類擾動(dòng)因素。分段延期出場和緊急插單導(dǎo)致后續(xù)分段的調(diào)度環(huán)境因空余作業(yè)場地減少而發(fā)生變化，影響了初始的全局調(diào)度。分段優(yōu)先權(quán)關(guān)系變動(dòng)對(duì)變動(dòng)分段調(diào)度期內(nèi)的環(huán)境造成改變。這些隨機(jī)擾動(dòng)因素影響了船舶堆場的生產(chǎn)進(jìn)度，嚴(yán)重阻礙了堆場物流系統(tǒng)的正常運(yùn)行，因此有必要對(duì)影響物流系統(tǒng)性能的各種擾動(dòng)進(jìn)行重調(diào)度。

對(duì)船舶分段堆場的作業(yè)過程進(jìn)行研究，考慮到調(diào)度的實(shí)際情況及求解計(jì)算方便，作以下假設(shè):1)堆場由若干大小相等的正方形場地組成;2)分段用最小包絡(luò)矩形近似;3)一個(gè)作業(yè)場地只能放一個(gè)分段，一個(gè)分段只能放在一個(gè)作業(yè)場地上;4)各裝卸設(shè)備正常運(yùn)行。要解決的問題有:1)確定進(jìn)場分段在堆場中合適的停放位置;2)確定分段進(jìn)出堆場的最佳路徑。

1.2 解決方法

船舶分段堆場調(diào)度需要在滿足分段后續(xù)作業(yè)需求的前提下，充分考慮調(diào)度周期內(nèi)所有計(jì)劃分段進(jìn)出堆場的順序?qū)Ψ侄瓮７盼恢玫挠绊?，并要?guī)劃好分段路徑。本文通過對(duì)調(diào)度分段所產(chǎn)生油耗的歷史數(shù)據(jù)統(tǒng)計(jì)分類，得到質(zhì)量-距離-成本模型，以總移動(dòng)成本最小化為目標(biāo)，對(duì)于調(diào)度周期內(nèi)的進(jìn)場分段，利用改進(jìn)遺傳方法為其安排停放位置，規(guī)劃其在堆場中的路徑。對(duì)于出場分段則只需根據(jù)其停放位置規(guī)劃出場路徑即可。

2 建立船舶分段堆場調(diào)度模型

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

為表達(dá)分段在堆場中的停放位置以及堆場中作業(yè)場地的狀態(tài)，建立圖1所示的堆場狀態(tài)矩陣。圖1表示的是五行九列作業(yè)場地的堆場，矩陣元素aij為場地狀態(tài)，其值為0或1，1表示某作業(yè)場地上已放有分段，否則為0。

圖1 堆場狀態(tài)矩陣Fig.1 Yard state matrix

2.2 質(zhì)量-距離-成本模型

在平板車運(yùn)輸過程中，分段質(zhì)量越重，移動(dòng)路程越長，平板車油耗越高，相應(yīng)的成本也就越大。對(duì)于同質(zhì)量分段，裝載、運(yùn)輸和卸載過程所需油耗與分段的形狀、駕駛員熟練度、道路濕度有關(guān)，物理學(xué)公式計(jì)算獲取油耗并不適用。本文以10 t作為單位質(zhì)量，以單個(gè)作業(yè)場地的邊長15 m作為單位距離，通過追蹤各個(gè)分段運(yùn)輸油耗并對(duì)同質(zhì)量區(qū)間同距離的油耗歷史數(shù)據(jù)進(jìn)行取平均值處理，得到分段的質(zhì)量-距離-成本模型，如表1所示。模型為

式中:Ai為待調(diào)度的第i個(gè)分段;mi表示分段Ai的質(zhì)量;Vij表示從上至下，從左至右第i行第j列作業(yè)場地;Cij為分段從Vij移至道路所需成本;O(mi，Ri)表示質(zhì)量為mi的分段到道路最優(yōu)距離Ri對(duì)應(yīng)的油耗;f0為當(dāng)前油價(jià)。

表1 質(zhì)量-距離-成本模型表Table 1 Weight-distance-cost model

2.3 重調(diào)度驅(qū)動(dòng)規(guī)則

周期性調(diào)度是按照系統(tǒng)事先安排的調(diào)度周期進(jìn)行周期性重調(diào)度，對(duì)系統(tǒng)缺乏應(yīng)對(duì)各種擾動(dòng)的快速響應(yīng)能力。而事件驅(qū)動(dòng)規(guī)則是針對(duì)突發(fā)事件所采取的調(diào)度策略，即當(dāng)堆場在生產(chǎn)過程中有突發(fā)事件出現(xiàn)，為響應(yīng)這些事件，而必須立即進(jìn)行重調(diào)度。通過采用基于事件驅(qū)動(dòng)的再調(diào)度策略，調(diào)度系統(tǒng)可以較好地響應(yīng)實(shí)際的動(dòng)態(tài)環(huán)境，保持一定的穩(wěn)定性，是實(shí)現(xiàn)動(dòng)態(tài)調(diào)度的一個(gè)較好的策略。例如，當(dāng)某分段的質(zhì)量不滿足驗(yàn)收標(biāo)準(zhǔn)時(shí)，啟動(dòng)重調(diào)度，將序號(hào)位于該分段前的所有分段按原計(jì)劃繼續(xù)調(diào)度，而剩余的分段構(gòu)成重調(diào)度優(yōu)化集，根據(jù)新的調(diào)度順序進(jìn)行重調(diào)度。

2.4 船舶分段堆場調(diào)度模型

2.4.1 概念定義

為了更好的理解模型，做如下定義:

計(jì)劃分段:T周期內(nèi)需要進(jìn)行操作的分段。擋道分段:由于擋道需臨時(shí)移出，最后又移回原位的分段。分段移動(dòng)成本:調(diào)度目標(biāo)分段所需的移動(dòng)成本，包括目標(biāo)分段和擋道分段。總移動(dòng)成本:所有計(jì)劃分段的分段移動(dòng)成本之和。

2.4.2 數(shù)學(xué)模型的建立

堆場作業(yè)計(jì)劃以總移動(dòng)成本最少為優(yōu)化目標(biāo)，對(duì)于進(jìn)場分段，可以將停放位置看作起始點(diǎn)，從停放位置處尋最優(yōu)路徑來簡化模型。參數(shù)設(shè)定如下:

A=((A1，m1)，(A2，m2)…，(Ai，mi)…，(An，mn))為T周期內(nèi)待調(diào)度計(jì)劃分段集，i=1，2…，n;;Ei為分段Ai開始調(diào)度時(shí)，堆場狀態(tài)矩陣中“0”的個(gè)數(shù);(L，W)為作業(yè)場地的尺寸，取L=W=15 m;(Li，Wi)為分段Ai的投影參數(shù);Ri為分段Ai到道路的最優(yōu)距離;Qi為靠近道路端的第i行作業(yè)場地;S=(S1，S2…，Sk…，Sm)為堆場內(nèi)的場地集，k=1，2…，m;Vr為道路對(duì)應(yīng)的節(jié)點(diǎn);Bi為周期內(nèi)第i個(gè)進(jìn)場分段，i=1，2，…，n;B0ij為堆場中第i行，第j列計(jì)劃出場的分段;B-k為周期內(nèi)第k個(gè)進(jìn)場分段在此周期內(nèi)出場;

［ts，tf］為 T 周期的始末時(shí)刻;［tis，tif］為Ai的計(jì)劃周期;P=(P1，P2，…，Pk，…，Pz)為T周期內(nèi)因事件觸發(fā)而導(dǎo)致計(jì)劃上出現(xiàn)異常的分段集(按初始計(jì)劃中的順序依次排列);h為若分段P1需延期進(jìn)出場，則h表示其在初始計(jì)劃中的序號(hào);若P1需提前進(jìn)出場，則h表示其在重調(diào)度計(jì)劃中的序號(hào);Uk為分段Pk的觸發(fā)時(shí)刻;trs為分段Pk重調(diào)度后的計(jì)劃進(jìn)或出場時(shí)刻，rs=1，2…，n;S0為單個(gè)作業(yè)場地的面積;根據(jù)質(zhì)量-距離-成本模型建立以移動(dòng)成本最小為優(yōu)化目標(biāo)的函數(shù):

該模型綜合考慮隨機(jī)擾動(dòng)、分段質(zhì)量、場地柔性和堆場布局等因素，以總移動(dòng)成本最小為優(yōu)化目標(biāo)。函數(shù)(1)逐個(gè)計(jì)算并確定每個(gè)分段的最優(yōu)路徑，得出該方案產(chǎn)生的最少總移動(dòng)成本。運(yùn)用改進(jìn)遺傳算法操作在所有方案中選出最優(yōu)方案來安排堆場計(jì)劃;約束條件(2)限制分段的出場時(shí)間要在T周期內(nèi);約束條件(3)說明需要時(shí)間重排異常分段;約束條件(4)保證作業(yè)場地能容下放置的分段;約束條件(5)限定一個(gè)作業(yè)場地只能放一個(gè)分段。約束條件(6)確保一個(gè)分段只能放置在一個(gè)作業(yè)場地上。約束條件(7)說明相鄰的調(diào)度分段之間的堆場狀態(tài)必定不同。

2.5 改進(jìn)遺傳算法

遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性。本文采用Srinvivas提出的一種自適應(yīng)算法，Pc和Pm能夠隨適應(yīng)度大小自動(dòng)改變［12］。對(duì)于適應(yīng)度高于群體平均適應(yīng)值的個(gè)體，相對(duì)應(yīng)于較低的Pc和Pm，使該解得以保護(hù)進(jìn)入下一代;而低于平均適應(yīng)值的個(gè)體，相對(duì)應(yīng)于較高的Pc和Pm，使該解被淘汰。Pc和Pm按如下公式進(jìn)行自適應(yīng)調(diào)整:

式中:fmax為群體中最大的適應(yīng)度值，favg為每代群體的平均適應(yīng)度值，f'為要交叉兩個(gè)體中較大的適應(yīng)度值，f為要變異個(gè)體的適應(yīng)度值。取適應(yīng)度函數(shù):

3 模型求解

3.1 編碼和解碼

對(duì)于進(jìn)場分段在堆場中可能放置的作業(yè)場地位置，依據(jù)數(shù)學(xué)組合原理，把每種不同的放置組合形成一種調(diào)度方案，即為一個(gè)染色體。

1)編碼:染色體的長度是待調(diào)度分段數(shù)目，其基因排列順序就是分段的調(diào)度順序。每個(gè)基因是一個(gè)二維數(shù)組，對(duì)于進(jìn)場分段，前者的值表示從上至下，從左至右第n個(gè)0作為停放位置，對(duì)于出場分段，則表示其所在位置。數(shù)組后者的值是計(jì)劃分段的質(zhì)量?，F(xiàn)根據(jù)圖1編制一染色體，如圖2所示。

圖2 染色體示例Fig.2 An example for chromosome

基因序號(hào)1～6依次是計(jì)劃分段的調(diào)度順序。3、6號(hào)是出場分段(其他為進(jìn)場分段)，3號(hào)的045代表其在V45，221代表質(zhì)量，6號(hào)的-2表示計(jì)劃分段中第2個(gè)進(jìn)場分段在周期內(nèi)出場。1號(hào)的3代表選擇第3個(gè)空作業(yè)場地作為停放位置。

2)解碼:計(jì)算每個(gè)分段的分段移動(dòng)油耗。具體過程如下:

現(xiàn)在，農(nóng)村相繼成立了合作社，農(nóng)民開始有計(jì)劃地科學(xué)種地。不需要鄉(xiāng)鎮(zhèn)干部瞎指揮了。全鄉(xiāng)除了農(nóng)科站、計(jì)劃生育辦還有點(diǎn)事外，其他人閑來無事，白天不是找借口劃拉個(gè)體戶，就是巧立名目大量開墾生活基地種經(jīng)濟(jì)作物；晚上，喝酒，打麻將——

①建立堆場初始節(jié)點(diǎn)質(zhì)量狀態(tài)模型，如圖3所示。

圖3 堆場初始狀態(tài)圖示例Fig.3 Example of yard initial state

②運(yùn)用動(dòng)態(tài)規(guī)劃:a.Q1～Q5逐行向上搜索得到節(jié)點(diǎn)信息:有無分段、分段質(zhì)量、路徑距離、最優(yōu)路徑、油耗(含擋道分段);b.搜索分向上、向左、向右3種。從Q2行左邊開始向左搜索相鄰節(jié)點(diǎn)的油耗，遇到擋道分段則按其最優(yōu)路徑距離加分段到擋道分段的距離之和作為最短路徑，求此路徑下油耗與擋道分段油耗之和;向右搜索同理，取三者的最小值作為分段移動(dòng)油耗，并更新節(jié)點(diǎn)的最優(yōu)路徑，路徑距離;c.Q3～Q5同Q2，求出各行各節(jié)點(diǎn)信息。

③若是出場分段，則直接獲得分段所在位置的分段移動(dòng)油耗;若是進(jìn)場分段，則將停放位置的質(zhì)量信息修改從而更新整個(gè)堆場的節(jié)點(diǎn)狀態(tài)，即可得到停放位置的分段移動(dòng)油耗信息，乘以油價(jià)即為分段移動(dòng)成本。每完成一個(gè)分段計(jì)劃，堆場節(jié)點(diǎn)信息相應(yīng)的更新一次。

④根據(jù)式(1)對(duì)進(jìn)出場各分段的分段移動(dòng)成本求和，計(jì)算該方案下的總移動(dòng)成本。

3.2 進(jìn)化

采用精英保留戰(zhàn)略，即把適應(yīng)度好的個(gè)體保留下來，并利用其好的性質(zhì)來繁殖后代。同時(shí)采用比例選擇算子，使個(gè)體按照與適應(yīng)度成正比的概率向下一代群體繁殖。設(shè)某染色體的適應(yīng)度為Pi，則其被選擇的概率為Pi/∑Pi。采用多點(diǎn)交叉，對(duì)于選中的用于繁殖的每一對(duì)個(gè)體，隨機(jī)地產(chǎn)生與個(gè)體長度相同的染色體O(所有基因值為0或1)，將雙親的基因，在染色體O的基因中基因值為1對(duì)應(yīng)的位置處相互交換?，F(xiàn)有個(gè)體X、Y，根據(jù)交叉規(guī)則，在隨機(jī)染色體O的基因中值為1處交叉產(chǎn)生新個(gè)體X'、Y'，它們組合了父輩個(gè)體的特征，如圖4所示。變異方式是先以一定概率從種群中選擇一個(gè)個(gè)體，再隨機(jī)生成一個(gè)染色體。個(gè)體將在隨機(jī)染色體中所有基因值為1處對(duì)應(yīng)的位置上，用另一隨機(jī)產(chǎn)生的序號(hào)代替它(若是出場分段則不變)。但要注意的是隨機(jī)產(chǎn)生的序號(hào)必須在1～n中產(chǎn)生，n是進(jìn)場分段當(dāng)前堆場狀態(tài)矩陣中0的個(gè)數(shù)上限。例如可從1～5中選取1代替圖5中X染色體的第2個(gè)基因值5。染色體變異如圖5所示。

圖4 染色體交叉圖Fig.4 Crossover of chromosome

圖5 染色體變異圖Fig.5 Mutation of chromosome

3.3 重調(diào)度

調(diào)度過程中若有擾動(dòng)事件發(fā)生，則抽取出所有因擾動(dòng)事件觸發(fā)而導(dǎo)致調(diào)度順序出現(xiàn)異常的分段，并根據(jù)生產(chǎn)具體情況將這些分段與待調(diào)度分段一起進(jìn)行順序重排，然后重復(fù)步驟1)、2)，得到重調(diào)度計(jì)劃。

4 實(shí)例驗(yàn)證與分析

4.1 實(shí)驗(yàn)驗(yàn)證與結(jié)果

為驗(yàn)證所建模型及算法的可行性與正確性，以上海某大型船廠1周內(nèi)的船舶分段堆場計(jì)劃調(diào)度為例，利用JAVA軟件，在處理器為2 GHz，內(nèi)存為4 GB的計(jì)算機(jī)上進(jìn)行求解。實(shí)驗(yàn)包括以下輸入?yún)?shù):1)堆場尺寸及當(dāng)前的使用狀況，即初始狀態(tài);2)一個(gè)周期內(nèi)，進(jìn)出場分段的計(jì)劃數(shù)量、計(jì)劃順序及計(jì)劃時(shí)間;3)遺傳算法參數(shù)設(shè)置如下:種群規(guī)模為100，個(gè)體長度為 37，交叉概率Pc1=0.9，Pc2=0.6，變異概率Pm1=0.1，Pm2=0.001，算法終止代數(shù)為 50。某堆場的初始狀態(tài)如圖6所示，0代表該作業(yè)場地沒有分段占用，非0數(shù)字代表放在該作業(yè)場地的分段質(zhì)量，圖中共有10個(gè)空作業(yè)場地。

按時(shí)間順序排列的一周內(nèi)堆場作業(yè)計(jì)劃如表2，序號(hào)26出場分段B-2的所在位置V5表示它由序號(hào)5的進(jìn)場分段決定。

圖6 堆場的初始狀態(tài)Fig.6 Yard initial state

表2 一周內(nèi)堆場計(jì)劃Table 2 Yard plan for one week

通過算法程序確定進(jìn)場分段在堆場中的停放位置以及進(jìn)出場分段從停放位置到道路Vr的路徑，得到一種較優(yōu)的堆場調(diào)度方案如表3所示。隨著程序的運(yùn)行，個(gè)體的多樣性在第17代后逐漸消失，解開始收斂，收斂時(shí)間為1.224 s，收斂曲線如圖7所示。

為驗(yàn)證重調(diào)度方法的有效性，以質(zhì)量檢驗(yàn)不合格導(dǎo)致分段推遲出場及訂單加急分段提前進(jìn)場兩類擾動(dòng)事件觸發(fā)重調(diào)度系統(tǒng)。現(xiàn)基于預(yù)測控制技術(shù)預(yù)知序號(hào)22的分段B047因質(zhì)量驗(yàn)收不合格而需要延期，在序號(hào)29的分段B14進(jìn)場后出場。序號(hào)33的分段B035因訂單加急在序號(hào)25的分段B13進(jìn)場后出場。結(jié)合滾動(dòng)時(shí)域重排分段的調(diào)度順序，并按時(shí)間順序進(jìn)行二次重調(diào)度，結(jié)果如表4所示(表中灰色表示分段重排后的新順序)。

表3 堆場計(jì)劃調(diào)度方案Table 3 Stockyard plan scheduling scheme

圖7 改進(jìn)遺傳算法收斂曲線Fig.7 Convergence curve of improve genetic algorithm

表4 堆場重調(diào)度方案Table 4 Yard rescheduling solution

4.2 數(shù)值分析

4.2.1 堆場尺寸及初始利用率的比較分析

進(jìn)場分段不同放置位置的組合以及進(jìn)出場路徑的選擇造成了船舶分段堆場調(diào)度問題的復(fù)雜性。表5顯示，總成本及收斂時(shí)間隨著堆場尺寸和計(jì)劃分段數(shù)的擴(kuò)大而增加;相同尺寸的堆場，在相同計(jì)劃分段數(shù)的調(diào)度下，初始利用率高的總成本比初始利用率低的高，程序運(yùn)行時(shí)間反之，這是由于初始利用率低的堆場少了擋道分段，進(jìn)出場分段相應(yīng)的移動(dòng)成本變低，且可行解規(guī)模大;堆場的行數(shù)比列數(shù)對(duì)實(shí)驗(yàn)結(jié)果影響更大。

表5 不同參數(shù)的對(duì)比結(jié)果Table 5 Comparison of different factors

4.2.2 算法比較分析

分段進(jìn)出場路徑的選擇使堆場調(diào)度問題復(fù)雜性增強(qiáng)。對(duì)于路徑的求解可以通過Dijkstra算法來優(yōu)化，Dijkstra算法是典型最短路算法，主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止，而此問題包含距離和質(zhì)量2個(gè)因素，故只知相鄰分段的質(zhì)量而無法直接得到分段移動(dòng)成本，需遍歷可能的路徑再逐個(gè)計(jì)算以獲得最優(yōu)路徑。本文將整個(gè)路徑選擇過程劃分為幾個(gè)階段子過程再利用動(dòng)態(tài)規(guī)劃逐個(gè)獲得移出分段的最小成本，從而簡化路徑選擇過程。利用JAVA軟件，在處理器為2.0 GHz，內(nèi)存為4 GB的計(jì)算機(jī)上實(shí)現(xiàn)改進(jìn)Dijkstra算法求解分段移動(dòng)路徑。并將改進(jìn)Dijkstra算法與動(dòng)態(tài)規(guī)劃進(jìn)行對(duì)比，結(jié)果如表6所示。可以發(fā)現(xiàn):隨著堆場規(guī)模的增大，2種算法的耗時(shí)都逐漸地提高，但后者的運(yùn)行時(shí)間明顯小于前者，并且堆場尺寸越小，動(dòng)態(tài)規(guī)劃算法較改進(jìn)Dijkstra算法的優(yōu)越性就更突出。

表6 算法比較分析Table 6 Comparison of algorithms

5 結(jié)束語

通過對(duì)船舶分段堆場的調(diào)度過程進(jìn)行研究，綜合考慮了擾動(dòng)事件、分段質(zhì)量、初始利用率、計(jì)劃分段個(gè)數(shù)、堆場尺寸等因素，通過建模并采用遺傳算法及改進(jìn)的啟發(fā)式規(guī)則對(duì)其進(jìn)行求解。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了方法的有效性和實(shí)用性。由于研究基于較多的假設(shè)，沒有考慮實(shí)際船廠運(yùn)作中平板車、龍門吊的可用性約束及分段進(jìn)出堆場的時(shí)間約束問題，需要進(jìn)一步研究。

［1］李莉，喬非，吳啟迪.半導(dǎo)體制造重調(diào)度研究［J］.中國機(jī)械工程，2006，17(6):612-616.LI Li，QIAO Fei，WU Qidi.Research on rescheduling for semiconductor wafer fabs［J］.China Mechanical Engineering，2006，17(6):612-616.

［2］FATTAHI P，JOLAI F，ARKAT J.Flexible job shop scheduling with overlapping in operations［J］.Applied Mathematical Modelling，2009，33(7):3076-3087.

［3］SABUNCUOGLU I，KARABUK S.Rescheduling frequency in an FMS with uncertain process times and unreliable machines［J］.Journal of Manufacturing Systems，1999，18(4):268-283.

［4］李鐵克，肖擁軍，王柏琳.基于局部性修復(fù)的HFS機(jī)器故障重調(diào)度［J］.管理工程學(xué)報(bào)，2010，4(3):45-49.LI Tieke，XIAO Yongjun，WANG Bolin.HFS rescheduling under machine failures based on local repair［J］.Journal of Industrial Engineering and Engineering Management，2010，4(3):45-49.

［5］JEMAI J，ZEKRI M，MELLOULI K.An NSGA-II algorithm for the green vehicle routing problem［M］//HAO J K，MIDDENDORF M.Evolutionary Computation in Combinatorial Optimization.Berlin:Springer，2012:37-48.

［6］PSYCHAS I D，MARINAKI M，MARINAKIS Y.A parallel multi-start NSGA II algorithm for multiobjective energy reduction vehicle routing problem［C］//Evolutionary Multi-Criterion Optimization.Springer，2015:336-350.

［7］SPLIET R，GABOR A F，DEKKER R.The vehicle rescheduling problem［J］.Computers ＆ Operations Research，2014，43(3):129-136.

［8］PARK C，SEO J.Mathematical modeling and solving procedure of the planar storage location assignment problem［J］.Computers＆ Industrial Engineering，2009，57(3):1062-1071.

［9］PARK C，SEO J.Comparing heuristic algorithms of the planar storage location assignment problem［J］.Transportation Research Part E:Logistics and Transportation Review，2010，46(1):171-185.

［10］張志英，申鋼，劉祥瑞，等.基于最短路算法的船舶分段堆場調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18(9):1982-1990.ZHANG Zhiying，SHEN Gang，LIU Xiangrui，et al.Block storage yard scheduling of shipbuilding based on shortestpath algorithm［J］.Computer Integrated Manufacturing Systems，2012，18(9):1982-1990.

［11］張志英，徐建祥，計(jì)峰.基于遺傳算法的船舶分段堆場調(diào)度研究［J］.上海交通大學(xué)學(xué)報(bào)，2013，47(7):1036-1042.ZHANG Zhiying，XU Jianxiang，JI Feng.Shipbuilding yard scheduling approach based on genetic algorithm［J］.Journal of Shanghai Jiaotong University，2013，47(7):1036-1042.

［12］SRINIVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms［J］.IEEE Transactions on Systems，Man，and Cybernetics，1994，24(4):656-667.