基于改進GA的分段堆場計劃調度方法研究

張志英，計峰，曾建智

(同濟大學機械與能源工程學院，上海200092)

分段是船體建造的基本單位，通常一艘船由上百個分段組成。分段在舾裝、噴漆等工藝處理后需到分段堆場進行預舾裝、檢驗和修補等作業或暫存。脫胎后的分段質量幾十至幾百噸。對進場分段，需安排一個空的作業場地和一條可行的路徑。由于分段尺寸和質量很大，吊車無法對其進行垂直方向上的運輸，因而只能在平面上通過平板車運輸，一次僅可裝一個。運輸道路上若存在分段擋道，應先將阻擋分段移至空地，待平板車運輸完目標分段后，再將阻擋分段移回原處。在實際堆場作業中，如何有效降低移動成本顯得尤為重要。

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

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

國內外針對船舶分段堆場調度問題的研究較少。Changkyu等以臨時分段移動量最少為目標建立優化模型，提出遺傳算法和改進動態啟發式算法對模型進行求解［8-9］。然而這些方法都限定分段必須按直線進出堆場，增加了臨時分段移動量。考慮到提升堆場柔性的必要性，申鋼等以臨時分段移動量最小為目標建立最短路模型，提出分支定界法和啟發式規則來確定分段移動路徑和停放位置［10］。徐建祥等提出臨時場地用于暫時停放臨時移動分段，利用遺傳算法確定分段在堆場中停放位置的最優方案，并構建啟發式規則來確定分段在堆場中的最優進、出場路徑［11］。

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

1 問題描述與解決方法

1.1 問題描述

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

在復雜多變的船舶堆場生產環境下，各種擾動的隨機發生導致了堆場運作的不確定性。本文主要討論分段延期出場、緊急插單和分段優先權關系變動這3類擾動因素。分段延期出場和緊急插單導致后續分段的調度環境因空余作業場地減少而發生變化，影響了初始的全局調度。分段優先權關系變動對變動分段調度期內的環境造成改變。這些隨機擾動因素影響了船舶堆場的生產進度，嚴重阻礙了堆場物流系統的正常運行，因此有必要對影響物流系統性能的各種擾動進行重調度。

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

1.2 解決方法

船舶分段堆場調度需要在滿足分段后續作業需求的前提下，充分考慮調度周期內所有計劃分段進出堆場的順序對分段停放位置的影響，并要規劃好分段路徑。本文通過對調度分段所產生油耗的歷史數據統計分類，得到質量-距離-成本模型，以總移動成本最小化為目標，對于調度周期內的進場分段，利用改進遺傳方法為其安排停放位置，規劃其在堆場中的路徑。對于出場分段則只需根據其停放位置規劃出場路徑即可。

2 建立船舶分段堆場調度模型

2.1 堆場狀態矩陣的建立

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

圖1 堆場狀態矩陣Fig.1 Yard state matrix

2.2 質量-距離-成本模型

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

式中:Ai為待調度的第i個分段;mi表示分段Ai的質量;Vij表示從上至下，從左至右第i行第j列作業場地;Cij為分段從Vij移至道路所需成本;O(mi，Ri)表示質量為mi的分段到道路最優距離Ri對應的油耗;f0為當前油價。

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

2.3 重調度驅動規則

周期性調度是按照系統事先安排的調度周期進行周期性重調度，對系統缺乏應對各種擾動的快速響應能力。而事件驅動規則是針對突發事件所采取的調度策略，即當堆場在生產過程中有突發事件出現，為響應這些事件，而必須立即進行重調度。通過采用基于事件驅動的再調度策略，調度系統可以較好地響應實際的動態環境，保持一定的穩定性，是實現動態調度的一個較好的策略。例如，當某分段的質量不滿足驗收標準時，啟動重調度，將序號位于該分段前的所有分段按原計劃繼續調度，而剩余的分段構成重調度優化集，根據新的調度順序進行重調度。

2.4 船舶分段堆場調度模型

2.4.1 概念定義

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

計劃分段:T周期內需要進行操作的分段。擋道分段:由于擋道需臨時移出，最后又移回原位的分段。分段移動成本:調度目標分段所需的移動成本，包括目標分段和擋道分段。總移動成本:所有計劃分段的分段移動成本之和。

2.4.2 數學模型的建立

堆場作業計劃以總移動成本最少為優化目標，對于進場分段，可以將停放位置看作起始點，從停放位置處尋最優路徑來簡化模型。參數設定如下:

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

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

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

2.5 改進遺傳算法

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

式中:fmax為群體中最大的適應度值，favg為每代群體的平均適應度值，f'為要交叉兩個體中較大的適應度值，f為要變異個體的適應度值。取適應度函數:

3 模型求解

3.1 編碼和解碼

對于進場分段在堆場中可能放置的作業場地位置，依據數學組合原理，把每種不同的放置組合形成一種調度方案，即為一個染色體。

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

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

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

2)解碼:計算每個分段的分段移動油耗。具體過程如下:

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

①建立堆場初始節點質量狀態模型，如圖3所示。

圖3 堆場初始狀態圖示例Fig.3 Example of yard initial state

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

③若是出場分段，則直接獲得分段所在位置的分段移動油耗;若是進場分段，則將停放位置的質量信息修改從而更新整個堆場的節點狀態，即可得到停放位置的分段移動油耗信息，乘以油價即為分段移動成本。每完成一個分段計劃，堆場節點信息相應的更新一次。

④根據式(1)對進出場各分段的分段移動成本求和，計算該方案下的總移動成本。

3.2 進化

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

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

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

3.3 重調度

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

4 實例驗證與分析

4.1 實驗驗證與結果

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

按時間順序排列的一周內堆場作業計劃如表2，序號26出場分段B-2的所在位置V5表示它由序號5的進場分段決定。

圖6 堆場的初始狀態Fig.6 Yard initial state

表2 一周內堆場計劃Table 2 Yard plan for one week

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

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

表3 堆場計劃調度方案Table 3 Stockyard plan scheduling scheme

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

表4 堆場重調度方案Table 4 Yard rescheduling solution

4.2 數值分析

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

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

表5 不同參數的對比結果Table 5 Comparison of different factors

4.2.2 算法比較分析

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

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

5 結束語

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

［1］李莉，喬非，吳啟迪.半導體制造重調度研究［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］李鐵克，肖擁軍，王柏琳.基于局部性修復的HFS機器故障重調度［J］.管理工程學報，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］張志英，申鋼，劉祥瑞，等.基于最短路算法的船舶分段堆場調度［J］.計算機集成制造系統，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］.上海交通大學學報，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.