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

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

關(guān)鍵詞： 船體分段； 生產(chǎn)調(diào)度； 衍生指令； 動態(tài)調(diào)整； 路徑規(guī)劃

中圖分類號：U673 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2017）02-60-05

0 引言

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

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

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

1 問題分析

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

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

2 調(diào)度指令的優(yōu)化策略

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

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

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

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

2.1 符號設(shè)置

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

i：某三級場地在對應(yīng)的二級場地中的行序號；

j：某三級場地在對應(yīng)的二級場地中的列序號；

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

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

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

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

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

2.2 船體分段調(diào)度規(guī)則

⑴ 移動申請清單排序

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

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

⑵ 計算空閑場地

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

⑶ 計算場地阻力

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

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

⑷ 獲取最短路徑

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

⑸ 移入指定三級場地

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

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

⑹ 平板運輸指令運算以及分發(fā)

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

2.3 船體分段調(diào)度流程圖

根據(jù)分段堆場的調(diào)度規(guī)則做出實際分段堆場的調(diào)度流程圖，如圖2所示。

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

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

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

最短移入路徑：

衍生指令：

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

3.2 仿真實驗驗證

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

4 結(jié)論

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

參考文獻(xiàn)（Reference）：

[1] 張志英.改進(jìn)粒子群算法的動態(tài)空間調(diào)度方法[J].哈爾濱工

程大學(xué)學(xué)報，2009.30（12）：1344-1350

[2] 陶寧蓉.帶時間窗約束的船體分段空間調(diào)度問題[J].計算機(jī)

集成制造系統(tǒng)，2010.16（12）：2674-2679

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

上海交通大學(xué)碩士學(xué)位論文，2011.

[4] 謝甜.分段調(diào)度優(yōu)化與堆場規(guī)劃研究[J].上海船舶運輸科學(xué)

研究所學(xué)報，2012.35（21）：81-84

[5] 馬少輝.動態(tài)空間調(diào)度的混合遺傳算法[J].運籌與管理，

2013.22（2）：99-104

[6] 張志英，計峰，曾建智.基于改進(jìn)GA的分段堆場計劃調(diào)度方

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

[7] 陶寧蓉.船舶分段建造過程中的資源調(diào)度優(yōu)化研究[D].上海

交通大學(xué)碩士學(xué)位論文，2013.

[8] 王玲玲.面向船體分段制造平臺資源調(diào)度方法設(shè)計及應(yīng)用研

究[D].哈爾濱工業(yè)大學(xué)碩士學(xué)位論文，2013.