考慮工藝順序和組合分段的多堆場(chǎng)調(diào)度方法

孟令通，蔣祖華，陶寧蓉，劉建峰，鄭 虹

(1. 上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院， 上海 200240； 2. 上海海洋大學(xué) 工程學(xué)院， 上海 201306；3. 上海外高橋造船有限公司， 上海 200137)

符號(hào)說(shuō)明:

di,j—分段i允許進(jìn)出堆位j的方向

Ey—堆場(chǎng)y與道路可直接通行的堆位集合

jy—堆場(chǎng)y中的堆位j

在現(xiàn)代造船模式中，分段作為基本生產(chǎn)單元在完成脫胎后，需經(jīng)過(guò)預(yù)舾裝、舾裝、涂裝、總組等工藝流程，最后完成船體搭載.堆場(chǎng)作為分段任務(wù)的緩沖地，具有承擔(dān)了部分后期加工任務(wù)的作用，在堆場(chǎng)中可以完成預(yù)舾裝、涂裝等工序.堆場(chǎng)中分段的調(diào)度由平板車完成，為了確保調(diào)度作業(yè)的準(zhǔn)時(shí)性，減少調(diào)度成本，提高堆場(chǎng)作業(yè)效率，優(yōu)化堆場(chǎng)調(diào)度策略至關(guān)重要.目前，許多傳統(tǒng)的調(diào)度方式僅適用于單堆場(chǎng)的調(diào)度情況，而單堆場(chǎng)調(diào)度屬于多堆場(chǎng)調(diào)度的特例，主要應(yīng)用于堆場(chǎng)和車間之間的分段流轉(zhuǎn).傳統(tǒng)調(diào)度方法雖然可以提高單堆場(chǎng)調(diào)度的效率、增加分段調(diào)度的合理性，但忽略了分段的工藝流向，并不適用于多堆場(chǎng)調(diào)度.然而，船廠內(nèi)堆場(chǎng)數(shù)量眾多，分段是在多個(gè)堆場(chǎng)和車間之間流轉(zhuǎn)的，因此，設(shè)計(jì)合理的船舶分段多堆場(chǎng)調(diào)度方法是提高船廠內(nèi)堆場(chǎng)整體調(diào)度效率的關(guān)鍵.

多堆場(chǎng)調(diào)度并不是單堆場(chǎng)調(diào)度的簡(jiǎn)單疊加，雖然其調(diào)度過(guò)程也是通過(guò)規(guī)劃分段調(diào)度的位置以及路線，進(jìn)而確定分段任務(wù)的執(zhí)行順序，但仍有諸多不同之處.

對(duì)于四面通行的單堆場(chǎng)調(diào)度，平板車的運(yùn)輸路徑多為直線.文獻(xiàn)[1]以減少無(wú)效移動(dòng)為目標(biāo)，規(guī)劃堆場(chǎng)布局和內(nèi)部通道，用阻擋分段率驗(yàn)證分段調(diào)度在船舶生產(chǎn)中的重要意義.文獻(xiàn)[2]在文獻(xiàn)[1]的基礎(chǔ)上重新定義了堆場(chǎng)分段位置的分配問(wèn)題，以進(jìn)出堆場(chǎng)阻擋分段為優(yōu)化目標(biāo)，設(shè)計(jì)遺傳算法優(yōu)化分段 堆位，提高了堆場(chǎng)調(diào)度效率.文獻(xiàn)[3]在遺傳算法優(yōu)化分段堆位的基礎(chǔ)上，設(shè)計(jì)進(jìn)場(chǎng)分段和阻擋分段的啟發(fā)式移動(dòng)策略用于求解四面通行堆場(chǎng)的堆位分配問(wèn)題.文獻(xiàn)[4]以阻擋分段數(shù)量為優(yōu)化目標(biāo)，設(shè)計(jì)進(jìn)場(chǎng)分段的堆位選擇策略和阻擋分段的移動(dòng)策略，得出分段任務(wù)的執(zhí)行順序?qū)φ{(diào)度結(jié)果有著重要影響的結(jié)論.

在實(shí)際應(yīng)用中，直線運(yùn)輸路徑一般用于場(chǎng)地資源不緊張的情況.當(dāng)場(chǎng)地資源有限時(shí)，平板車的運(yùn)輸路徑主要為折線.節(jié)點(diǎn)狀態(tài)模型是適用于折線運(yùn)輸?shù)恼{(diào)度模型且其分段形狀均為矩形.文獻(xiàn)[5]設(shè)計(jì)了啟發(fā)式規(guī)則以確定分段移動(dòng)路線，并通過(guò)遺傳算法優(yōu)化分段在堆場(chǎng)中的堆位.文獻(xiàn)[6]結(jié)合了分段質(zhì)量和移動(dòng)距離，用雙層遺傳算法確定分段的調(diào)度順序及其在堆場(chǎng)中的停放位置，并設(shè)計(jì)了啟發(fā)式算法規(guī)劃分段最優(yōu)移動(dòng)路線.文獻(xiàn)[7]在文獻(xiàn)[4]的基礎(chǔ)上，以分段移動(dòng)度為優(yōu)化目標(biāo)，針對(duì)單面通行堆場(chǎng)設(shè)計(jì)了5種阻擋分段的移動(dòng)策略，并用多鏈DNA遺傳算法對(duì)分段任務(wù)的執(zhí)行順序進(jìn)行求解.文獻(xiàn)[8]以分段移動(dòng)度為優(yōu)化目標(biāo)，考慮分段工藝階段和多堆場(chǎng)堆位優(yōu)先級(jí)，針對(duì)多個(gè)堆場(chǎng)的分段調(diào)度問(wèn)題，設(shè)計(jì)了阻擋分段啟發(fā)式調(diào)度規(guī)則.文獻(xiàn)[9]提出將分段進(jìn)行組合堆置，但僅研究了組合分段在單堆場(chǎng)中的調(diào)度問(wèn)題，并沒有涉及多堆場(chǎng)調(diào)度.

針對(duì)多規(guī)格分段布局的研究大多不劃分堆位且調(diào)度場(chǎng)景主要集中在分段建造車間內(nèi).文獻(xiàn)[10]深入分析了分段屬性以及加工平臺(tái)、加工空間、加工流程等各類約束，設(shè)計(jì)了一種貪婪的啟發(fā)式搜索算法，并與網(wǎng)格搜索算法和遺傳算法進(jìn)行了對(duì)比.文獻(xiàn)[11]考慮了不同規(guī)格和擺放方向的分段，將問(wèn)題表述為一個(gè)混合整數(shù)規(guī)劃(MIP)模型，設(shè)計(jì)了調(diào)度優(yōu)先級(jí)規(guī)則和對(duì)角填充空域分配方法.文獻(xiàn)[12]同時(shí)考慮了分段布局和模糊建造時(shí)間，提出用模糊三角時(shí)間模型表示不確定的分段開工和完工時(shí)間，并設(shè)計(jì)了遺傳算法優(yōu)化分段加工位置.

以上研究都是只針對(duì)單一規(guī)格分段、堆位固定且只能容納一個(gè)分段的堆場(chǎng)調(diào)度問(wèn)題，可處理的分段數(shù)量和種類較少，簡(jiǎn)化了分段在各個(gè)堆場(chǎng)流轉(zhuǎn)過(guò)程中任務(wù)的連續(xù)性，忽略了分段的工藝順序.針對(duì)上述問(wèn)題，本文在文獻(xiàn)[13]的基礎(chǔ)上提出了組合分段多堆場(chǎng)調(diào)度模型，考慮堆位內(nèi)組合分段之間的干涉，設(shè)計(jì)了多堆場(chǎng)分段堆位選擇策略和阻擋分段跨堆場(chǎng)移動(dòng)策略，以確定分段的目標(biāo)堆位；改進(jìn)了傳統(tǒng)的任務(wù)順序調(diào)整策略，并用禁忌搜索算法進(jìn)行優(yōu)化；最后，討論了不同調(diào)度策略對(duì)運(yùn)輸成本的影響，并通過(guò)實(shí)例求解得到多堆場(chǎng)內(nèi)任務(wù)和阻擋分段的多堆場(chǎng)調(diào)度方案.

1 問(wèn)題模型

1.1 問(wèn)題描述

分段多堆場(chǎng)調(diào)度示意圖如圖1所示，多堆場(chǎng)調(diào)度與單堆場(chǎng)調(diào)度的差異如表1所示.

圖1 分段多堆場(chǎng)調(diào)度示意圖Fig.1 Sketch of block transportation in multi-stockyard scheduling

表1 多堆場(chǎng)調(diào)度與單堆場(chǎng)調(diào)度的差異Tab.1 Difference between multi-stockyard scheduling and stockyard scheduling

多堆場(chǎng)調(diào)度遵循以下假設(shè)：

(1) 堆場(chǎng)均為組合分段堆場(chǎng)，一個(gè)堆位可以堆置1個(gè)大型分段，或2個(gè)小型分段；

(2) 各堆場(chǎng)規(guī)格不同，但堆位序號(hào)的編碼方式相同，從堆場(chǎng)左上角開始依次由左至右、由上至下編號(hào)；

(3) 所有分段投影的外包絡(luò)線均簡(jiǎn)化為直角梯形，組合分段在一個(gè)堆位內(nèi)按照堆位編碼方式左右水平堆置；

(4) 堆場(chǎng)之間由道路連接，不考慮道路寬度對(duì)平板車運(yùn)輸?shù)挠绊懀?/p>

(5) 堆場(chǎng)外運(yùn)輸先將分段運(yùn)輸至堆場(chǎng)邊緣，再進(jìn)行堆場(chǎng)內(nèi)運(yùn)輸，且堆場(chǎng)外運(yùn)輸時(shí)將堆場(chǎng)視為節(jié)點(diǎn)；

(6) 堆場(chǎng)可進(jìn)行部分后期加工，如完成預(yù)舾裝、涂裝等工序；

(7) 阻擋分段不能再次產(chǎn)生阻擋，待完成后期加工后可以跨堆場(chǎng)調(diào)度；

(8) 任務(wù)分段和阻擋分段根據(jù)下一個(gè)工序選擇堆場(chǎng).

1.2 數(shù)學(xué)模型

多堆場(chǎng)調(diào)度主要從兩個(gè)角度對(duì)調(diào)度進(jìn)行優(yōu)化：① 減少調(diào)度過(guò)程中產(chǎn)生阻擋分段的數(shù)量，降低分段重復(fù)搬運(yùn)造成的資源浪費(fèi)；② 優(yōu)化分段移動(dòng)路線，降低平板車油耗.目標(biāo)函數(shù)將綜合這兩個(gè)方面進(jìn)行考慮.

決策變量：

目標(biāo)函數(shù)：

(1) 任務(wù)分段移動(dòng)時(shí)產(chǎn)生的阻擋分段總數(shù)

(1)

(2) 任務(wù)分段和阻擋分段在堆場(chǎng)內(nèi)的運(yùn)輸距離

(2)

(3) 任務(wù)分段及阻擋分段跨堆場(chǎng)間的運(yùn)輸距離

(3)

優(yōu)化目標(biāo)函數(shù)表示為

F=

(4)

式中：wm表示移動(dòng)阻擋分段的權(quán)重；wl表示平板車負(fù)載運(yùn)輸?shù)臋?quán)重.

s.t.

(1) 分段運(yùn)輸在調(diào)度周期內(nèi)執(zhí)行，

(5)

(2) 堆場(chǎng)中同一個(gè)堆位上至多可以堆置2個(gè)小型分段.

(6)

(3) 任務(wù)分段所在堆場(chǎng)符合分段所處的工藝階段，分段的下一個(gè)工藝階段是在合適的堆場(chǎng)進(jìn)行,

(7)

(8)

(5) 分段只能通過(guò)堆場(chǎng)與周圍道路可直接通行的堆位進(jìn)出堆場(chǎng)，其余的堆場(chǎng)方向視為圍墻禁止通行.若一個(gè)6×10堆場(chǎng)只能單面通行且堆場(chǎng)內(nèi)的分段只能從堆場(chǎng)上方運(yùn)輸出去，可通行堆位集合Ey={0,1,…,9}，對(duì)于進(jìn)出堆場(chǎng)路線的邊緣堆位有

(9)

(6) 在執(zhí)行任務(wù)的過(guò)程中，進(jìn)入目標(biāo)堆場(chǎng)時(shí)，不能超過(guò)堆場(chǎng)容量，因此需要在目標(biāo)堆場(chǎng)中找出能滿足大型分段或組合分段的堆位，

(10)

對(duì)目標(biāo)函數(shù)求解之前，首先要獲取各堆場(chǎng)已知的初始狀態(tài)，包括堆場(chǎng)規(guī)格、分段布局和堆場(chǎng)四周的通行情況，分段只能經(jīng)過(guò)堆場(chǎng)與道路可直接通行的堆位(即矩形堆場(chǎng)的某些邊)進(jìn)出堆場(chǎng).若分段按照策略無(wú)候選堆位或堆場(chǎng)已經(jīng)堆滿分段時(shí)，則將分段運(yùn)輸?shù)?號(hào)堆場(chǎng)，并在目標(biāo)函數(shù)中加入懲罰值Z.

2 模型求解

2.1 組合分段干涉方向判斷

利用啟發(fā)式規(guī)則判斷組合分段在一個(gè)堆位內(nèi)的干涉方向：在可行的空域內(nèi)，分段的最終參考點(diǎn)位置要盡可能靠近可行域最左下角的頂點(diǎn)，也就是文獻(xiàn)[13]中的最左最下規(guī)則.如圖2所示，b1為堆位中已經(jīng)堆置好的分段，需要將分段b1的頂點(diǎn)G1靠近堆位最左下角的頂點(diǎn)；b2是將要與b1組合堆置的分段，頂點(diǎn)G2需要盡量靠近分段b1.因此，分段b1的可移動(dòng)方向?yàn)樯?、左、下，即移?dòng)方向db1,j=j-N,j+N,j-1；當(dāng)db1,j=j+1時(shí)，阻擋分段數(shù)量會(huì)增加.

圖2 可行空域分段堆位最左最下規(guī)則Fig.2 The left-bottom rule of feasible space in cell

使用空域的方法，對(duì)組合分段通過(guò)包絡(luò)轉(zhuǎn)角進(jìn)行16種判斷，判斷過(guò)程如圖3所示.分段b1通過(guò)4次90° 的順時(shí)針旋轉(zhuǎn)調(diào)整其在堆位j中的堆置方向(圖3(a))，每種b1的堆置方向?qū)?yīng)4種組合分段b2的堆置方向(圖3(b)).如圖3(b)所示，可以組合堆置的方式有0°、180° 兩種，因此，在分段組合堆置后，當(dāng)移動(dòng)b1時(shí)，對(duì)應(yīng)的干涉方向分別為右方(0°)、右方和上方(180°)；當(dāng)移動(dòng)b2時(shí)，對(duì)應(yīng)的干涉方向?yàn)樽蠓健⒆蠓胶拖路?當(dāng)有多種方式可以堆置分段時(shí)，需要選擇干涉方向較少的組合方式堆置分段.

實(shí)際上，在組合堆位的分段進(jìn)入堆場(chǎng)的過(guò)程中，目標(biāo)堆位上已有分段的堆置方式已經(jīng)確定，需要根據(jù)不同的組合方式調(diào)整進(jìn)場(chǎng)分段的堆置方向.整個(gè)調(diào)整過(guò)程依靠平板車的液壓驅(qū)動(dòng)、液壓懸掛、獨(dú)立轉(zhuǎn)向、車架自動(dòng)調(diào)平等技術(shù)完成.需要注意的是本文忽略了因再次調(diào)整組合分段位置產(chǎn)生的調(diào)度成本.

圖3 堆位空間分段組合可行性性判斷Fig.3 Feasibility judgment of block combination in cell

2.2 任務(wù)執(zhí)行順序調(diào)整策略

表2 調(diào)度周期第t天的任務(wù)分段時(shí)間余量Tab.2 Time information of block transportation tasks on Day t of scheduling

分段在移動(dòng)過(guò)程中應(yīng)盡量減少阻擋分段的產(chǎn)生，因此若任務(wù)分段的阻擋分段中包含后續(xù)分段，則要將后續(xù)分段的運(yùn)輸提前.如圖4所示，165,175表示計(jì)劃第5天出場(chǎng)的組合堆置的分段16和17，在實(shí)線標(biāo)出的路徑上，3號(hào)分段是17號(hào)分段的阻擋分段，因此可以將3號(hào)分段提前運(yùn)輸.具體步驟如下：

圖4 堆場(chǎng)內(nèi)的分段任務(wù)執(zhí)行順序Fig.4 Sequence of block transportation tasks in stockyard

步驟1先執(zhí)行出場(chǎng)分段任務(wù)，將任務(wù)組內(nèi)的出場(chǎng)分段按照移動(dòng)成本進(jìn)行排序.若成本相同，則按照時(shí)間余量進(jìn)行排序.

步驟2判斷后續(xù)分段任務(wù)中是否存在任務(wù)分段的阻擋分段.若有，則將阻擋分段提前至任務(wù)分段前執(zhí)行.

步驟3判斷后續(xù)分段任務(wù)中是否有任務(wù)分段的組合分段.若有，則將組合分段提前至任務(wù)分段之后執(zhí)行.

步驟4判斷后續(xù)分段任務(wù)中是否有到當(dāng)前分段的無(wú)阻擋路徑.若有，則將分段提前至任務(wù)分段之后執(zhí)行；否則，返回步驟1繼續(xù)執(zhí)行任務(wù)序列中的任務(wù)，直至所有任務(wù)執(zhí)行完畢，得到最終的任務(wù)出場(chǎng)執(zhí)行順序.

2.3 多堆場(chǎng)分段堆位選擇策略

步驟2選擇p′

步驟3判斷A是否為空集.若A=?，則將堆位加入A1，進(jìn)而判斷堆位中分段是否可以與任務(wù)分段組合堆置；否則返回步驟2，直至A中分段遍歷完畢.若可以組合堆置，則將堆位加入A2.

步驟4得到集合A1和A2.

步驟5若A1和A2都為空集，則說(shuō)明該堆場(chǎng)已經(jīng)達(dá)到堆場(chǎng)容量上限.

候選堆位是允許堆置進(jìn)場(chǎng)分段的堆位，具體堆位的選擇有如下兩種策略.

策略1若任務(wù)分段是組合分段，則選擇候選集合A2中出場(chǎng)時(shí)間相同的分段進(jìn)行組合堆置；若分段是大型分段，或者無(wú)出場(chǎng)時(shí)間相同的組合分段，則計(jì)算每個(gè)空堆位與周圍分段的平均出場(chǎng)間隔時(shí)間

其中：R表示候選堆位四周的分段數(shù)量；τht,τr分別表示任務(wù)分段和四周各個(gè)分段的預(yù)計(jì)出場(chǎng)時(shí)間.選擇與周圍分段平均出場(chǎng)間隔時(shí)間最小的位置作為進(jìn)場(chǎng)堆位.

策略2綜合考慮進(jìn)場(chǎng)分段對(duì)在場(chǎng)分段及空堆位的影響，選擇合適的堆位堆置進(jìn)場(chǎng)分段.堆位候選集合中每個(gè)可行堆位在放置任務(wù)分段后，需計(jì)算當(dāng)前階段預(yù)計(jì)產(chǎn)生的調(diào)度成本，并選擇對(duì)后續(xù)分段移動(dòng)影響最小的堆位，具體步驟如下：

步驟1獲取任務(wù)分段i的堆位候選集合A1和A2.

步驟3對(duì)堆場(chǎng)中的其余分段，將與之相比出場(chǎng)時(shí)間較早的分段不計(jì)，計(jì)算預(yù)計(jì)產(chǎn)生的出場(chǎng)移動(dòng)成本α1=∑j′∈A1∪A2(wmnj′+λwldj′).

步驟4對(duì)堆場(chǎng)中每個(gè)可推置堆位j″∈A1∪A2，同理計(jì)算有分段進(jìn)入該堆位時(shí)的預(yù)計(jì)移動(dòng)成本α2=∑j″∈A1∪A2(wmnj″+λwldj″)，得到分段i堆置于堆位j對(duì)整個(gè)堆場(chǎng)的影響指標(biāo)Vj′=α+α1+α2.

步驟5返回步驟2，直至候選集合中堆位遍歷完畢.

步驟6選擇Vj′值最小的堆位作為分段i的進(jìn)場(chǎng)堆位j.

2.4 阻擋分段跨堆場(chǎng)移動(dòng)策略

在多堆場(chǎng)調(diào)度阻擋分段的堆位選擇過(guò)程中，阻擋分段可以在原有堆場(chǎng)中進(jìn)行調(diào)度，也可以在完成當(dāng)前堆場(chǎng)的部分加工后直接運(yùn)輸?shù)狡渌褕?chǎng).若需要移動(dòng)到其他堆場(chǎng)，則要首先確定阻擋分段接下來(lái)要被運(yùn)輸?shù)哪繕?biāo)堆場(chǎng).目標(biāo)堆場(chǎng)可以是符合阻擋分段下一階段工藝屬性的堆場(chǎng)或僅僅是臨時(shí)堆場(chǎng)，但不能返回阻擋分段當(dāng)前工藝階段之前的堆場(chǎng)，否則將影響其他堆場(chǎng)內(nèi)部的周轉(zhuǎn)，進(jìn)而增大運(yùn)輸成本.為了降低運(yùn)輸?shù)那短仔裕钃醴侄卧谖恢弥匦路峙涞倪^(guò)程中不允許再次產(chǎn)生阻擋分段，只可以選取平板車能夠直接到達(dá)的堆場(chǎng)堆位.

策略3將阻擋分段就近堆置在原堆場(chǎng)，剔除原堆場(chǎng)中的任務(wù)分段路徑，選擇通行無(wú)阻擋的堆位；區(qū)分大型分段和組合分段，挑選與周圍分段出場(chǎng)時(shí)間較為接近的堆位進(jìn)行堆置.

策略4拓寬阻擋分段的堆位選擇范圍.根據(jù)工藝階段，確定阻擋分段的堆場(chǎng)，根據(jù)阻擋分段對(duì)堆場(chǎng)空堆位及在場(chǎng)分段的影響指標(biāo)確定阻擋分段重新分配的堆場(chǎng)及堆位，其具體流程如圖5所示.其中：y′為任務(wù)i的當(dāng)前堆場(chǎng)；A′為阻擋分段移動(dòng)的堆位集合.

圖5 阻擋分段移動(dòng)策略2的流程圖Fig.5 Flowchart of moving strategy 2 with obstructive blocks

2.5 禁忌搜索

2.5.1禁忌搜索結(jié)構(gòu) 通過(guò)鄰域搜索優(yōu)化任務(wù)的執(zhí)行順序.設(shè):π為初始解；TL為一個(gè)空的禁忌搜索集合；Iter和NIter分別表示總迭代次數(shù)和結(jié)果沒有提升的次數(shù).當(dāng)Iter≥MaxIter或者NIter≥NonImpIter 時(shí)，則終止循環(huán).計(jì)算步驟見文獻(xiàn)[9].

圖6 鄰域搜索示意圖Fig.6 Illustration of neighborhood search

禁忌搜索表是在搜索過(guò)程中為了防止重復(fù)循環(huán)記錄鄰域變換的集合，每個(gè)任務(wù)用(t,m,x1,x2)表示.其中：m表示領(lǐng)域搜索的模式，m=0表示交換模式，m=1表示插入模式；x1,x2表示任務(wù)取出后，交換或插入的位置.

3 算例分析

3.1 調(diào)度結(jié)果分析

為了驗(yàn)證模型以及算法的可行性，本文設(shè)計(jì)了多組實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證.為了提高數(shù)據(jù)的實(shí)用性，所生成的數(shù)據(jù)在分段規(guī)模、堆場(chǎng)占用率、堆場(chǎng)布局等方面均參考了船廠的實(shí)際調(diào)度數(shù)據(jù).程序采用java代碼編寫，在 3.2 GHz雙核處理器、8 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行.

輸入?yún)?shù)設(shè)定如下：

(1) 調(diào)度周期10天；滾動(dòng)周期2天；分段在堆場(chǎng)中的平均停留時(shí)間3天.

(2) 組合及非組合分段數(shù)量為200個(gè)；堆場(chǎng)初始占用率分別為70%、80%、90%.

(3)wm=1，w1=0.01，當(dāng)分段按照策略無(wú)候選堆位或堆場(chǎng)已經(jīng)堆滿分段時(shí)，則將分段運(yùn)輸?shù)?號(hào)堆場(chǎng)，并在目標(biāo)函數(shù)中加入懲罰Z=5.

(4) 堆場(chǎng)狀態(tài)為5個(gè)單面通行的堆場(chǎng).堆場(chǎng)1為4×5；堆場(chǎng)2為5×6；堆場(chǎng)3為5×6；堆場(chǎng)4為 6×10；堆場(chǎng)5為6×10；堆場(chǎng)6為最終的總組堆場(chǎng)，不考慮堆場(chǎng)6內(nèi)的分段如何移動(dòng)(相當(dāng)于節(jié)點(diǎn))，共有200個(gè)堆位.堆場(chǎng)編號(hào)決定了分段按照工藝要求只能運(yùn)輸?shù)蕉褕?chǎng)編號(hào)較大的堆場(chǎng)，堆場(chǎng)內(nèi)每個(gè)堆位的間距為10 m，堆場(chǎng)布局及初始狀態(tài)如圖7所示，堆場(chǎng)之間的距離如表3所示.

(5) 禁忌搜索中MaxIter=100,NonImpIter=50.

圖7 多堆場(chǎng)調(diào)度堆場(chǎng)布局實(shí)例Fig.7 Example of multi-stockyard layout

表3 堆場(chǎng)之間的距離(m)Tab.3 Distance between multi-stockyard (m)

任務(wù)執(zhí)行順序策略：① 按照搭載時(shí)間余量確定任務(wù)的執(zhí)行順序；② 改進(jìn)任務(wù)的執(zhí)行順序并用禁忌搜索進(jìn)行優(yōu)化.

堆場(chǎng)堆位選擇策略：① 以平均出場(chǎng)間隔時(shí)間最小為依據(jù)選擇進(jìn)場(chǎng)堆位；② 綜合考慮進(jìn)場(chǎng)分段對(duì)在場(chǎng)分段及空堆位的影響后選擇堆位.

阻擋分段移動(dòng)策略：① 根據(jù)工藝階段，在下游堆場(chǎng)中以平均出場(chǎng)間隔時(shí)間最小為依據(jù)選擇阻擋分段堆位；② 在①的基礎(chǔ)上，根據(jù)阻擋分段對(duì)堆場(chǎng)空堆位及在場(chǎng)分段的影響指標(biāo)確定阻擋分段堆位.

組合對(duì)比任務(wù)執(zhí)行順序策略、進(jìn)場(chǎng)分段堆位選擇策略及阻擋分段移動(dòng)策略(共8種策略組合方式)，在新進(jìn)入堆場(chǎng)的分段數(shù)量為0或與進(jìn)入堆場(chǎng)6的分段數(shù)量相同的條件下進(jìn)行實(shí)驗(yàn).

當(dāng)新進(jìn)入5個(gè)堆場(chǎng)的分段數(shù)量為0時(shí)，代表周期內(nèi)沒有中小組立加工成為分段，即沒有分段從加工車間運(yùn)輸至堆場(chǎng)；當(dāng)新進(jìn)入5個(gè)堆場(chǎng)的分段數(shù)量等于堆場(chǎng)進(jìn)入堆場(chǎng)6的分段數(shù)量時(shí)，調(diào)度周期內(nèi)的堆場(chǎng)平均占用率可以維持在70%、80%、90%左右.組合策略的調(diào)度結(jié)果對(duì)比如表4所示，其中，F(xiàn)為目標(biāo)函數(shù);r為阻擋分段數(shù)量占任務(wù)分段的比例.由表4可知：在多堆場(chǎng)調(diào)度中，若堆場(chǎng)都是單面通行，則其阻擋分段的比例較高；當(dāng)無(wú)新分段進(jìn)入堆場(chǎng)時(shí)，幾種方法r的均值分別在30%、33%、37%左右； 當(dāng)堆場(chǎng)平均占用率保持相對(duì)穩(wěn)定時(shí)，幾種方法的阻擋分段比例分別在60%、70%、82%左右.

通過(guò)對(duì)比分析任務(wù)執(zhí)行順序策略，進(jìn)場(chǎng)分段位置選擇策略和阻擋分段移動(dòng)策略，可以得到在其他條件相同的情況下， 任務(wù)執(zhí)行順序策略②相比策略①對(duì)調(diào)度結(jié)果有一定程度的提升且始終優(yōu)于策略①；在堆場(chǎng)占用率較低時(shí)，與策略①的目標(biāo)函數(shù)值、阻擋分段數(shù)量相近，策略②對(duì)于阻擋分段非放回式的多堆場(chǎng)調(diào)度并沒有較大的提升空間；而當(dāng)分段數(shù)量較多時(shí)，任務(wù)執(zhí)行順序策略②的優(yōu)化效果較為明顯，說(shuō)明以完成搭載的時(shí)間余量規(guī)劃任務(wù)執(zhí)行順序只是考慮了分段對(duì)搭載的影響，并沒有考慮分段在堆場(chǎng)中調(diào)度的干涉，而通過(guò)改進(jìn)策略并用禁忌搜索進(jìn)行優(yōu)化后能夠使任務(wù)在執(zhí)行日期內(nèi)的排序更加合理.

進(jìn)場(chǎng)分段位置選擇策略②相較于策略①對(duì)調(diào)度結(jié)果的優(yōu)化有一定程度的提升，說(shuō)明考慮進(jìn)場(chǎng)分段對(duì)整個(gè)堆場(chǎng)影響的堆位選擇策略同樣適用于多堆場(chǎng)調(diào)度.通過(guò)考慮相鄰堆位分段相對(duì)出場(chǎng)時(shí)間均值的方式選擇堆位，而不是直接根據(jù)阻擋分段數(shù)量或是移動(dòng)距離長(zhǎng)短進(jìn)行判斷，其相鄰分段的出場(chǎng)時(shí)間可能較為接近，但在處理組合分段時(shí)有一定的局限性.策略①中組合分段只能與出場(chǎng)時(shí)間相同的分段進(jìn)行組合堆置，當(dāng)堆場(chǎng)較為復(fù)雜、占用率較高時(shí)，組合分段可選擇的堆位較少，可能會(huì)出現(xiàn)組合分段獨(dú)占一個(gè)堆位的情況，使調(diào)度成本上升.

阻擋分段移動(dòng)策略②對(duì)求解任務(wù)目標(biāo)函數(shù)的優(yōu)化程度很明顯.當(dāng)堆場(chǎng)占用率逐漸遞減時(shí)，在堆場(chǎng)初始占用率分別為70%、80%、90%的情況下，阻擋分段移動(dòng)策略②相比于策略①的目標(biāo)函數(shù)值分別有 7.6%、10.8%、11.5%的降低；當(dāng)堆場(chǎng)平均占用率保持不變時(shí)，策略②相比于策略①分別有19.1%、24.6%、37.9%的降低，這主要是由于當(dāng)保持5個(gè)堆場(chǎng)中的分段總數(shù)不變時(shí)，堆場(chǎng)密度可能出現(xiàn)不平衡，進(jìn)而造成某個(gè)堆場(chǎng)分段占用率很高，而其他幾個(gè)堆場(chǎng)分段占用率較低的情況.策略①的阻擋分段調(diào)度方式極大地增加了堆場(chǎng)本身的負(fù)擔(dān)，因此出現(xiàn)了很多阻擋分段無(wú)堆位可放的現(xiàn)象，增加了懲罰，從而提高了調(diào)度成本；而策略②將已經(jīng)完成加工的阻擋分段移動(dòng)到下一工藝階段的堆場(chǎng)符合調(diào)度的工藝方向，在一定程度上避免了分段過(guò)于集中的現(xiàn)象，降低了多堆場(chǎng)調(diào)度的復(fù)雜性.

3.2 實(shí)例驗(yàn)證

當(dāng)堆場(chǎng)占用率為70%時(shí)，分別使用任務(wù)執(zhí)行策略②、進(jìn)場(chǎng)堆位選擇策略②、阻擋分段移動(dòng)策略②作為分段調(diào)度策略.由于數(shù)據(jù)量較大，表5只列出了第1天和第2天的分段調(diào)度任務(wù)，表中第1組數(shù)據(jù)表示分段3于第1天執(zhí)行從堆場(chǎng)1的堆位2運(yùn)輸?shù)?號(hào)堆場(chǎng)的任務(wù).

圖8 堆場(chǎng)4示意圖Fig.8 Illustration of stockyard 4

表5 分段調(diào)度任務(wù)Fig.5 Block scheduling tasks

第1天以及第2天的任務(wù)調(diào)度結(jié)果如表6所示.其中，任務(wù)1表示分段158首先執(zhí)行，從堆場(chǎng)5的堆位22，經(jīng)過(guò)堆位12-11-1，最終運(yùn)輸至堆場(chǎng)6.但是，在執(zhí)行任務(wù)1時(shí)，將會(huì)遇到阻擋分段，而分段144是堆場(chǎng)5中出場(chǎng)時(shí)間比較晚的分段，因此將該分段任務(wù)提前執(zhí)行，經(jīng)過(guò)堆位11-1出場(chǎng)，然后再運(yùn)輸?shù)蕉褕?chǎng)6.

表6 分段任務(wù)調(diào)度結(jié)果Fig.6 Results of block scheduling tasks

(續(xù)表)

4 結(jié)論

針對(duì)船舶分段多堆場(chǎng)調(diào)度過(guò)程中成本高、效率低的問(wèn)題，提出考慮分段工藝階段的組合分段多堆場(chǎng)調(diào)度模型，增加了阻擋分段調(diào)度的靈活性，并通過(guò)改進(jìn)和優(yōu)化傳統(tǒng)多堆場(chǎng)調(diào)度任務(wù)的執(zhí)行順序得到了新的調(diào)度方案.主要結(jié)論如下：

(1) 分析對(duì)比了單堆場(chǎng)和多堆場(chǎng)調(diào)度的區(qū)別，構(gòu)建了組合分段多堆場(chǎng)調(diào)度模型，考慮了分段工藝階段、堆場(chǎng)容量及堆場(chǎng)四周通行情況，量化了多堆場(chǎng)調(diào)度的運(yùn)輸成本.

(2) 在考慮分段搭載節(jié)點(diǎn)的基礎(chǔ)上設(shè)計(jì)了啟發(fā)式規(guī)則用于調(diào)整任務(wù)的執(zhí)行順序，并通過(guò)禁忌搜索進(jìn)行優(yōu)化，結(jié)果表明該方法對(duì)于平均占用率較高的堆場(chǎng)效果明顯，可以有效地降低多堆場(chǎng)調(diào)度的運(yùn)輸成本.

(3) 考慮阻擋分段的跨堆場(chǎng)調(diào)度，設(shè)計(jì)了阻擋分段的移動(dòng)策略，將已完成當(dāng)前工藝的阻擋分段提前運(yùn)輸至目標(biāo)堆位，提升了多堆場(chǎng)調(diào)度的效率.

本文的研究對(duì)象為兩種規(guī)格的直角梯形分段多堆場(chǎng)調(diào)度，對(duì)于形狀不規(guī)則的堆場(chǎng)或任意規(guī)格分段的堆場(chǎng)調(diào)度方法還需進(jìn)一步深入研究.