分段堆場的動態(tài)調(diào)度方法

2017-03-06 20:49:05孫曉軍董飛梁鳳婷董貴穎

計(jì)算機(jī)時(shí)代 2017年2期

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

摘要：針對造船過程中分段堆場的堆放混亂和調(diào)度效率低下的問題，通過緊密結(jié)合調(diào)度規(guī)則，以使分段移動過程中產(chǎn)生的衍生指令數(shù)最小為目標(biāo)，綜合考慮分段的時(shí)間和空間要求，兼顧相關(guān)場地堆放不合理分段的調(diào)整，提出目標(biāo)分段移入場地的位置選擇和出入堆場路徑優(yōu)化的方法，并設(shè)計(jì)了計(jì)算流程。在場地堆放率為83.6%的情況下經(jīng)過多次實(shí)驗(yàn)，得到的衍生指令的平均比例降低到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)代造船模式下，船體分段制造活動是整個(gè)造船過程的瓶頸，其生產(chǎn)周期長，生產(chǎn)過程中的資源約束多。在分段制造過程中，分段堆場往往出現(xiàn)密集堆放的情況，并且生產(chǎn)計(jì)劃時(shí)常變動。這難免會導(dǎo)致分段堆場的堵塞現(xiàn)象的發(fā)生，使得分段調(diào)度效率低下，造成制船廠額外的運(yùn)輸成本。

目前對分段堆場的調(diào)度研究較多，張志英等針對矩形分段提出了一種基于改進(jìn)粒子群算法的動態(tài)空間調(diào)度方法，利用改進(jìn)粒子群算法對分段進(jìn)行加工排序，在算法設(shè)計(jì)時(shí)采用遺傳算法與粒子群算法的部分結(jié)合，通過自適應(yīng)慣性權(quán)重策略實(shí)現(xiàn)了算法的收斂性[1]。陶寧蓉等針對船體各種不規(guī)則分段，提出將空間資源作為關(guān)鍵資源的空間調(diào)度問題，以具有時(shí)間窗約束的空間調(diào)度三維模型為基礎(chǔ)，提出了結(jié)合禁忌搜索和基于極點(diǎn)的定位規(guī)則的優(yōu)化算法[2]。鄭俊麗等針對船體分段制造提出具體的模型及解決方法，主要利用三維裝箱問題來解決，最后通過一個(gè)系統(tǒng)的實(shí)現(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)整，難點(diǎn)就在于動態(tài)調(diào)整的過程，最終提出船體分段調(diào)度的算法。這一算法使得調(diào)度問題的計(jì)算過程更加透明，通過計(jì)算可得到具體的調(diào)度指令，使調(diào)度有序的進(jìn)行，可操作性更強(qiáng)。

1 問題分析

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

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

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

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

⑴ 每個(gè)三級場地只放一個(gè)分段；

⑵ 分段的重量對于搬運(yùn)工作沒有影響；

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

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ī)則

⑴ 移動申請清單排序

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

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

⑵ 計(jì)算空閑場地

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

⑶ 計(jì)算場地阻力

場地阻力值指的是平板車經(jīng)過某個(gè)三級場地所遇到的阻力，空場地的阻力值為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è)三級場地的所有出場路徑。將每個(gè)二級場地構(gòu)建成一個(gè)網(wǎng)絡(luò)，構(gòu)建方法如下：以每個(gè)三級場地為頂點(diǎn)，相鄰的兩個(gè)三級場地之間用有向邊連接，權(quán)重為進(jìn)入該場地的阻力值，構(gòu)建場地有向圖。利用路徑計(jì)算方法，可以計(jì)算出每個(gè)三級場地至道路阻力值最小的路徑。

⑸ 移入指定三級場地

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

獲取分段的入場路徑與出場路徑相似，不同點(diǎn)在于入場時(shí)要計(jì)算的是各空閑三級場地的最短路徑值。

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

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

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

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

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

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

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

最短移入路徑：

衍生指令：

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

3.2 仿真實(shí)驗(yàn)驗(yàn)證

最后我們利用仿真程序，通過對10個(gè)不同場地?cái)[放的模擬，在堆場堆放率達(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)生的運(yùn)力、時(shí)間等成本。

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

2013.22（2）：99-104

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