船廠鋼板堆場多時段作業計劃優化

張志英，王維澤，侯俊

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

在船舶制造中，鋼板堆場是連接外部物流和內部物流的樞紐，承擔著生產所需鋼板的進料、保管和供應職責，是實現精益造船的重要環節，具有以下特點:1)尺寸約束，即同一堆垛中，相鄰的兩塊板尺寸之差不能超過約束值，否則會引起上層板的形變;2)時間約束，每塊鋼板都有固定的入庫時間與出庫時間;3)從多時間段角度，堆場管理屬于多階段決策優化問題，從垛位分配角度，屬于組合優化問題;4)每批次入庫和出庫鋼板數量多，入庫時需要考慮對已入庫和后入庫板的影響，垛位分配難度大，屬于NP-Hard問題。因此，鋼板堆場調度難度大，目前國內外學者對造船廠鋼板堆場問題研究主要有仿真方法和智能算法兩類。仿真方法的主要目的實施現堆場管理自動化。蔣如宏等在分析堆場系統結構特征及堆放規則的基礎上，應用數據庫和計算機仿真技術建立堆場數字化仿真模型［1］;C.Park等用仿真方法研究了堆放場地大小、堆垛計劃日期變化等因素對堆場管理的影響［2］。隨著遺傳算法等智能算法的廣泛運用，金淳等以出庫作業時間最短為目標研究出庫作業，并運用遺傳算法求解模型［3］;劉建峰等結合堆場庫存現狀及鋼板出入庫計劃，采用遺傳算法研究入庫鋼板的分配策略［4］;徐萍等采用遺傳模擬退火算法研究了造船廠的鋼板入庫作業［5］。以上研究將入庫和出庫分開，且應用智能算法求解，運行時間長，只適合解小規模問題。因此，Zhang等建立出庫和入庫的綜合模型，采用貪婪算法實現快速求解［6］，但忽略了堆場倒垛主要是由不同時間段的入庫出庫板相互疊壓引起的。因此，在上述研究的基礎上，建立了一個以減少倒垛量為目標的多時間段鋼板堆場優化模型;提出由動態規劃啟發式算法和變鄰域搜索算法組成的兩階段求解算法，并利用實際生產中的數據驗證其有效性與實用性。

1 問題描述和數學模型

1.1 船廠鋼板管理過程和問題描述

鋼板管理包括鋼板預算、鋼板采購、供貨、鋼板存放、進出庫計劃、切割計劃和余料管理等。文中主要研究鋼板入庫、在庫管理和出庫等過程的計劃安排與優化問題。

1.1.1 鋼板入庫出庫計劃

入庫計劃的目的是為一批到貨鋼板安排合理垛位。理想情況下，先出庫鋼板應該放在上層以減少倒垛量，而實際作業中，每個到達批次包含不同出庫日期的鋼板，先出庫鋼板會被后入庫后出庫的鋼板疊壓，引起倒垛。因此鋼板入庫堆放時不僅要結合當前庫內鋼板的堆放情況，同時要考慮與后期入庫、出庫作業的相互影響。出庫計劃主要根據后道工序的切割計劃編制。為了保證后道工序的順利進行，鋼板必須按時按量在規定的時間節點出庫，而且也不能提前出庫，否則會造成切割鋼板的大量積壓和丟失。

1.1.2 鋼板的在庫管理

圖1所示的鋼板堆場由4個跨組成，每跨包含18個堆垛，在跨內部和跨之間鋼板分別通過橋吊和傳送帶搬運。堆場的每一跨內部主要有3個區域組成:卸貨堆垛、臨時堆放堆垛和上料堆垛。各跨預留馬路兩側的堆垛作為卸貨堆垛，在卸貨堆垛內可以調整入庫順序;為了平衡傳送帶的負荷，同時又不影響橋吊的工作效率，在傳送帶附近設置一些上料堆垛;堆場中余下的堆垛作為臨時堆放堆垛。

圖1 鋼板堆場結構示意圖Fig.1 Structure of steel plate stockyard

在堆場中鋼板首先被卸載在卸貨堆垛，待臨時堆放堆垛中需要出庫的鋼板全部搬運至上料堆垛后，再將卸貨堆垛中的鋼板運至臨時堆放堆垛中合適的垛位。因此堆場作業計劃優化的研究對象是由鋼板從卸貨堆垛進入臨時堆放堆垛的入庫作業，鋼板離開臨時堆放堆垛的出庫作業，以及相關的倒垛作業組成。

1.2 數學模型

假設:

1)每天為一個時間段，多個時間段為一個計劃期;2)計劃期開始前和結束時堆場為空;3)鋼板到達時間段和離開時間段已知;4)為了減少倒垛量，堆場在某個時間段內作業順序為先出庫，后入庫;5)每個時間段出庫和入庫的鋼板批次都不會超過一個;6)每個時間段內入庫鋼板數量不會超過堆場容量;7)跨之間不能倒垛。

根據以上假設，針對入庫、出庫及倒垛作業，整個堆場可以表示為如圖2所示的獨立作業單元，堆場由S個堆垛構成，S=m×n，堆垛位置表示為(x，y)。

圖2 堆場模型Fig.2 Stockyard model

堆垛中的鋼板的層計數方式為從上到下，為了方便堆場管理描述，設置如下符號:T為計劃期長度;t為第t個時間段;、分別表示t時間段鋼板出庫后和入庫后堆垛(i，j)中的鋼板數量;為堆垛(i，j)的第k層鋼板;、分別表示t時間段內鋼板出庫后和入庫后的堆場{1，2，..，m，j=1，2，3，..，n，k=1，2，..，}，{|i=1，2，..，m，j=1，2，3，..，n，k=1，2，..，};vt為t時段入庫鋼板總數;為t時間段的序號為g的入庫鋼板;πt為t時間段入庫鋼板集合，πt={|，g=1，2，..，vt};Π 為計劃期內的入庫鋼板集合，Π={πt|t=1，2，..，T};num為每塊入庫的板唯一的標識;Zt為t時間段出庫鋼板的數量；為第t第z塊出庫鋼板，∈;ut為t時間段的出庫鋼板集合，ut={1，2，..，m，j=1，2，..，n，z=;1，2，..，Zt};Ω 為計劃期內出庫集合，Ω={ut|t=1，2，..，T}。

模型參數和變量如下:

H為每個垛位中可堆放的鋼板數量的上限;Q為一個無限大的值;ψ為異類板集合;At為第t時間段出庫需要倒垛的鋼板集合;δw為同一個堆垛中，兩塊相鄰鋼板之間的寬度差極限δl為同一個堆垛中，兩塊相鄰鋼板之間的長度差極限。

決策變量:

因此，目標函數為

除特殊說明，否則qijz∈ut∈ πt，i=1，2，..，m，j=1，2，..，n，i＇=1，2，..，m，j＇=1，2，..，n，t=1，2，..，T。式(6)～(9)中w∈e，w＇∈e＇，e∈，e＇∈。

其中，式(1)為目標函數，最小化計劃期內各個時間段內倒垛量的總和;約束(2)保證t時間段內一塊入庫鋼板只被分配到一個位置上;約束(3)保證t時間段內每個位置只放一塊鋼板;約束(4)保證t時間段內一次倒垛發生，鋼板只被放到一個新位置;約束(5)保證t時間段內鋼板不被懸空放置;約束(6)和(7)表示同一個堆中兩塊相鄰鋼板間的寬度差異限制;約束(8)和(9)表示同一個堆中的兩塊相鄰鋼板的長度差異限制。

2 兩階段優化求解方法

定義:異類板，指在堆場管理中引起倒垛的板，包括兩類:一種是受尺寸約束，入庫時需要倒垛的板;另一種是出庫時引發倒垛的板。

船廠鋼板堆場多時段作業計劃優化既是一個多階段優化決策問題，又是一個組合優化問題。根據多時段堆場性質，將問題劃分為兩個階段求解，首先針對多階段性，采用動態規劃啟發式算法得到初始解及異類板集合，然后從組合優化出發采用變鄰域搜索算法對初始解進行組合優化。

2.1 階段I－動態規劃啟發式算法

船廠鋼板堆場多時段作業計劃優化屬于多階段最優決策問題，即不論當前狀態是由以前何種決策所造成，余下的策略對當前的狀態，必定構成最優策略［7］。

多時段作業的每個時間段是一個相對獨立的單元，按時間段的先后順序將研究的問題劃分為T階段，第t階段對應第t時間段，x(t)對應第t時間段出庫結束時的狀態，u(t)(t=0，1，..，T－1)代表第t時間段的出庫、入庫和倒垛決策，則問題表示如下:

x(t+1)=Ht(x(t)，u(t))，Ht代表狀態轉移函數，令F為總目標函數，ft為第t階段的目標函數，遞歸函數如下:

為了減少運算時間，在決策階段引入啟發式規則，如動態規劃啟發式算法步驟2)所示。動態規劃的實施過程如圖3所示，根據動態規劃遞歸函數的終止條件，在T階段出庫結束后的空堆場基礎上，將T階段出庫的鋼板ut按啟發式規則分配垛位，狀態轉移得到，即第T－1階段鋼板入庫后的堆場，將第T－1階段入庫的鋼板πT－1移除，獲得，同理取得各階段堆場中的堆放狀態。

圖3 動態規劃啟發式算法示意圖Fig.3 Dynamic programming based heuristics

動態規劃啟發式算法步驟如下:

1)令t=T，轉2);

2)ut在的基礎上入庫，獲得:

①從ut隨機選出板，從ut中刪除，轉②;

②在的堆場狀態下，令i=1，j=1，k=1，(x，y，z)為插入的位置，ftemp為相應的倒垛量，Stemp表示目標位置與的長之差與寬之差之和，令x=0，y=0，z=0，ftemp=Q，Stemp=Q，轉③;

③如果zijt≥H，則轉⑨;如果，則轉⑤;如果與滿足約束(7)－(10)，則轉④，否則令k=k+1，重復③;

④如果存在，k＇=k，k+1，..，，的入庫日期與的入庫日期相同，則引起的倒垛量temp1=0;否則，令k＇=k－ 1，轉⑤;

⑤比較與的入庫日期，如果＇先入庫，則temp1=temp1+2;如果k＇≠ 1，則令k＇=k＇－1，重復⑤;如果k＇=1，則轉⑥;

⑥如果ftemp＞temp1，則轉⑧;如果ftemp=temp1，則轉⑦;如果ftemp＜temp1，則轉⑨;

⑦用temp2表示與的長之差和寬之差的和，如果Stemp＞temp2，則轉⑧，否則轉⑨;

⑧更新相應的入庫候選位置信息:

x=i，y=j，z=k，ftemp=temp1，Stemp=temp2，轉⑨;

⑨如果i＜m，令i=i+1，轉③;否則轉⑩;

⑩如果j＜n，令j=j+1，轉③;否則

3)利用 πt－1通過得到:刪除中所有第t－1階段入庫的鋼板，同時更新堆垛信息，獲得，如果t＞1，則t=t－1，轉2);否則結束循環。

2.2 階段Ⅱ－變鄰域搜索算法

目前，鄰域搜索算法已廣泛運用于集裝箱堆場和鋼廠堆場調度中，包括集裝箱出庫［8］、集裝箱出庫預處理［9］和鋼廠鋼板倒垛［10］。在船廠鋼板堆場多時段作業計劃優化中以異類板為中心構造鄰域，消除異類板的同時可能產生新的異類板，因此鄰域結構需要變換。Hansen等提出的變鄰域搜索算法在大規模組合優化問題有突出的表現［11］，適合船廠鋼板堆場，其優良性由兩個關鍵步驟決定:局部搜索和鄰域結構改變。通過局部搜索可以在一個鄰域內找到局部最優解，在局部最優解的基礎上改變鄰域結構以跳出局部最優達到全局最優。

Nk(k=1，..，+∞)表示鄰域結構集，Bk表示相應的局部最優解，Ek表示局部最優解產生的倒垛次數，ψ表示每一個領域結構對應的異類板的集合，νk表示第k塊異類板的鄰域，νk［j］表示第j個可行解，是一個垛位編號，如(x，y，z)，νk∈Nk，Gk記錄第k個局部最優解時，計劃期內每個時間段堆場的所有堆垛中z最大的異類板集合，α是結束搜索系數，指的是從第m個鄰域結構出發，如果在第(m+α)個鄰域結構時還找不到更優的解，則結束搜索，Eα為最優解。

變鄰域搜索算法步驟如下:

1)統計出庫入庫引起的倒垛量:

①t=1，轉②;

②遍歷Ot2-1中所有堆垛，統計每個堆垛出庫時間段為t的鋼板數量l，及所有出庫板所在層位置z的最大值zmax，temp=temp+2×(zmax－l)，如果zmax≠1，則Gk=Gk+numzmax;遍歷結束后轉③;

③遍歷Ot2中所有堆垛，統計入庫時間段為t的鋼板數量l，及所有入庫板所在層位置z的最大值zmax，temp=temp+2×(zmax－l)，如果zmax≠1，則Gk=Gk+numzmax，如果t≥T，則結束，否則t=t+1，轉②。

2)K鄰域的構造及搜索:

①k=1，執行 1)，Ek=temp，轉 ②;

②從Gk中隨機選擇一張板numk，且numk?ψ，構鍵νk:t為入庫時間遍歷找出所有(x，y，z)，且numk與rxyz，及rxy(z－1)與numk滿足約束(7)－(10)νk=νk+(x，y，z)，轉③;

③執行1)，在Bk的基礎上計算numk入庫位置為vk［i］時的temp，如果temp＜Ek，則Ek=temp，Bk更新為最新堆場垛位信息，遍歷vk，轉④;

④如果k＞α ，且Ek－α＜Ek－α+1，Ek－α+2，..，Ek，則結束搜索;否則令k=k+1，轉②;

3 實例驗證與數值分析

3.1 實例驗證

為了驗證所提方法的實用性和有效性，下面將兩階段方法與文獻［1］的仿真和文獻［4］的遺傳算法(GA)進行比較。

3.1.1 算例設置

算法是在Windows 7系統上基于Visual C#實現，選取某大型船廠的實際數據驗證，研究的計劃期T=4，堆場有12個堆垛，即S=12，每一樁位最高堆疊層數H=20，變鄰域搜索算法中的結束搜索系數α=5。GA的參數選取為:種群規模N=500，進化代數M=200，交叉概率=0.95，變異概率=0.05。

表1 實例數據Table 1 Actual data

根據參與調度的鋼板數量的不同設置了26組算例(如表1)，表中Dn代表第n天。得到3種途徑下的倒垛次數R1，R2，R3和運行時間，如表2所示，α12和α13表示兩階段方法比另外兩種方法的倒垛次數優化率，α12=(R2－R1)/R2，α13=(R3－R1)/R3，負值表示沒有起到優化作用。

3.1.2 實驗結論及結果分析

表2為實例驗證結果。圖4為3種方法倒垛量與鋼板數量關系圖。對結果進行分析，可知:1)如圖4，當GA參數固定時，在某個鋼板數量范圍內求得較優解。當參與調度的鋼板數量少于125張時，遺傳算法優于兩階段方法;當參與調度的鋼板數量較多，大于130張時，兩階段方法優于遺傳算法，倒垛次數減少6%至75%。2)仿真方法在小規模問題時優于兩階段法。當鋼板量大時，解的質量下降，此時使用兩階段方法倒垛量可以減少28%至75%。3)遺傳算法運行時間長，并且隨著鋼板數量增加，運行時間快速增長，當鋼板數量為300張時，運行時間已經達到 4 897.7s。

表2 算例結果Table 2 Output of numerical experiment

出現以上結果的原因是仿真方法依靠人工決策規則，對大量鋼板出入庫時難以適應;而遺傳算法容易陷入局部最優化。如果要兼顧全局性，需要針對不同的鋼板數量范圍，調整種群規模、遺傳代數、交叉概率及變異概率，從而增加算法使用復雜程度和運算時間。相比較，本文的兩階段方法在解決實際生產中的大規模鋼板出入庫調度問題時運行時間短，結果優異。

圖4 倒垛量與鋼板數量的關系圖Fig.4 Shuffling operation quantities vs steel plate quantities

3.2 數值試驗與討論

在一個計劃期內，鋼板堆場的倒垛量與兩階段方法的參數α值選取有密切關系。

以表1中第26組算例為對象，研究α值對結果的影響。如表3所示，其中t表示運行時間，k表示鄰域結構的數量，可以看出α增加，倒垛次數減少，運行時間變長，原因是由于α越大，VNS越容易逃逸出局部最優，搜索的范圍越廣，全局性越好，運行時間也增加。理論上，只要α足夠大，可以找到最優解。

以α=7為例分析最優解與α的關系，以鄰域結構編號為橫坐標，局部最優解為縱坐標，作鄰域結構變化圖，如圖5所示:1)總體上倒垛量不斷減少;2)在相鄰的幾個鄰域結構容易陷入局部最優化，比如第1，2…，6鄰域結構時，假如當α=1或2就無法逃逸出該局部最優陷阱，最優解等于鄰域結構N3的局部最優解，不能繼續搜尋到N18時的局部最優解。

表3 α與R、t、k的關系Table 3 The relationship between α and R ，t，k

圖5 局部最優解隨鄰域結構的變化情況Fig.5 The diagram of local optimum and neighborhood structure

4 結束語

不同鋼板在不同時間段入出庫是引起堆場倒垛的主要原因，本文綜合考慮一個計劃期內的鋼板出庫、入庫問題，建立了以減少倒垛量為目標的鋼板堆場多時間段堆場作業計劃優化模型，并把問題分解為兩個階段求解，使復雜問題簡單、易實現。兩階段方法由動態規劃啟發式算法和變鄰域搜索算法構成，最后運用實例，與遺傳算法和仿真結果作對比，證明了本文所提出的兩階段方法的實用性和有效性，同時通過數值實驗，研究了算法參數對結果的影響。

［1］蔣如宏，鐘宏才，譚家華.船廠鋼板堆場管理的數字化仿真［J］.上海交通大學學報，2003，37(7):1242-1245.JIANG Ruhong，ZHONG Hongcai，TAN Jiahua.Simulation of digitized plate stockyard management in shipyards［J］.Journal of Shanghai Jiaotong University，2003，37(7):1242-1245.

［2］PARK C，PARK J C，BYEON G G，et al.Steel stock management on the stockyard operations in shipbuilding:a case of Hyundai Heavy Industries［J］.Production Planning and Control:The Management of Operations，2006，17(1):1-12.

［3］金淳，王廣民，高鵬.造船廠鋼板出庫作業計劃的建模及優化研究［J］.工業工程與管理，2009，14(6):12-17.JIN Chun，WANG Guangmin，GAO Peng.Modeling and optimization on operation scheduling for a steel plate yard in a shipyard［J］.Industrial Engineering and Management，2009，14(6):12-17.

［4］劉曉峰，張小輝，蔣志勇，等.基于遺傳算法入庫鋼板分配策略［J］.江蘇科技大學學報:自然科學版，2011，25(6):524-529.LIU Xiaofeng，ZHANG Xiaohui，JIANG Zhiyong，et al.Allocation strategy of steel plate in store house based on genetic algorithm［J］.Journal of Jiangsu University of Science and Technology:Natural science Edition，2011，25(6):524-529.

［5］徐萍，葛世倫.造船廠鋼板入庫作業優化研究［J］.航海工程，2012，41(1):33-37.XU Ping，GE Shilun.Optimization on entering storage operations of steel plate in a shipyard［J］.Ship and Ocean Engineering，2012，41(1):33-37.

［6］ZHANG Zhiying，WANG Peng，WANG Weize.Optimization and operation scheduling for a steel plate yard based on greedy algorithm［J］.Journal of Networks，2013，8(7):1654-1659.

［7］李瑞，錢富才，李力，等.動態規劃問題研究［J］.系統工程理論與實踐，2007，8:56-64.LI Duan，QIAN Fucai，LI Li，et al.Research on dynamic programming［J］.Systems Engineering theory and Practice，2007，8:56-64.

［8］LEE Y，LEE Y.A heuristic for retrieving containers from a yard［J］.Computer and Operation Research，2010，37(6):1139-1147.

［9］LEE Y，CHAO Shiliang.A neighborhood search heuristic for pre-marshaling export containers［J］.European Journal of Operational Research，2009，196(2):468-475.

［10］王敏，李鐵克，王伯琳.多對多板坯倒垛問題的一種鄰域搜索算法［J］.計算機集成制造系統，2010，16(3):658-671.WANG Min，LI Tieke，WANG Bailin.Local search algorithm for the overlapped turned-out slab pile problem［J］.Computer Integrated Manufacturing Systems，2010，16(3):658-475.

［11］MLADENOVIC N，HANSEN P.Variable neighborhood search［J］.Computer and Operations Research，1997，24(11):1097-1100.