分段堆場的動態調度方法

孫曉軍++董飛+梁鳳婷+董貴穎

摘 要： 針對造船過程中分段堆場的堆放混亂和調度效率低下的問題，通過緊密結合調度規則，以使分段移動過程中產生的衍生指令數最小為目標，綜合考慮分段的時間和空間要求，兼顧相關場地堆放不合理分段的調整，提出目標分段移入場地的位置選擇和出入堆場路徑優化的方法，并設計了計算流程。在場地堆放率為83.6%的情況下經過多次實驗，得到的衍生指令的平均比例降低到37.89%，得到了良好的調度結果，證明該方法在分段調度問題上的有效性。

關鍵詞： 船體分段； 生產調度； 衍生指令； 動態調整； 路徑規劃

中圖分類號：U673 文獻標志碼：A 文章編號：1006-8228（2017）02-60-05

0 引言

在現代造船模式下，船體分段制造活動是整個造船過程的瓶頸，其生產周期長，生產過程中的資源約束多。在分段制造過程中，分段堆場往往出現密集堆放的情況，并且生產計劃時常變動。這難免會導致分段堆場的堵塞現象的發生，使得分段調度效率低下，造成制船廠額外的運輸成本。

目前對分段堆場的調度研究較多，張志英等針對矩形分段提出了一種基于改進粒子群算法的動態空間調度方法，利用改進粒子群算法對分段進行加工排序，在算法設計時采用遺傳算法與粒子群算法的部分結合，通過自適應慣性權重策略實現了算法的收斂性[1]。陶寧蓉等針對船體各種不規則分段，提出將空間資源作為關鍵資源的空間調度問題，以具有時間窗約束的空間調度三維模型為基礎，提出了結合禁忌搜索和基于極點的定位規則的優化算法[2]。鄭俊麗等針對船體分段制造提出具體的模型及解決方法，主要利用三維裝箱問題來解決，最后通過一個系統的實現具體的顯示了所寫算法的正確性及可行性[3]。謝甜就分段堆場堆放混亂、分段難查詢等問題，綜合分析各部門分段建造及船舶合攏的一般規律，提出了分段調度和場地規劃方案[4]。馬少輝等針對矩形分段基于遺傳算法安排加工順序、利用平均最大矩形啟發策略安排空間位置[5]。張志英等考慮船舶分段堆場調度過程中的擾動因素，結合分段的質量和移動距離建立數學模型，并用改進遺傳算法提出分段在堆場中堆放位置的較優方案[6]。

本文以分段移動過程中產生的衍生指令數最小為目標，考慮場地屬性和分段要求匹配，兼顧分段的剩余加工周期天數和所占場地的阻力系數進行動態調整，難點就在于動態調整的過程，最終提出船體分段調度的算法。這一算法使得調度問題的計算過程更加透明，通過計算可得到具體的調度指令，使調度有序的進行，可操作性更強。

1 問題分析

在現代造船模式下，在船體裝配之前，船體分段需要先后在多個堆場中進行堆放以及加工，如舾曬、噴砂、涂裝、打磨和小裝配等。每個堆場容量有限并且功能相對單一，而每個分段所要求進行的工藝階段是不同的，這就要求各個分段在幾個堆場之間進行不同而有序的單向流動。

場地按照空間位置即工藝不同劃分成為多個隔離的二級場地，而每一個小方格是容納分段的三級場地。每天，業務部門都會向物流部門提出若干分段移動的需求，由于目標分段存放在各二級場地上，而二級場地上沒有預留平板車行駛的空間，平板車移出目標分段就需要先挪開路徑上的其他分段，即衍生指令，使得分段調度問題復雜化，加大了調度工作量，這就導致了分段堆場的調度問題的出現。

2 調度指令的優化策略

為了方便問題的研究可以做出如下假設：

⑴ 每個三級場地只放一個分段；

⑵ 分段的重量對于搬運工作沒有影響；

⑶ 由于衍生指令而移動的分段在工作指令完成之后不需要搬運回原位置。

2.1 符號設置

為了簡化描述，采用下述符號表示：

i：某三級場地在對應的二級場地中的行序號；

j：某三級場地在對應的二級場地中的列序號；

：工藝n二級場地上的三級場地（i，j）的分段；

：工藝n二級場地上的三級場地（i，j）；

：工藝n二級場地上的三級場地（i，j）的堆放系數；

：位于工藝n級場地上的三級場地（i，j）的分段的阻力值；

：位于工藝n級場地上的三級場地（i，j）的分段在工藝m二級場地上的工藝周期天數。

2.2 船體分段調度規則

⑴ 移動申請清單排序

一個完整的移動申請清單包括以下幾個部分：移動申請ID、移動分段ID、移出區域（三級場地）、移入區域（二級場地）、工藝流向、動能需求、分段在該場地的工藝周期天數。

對于有移動需求的若干分段，按分段提取的優先級進行排序，加工工藝流向靠后的或者工藝周期短的靠前，相反則靠后。要求工藝流向靠后的分段首先被執行，因為其工藝更接近裝配環節，其移出后留下的空位可以為前序工藝的分段使用，從而減少衍生指令的產生。

⑵ 計算空閑場地

在分段的移動流程開始前，要先確定二級場地中空閑著的三級場地，它包括已經存在的空閑三級場地，以及分段將要移出的三級場地。

⑶ 計算場地阻力

場地阻力值指的是平板車經過某個三級場地所遇到的阻力，空場地的阻力值為0，有分段擺放的三級場地阻力值為某一具體值。

從整體優化的角度來看，在分段移動過程中應協調場地的堆放系數與分段工藝周期的關系，調整相關堆場里堆放不合理的情況。工藝周期天數較大的分段近期提取的可能性較小，應放置在堆放系數較大的三級場地以免阻擋其他分段的提取，而工藝周期天數較小的分段應放置在堆放系數較小的三級場地以便于進出。首先確定該二級場地的堆放系數數列，如圖1所示。其次按照分段在該場地的剩余工藝周期天數進行排序。最后將分段的剩余周期天數和堆放系數做對比，判斷分段堆放是否合理。若分段堆放合理，設置其阻力值為1；若某分段的剩余周期天數排序靠前（周期較長）而堆放系數很小，即堆放不合理，則將其阻力值設為a（a<1），a<1表示若產生衍生指令則優先移動堆放不合理的分段。

⑷ 獲取最短路徑

為使進出場過程中衍生指令最少，利用dijkstra方法比對每個三級場地的所有出場路徑。將每個二級場地構建成一個網絡，構建方法如下：以每個三級場地為頂點，相鄰的兩個三級場地之間用有向邊連接，權重為進入該場地的阻力值，構建場地有向圖。利用路徑計算方法，可以計算出每個三級場地至道路阻力值最小的路徑。

⑸ 移入指定三級場地

移入指定三級場地實際上包括兩個步驟：選定目標三級場地和決定最優的進入路徑。在選定目標三級場地時要注意所選三級場地應符合各項約束條件，包括硬性約束和軟性約束。硬性約束包括滿足動能源、工藝流向、大分段擺放，軟性約束包括場地優先級、場地堆放系數等。硬性約束必須滿足，軟性約束包括滿足場地堆放系數與分段工藝周期的匹配等。

獲取分段的入場路徑與出場路徑相似，不同點在于入場時要計算的是各空閑三級場地的最短路徑值。

⑹ 平板運輸指令運算以及分發

平板運輸指令運算，要按照先后順序進行待移入場地盤整、待移出場地盤整、計劃指令。并規定，衍生指令產生的分段優先放置于空閑位置，如果沒有空閑位置則放回原位；前后有重復的衍生指令需要合并，優化指令體系，避免各條指令中的沖突問題。

2.3 船體分段調度流程圖

根據分段堆場的調度規則做出實際分段堆場的調度流程圖，如圖2所示。

[開始][輸入分段移動申請][更新移動申請清單][根據工藝流向/周期進行移動清單排序][找到移出場地的

不匹配分段][計算分段的移出路徑][排除該路徑][最優路徑？] [更新移出堆場的堆放情況] [否][是][結束][生成平板車運輸

指令并下達][處理完所有申請？] [更新平板車運輸指令清單][更新移入堆場堆放情況][最優位置的最優路徑？] [排除該路徑][計算分段的移入路徑][最優位置？] [排除該位置][選擇分段的移入位置][計算移入場地的阻力值][找到移入場地的

最短移入路徑：

衍生指令：

⑹ 更新移動指令清單，當前只需移動分段001，需重新計算阻力值。如圖8所示，在分段012的移動過程中將原分段移到了三級堆場上，實現了三級場地的相對優化。

3.2 仿真實驗驗證

最后我們利用仿真程序，通過對10個不同場地擺放的模擬，在堆場堆放率達到83.6%的情況下進行了20次試調度，對其結果進行分析可以得到衍生指令占總指令比例的平均值為37.89%，低于40%。從這一仿真結果來看，本文給出的調度策略，可以在堆場堆存率達到80%的情況下，將衍生指令降低到占總指令的40%以下，達到了整體優化的目標，有效減了因衍生指令而產生的運力、時間等成本。

4 結論

本文提出的分段調度方法能有效改善造船廠分段堆場堆放不合理的情況，通過綜合考慮分段的工藝流向、工藝周期，結合移出堆場和移入堆場的阻力系數分布，兼顧不合理分段的調整。降低了調度任務中移動次數，提高了堆場的物流效率，更加有利于造船廠對分段堆場進行管理。但在現實生活中，一個三級場地可以不止堆放一個分段，未來可對一個三級場地堆放若干分段的復雜問題進行進一步的研究。

參考文獻（Reference）：

[1] 張志英.改進粒子群算法的動態空間調度方法[J].哈爾濱工

程大學學報，2009.30（12）：1344-1350

[2] 陶寧蓉.帶時間窗約束的船體分段空間調度問題[J].計算機

集成制造系統，2010.16（12）：2674-2679

[3] 鄭俊麗.船舶分段制造車間的模塊空間調度模型及算法[D].

上海交通大學碩士學位論文，2011.

[4] 謝甜.分段調度優化與堆場規劃研究[J].上海船舶運輸科學

研究所學報，2012.35（21）：81-84

[5] 馬少輝.動態空間調度的混合遺傳算法[J].運籌與管理，

2013.22（2）：99-104

[6] 張志英，計峰，曾建智.基于改進GA的分段堆場計劃調度方

法研究[J].哈爾濱工程大學學報，2015.36（8）：1103-1108

[7] 陶寧蓉.船舶分段建造過程中的資源調度優化研究[D].上海

交通大學碩士學位論文，2013.

[8] 王玲玲.面向船體分段制造平臺資源調度方法設計及應用研

究[D].哈爾濱工業大學碩士學位論文，2013.