孟令通， 蔣祖華， 陶寧蓉， 劉建峰， 李柏鶴

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

在現(xiàn)代造船行業(yè)中，船舶建造以分段作為基本生產(chǎn)單元.分段在建造車間脫胎后，需經(jīng)過預(yù)舾裝、舾裝、涂裝、總組等工藝流程，再到船塢進(jìn)行搭載并最終合攏成整船.為了協(xié)調(diào)各工藝流程的工作節(jié)拍，船廠中劃分了若干堆場(chǎng)用于在生產(chǎn)流通過程中臨時(shí)存放分段.堆場(chǎng)中的調(diào)度作業(yè)是靠平板車完成的，為了減少平板車的運(yùn)輸耗油量、提高堆場(chǎng)的調(diào)度作業(yè)效率，優(yōu)化堆場(chǎng)調(diào)度方法至關(guān)重要[1].

利用現(xiàn)有的堆場(chǎng)布局方式及調(diào)度方法，只能解決單一規(guī)格分段的調(diào)度問題.在多規(guī)格分段堆場(chǎng)的堆位布局和堆場(chǎng)調(diào)度中，通常以犧牲空間資源利用率來達(dá)到簡(jiǎn)化調(diào)度作業(yè)的目的.由于經(jīng)驗(yàn)型堆場(chǎng)布局過多，容易導(dǎo)致調(diào)度作業(yè)效率下降、空間利用率過低等問題.實(shí)際上，許多分段工藝具有相似性，只要組合分段的堆置時(shí)間相近且形狀互補(bǔ)，就能夠堆置在同一堆位中.設(shè)計(jì)針對(duì)組合分段的堆場(chǎng)調(diào)度方法，可以有效地增加堆場(chǎng)的空間利用率、提高船舶的生產(chǎn)效率，同時(shí)降低堆場(chǎng)的調(diào)度成本.

分段堆場(chǎng)調(diào)度問題是一種考慮時(shí)間及空間約束的調(diào)度問題.該問題的核心是優(yōu)化船舶分段在堆場(chǎng)中的堆位分配、進(jìn)出堆場(chǎng)路徑及任務(wù)執(zhí)行順序，并最終達(dá)到分段存取物流成本最小化的目標(biāo)[2].文獻(xiàn)[3]分析了分段堆場(chǎng)調(diào)度問題的物流成本，將阻擋分段的移動(dòng)作為非增值運(yùn)輸，提出了分段堆位選擇策略和阻擋分段移動(dòng)策略，并在此基礎(chǔ)上研究了分段移動(dòng)次序和堆場(chǎng)布局對(duì)調(diào)度結(jié)果的影響.文獻(xiàn)[4]重新定義了分段堆場(chǎng)調(diào)度問題，將堆場(chǎng)劃分為若干個(gè)堆位，分段與堆位之間一一對(duì)應(yīng)，則分段堆場(chǎng)調(diào)度問題可以轉(zhuǎn)化為堆場(chǎng)中的堆位選擇問題.文獻(xiàn)[5]將任務(wù)執(zhí)行順序作為堆場(chǎng)調(diào)度的優(yōu)化目標(biāo)之一，提出啟發(fā)式堆位分配策略，并通過禁忌搜索算法進(jìn)行求解，提高了分段在堆場(chǎng)內(nèi)的周轉(zhuǎn)效率.但是，上述研究均假設(shè)運(yùn)輸路徑為直線，且阻擋分段在移動(dòng)后要放回原堆位，這種調(diào)度方式的分段移動(dòng)條件較為苛刻，增加了分段的重復(fù)運(yùn)輸，僅適用于場(chǎng)地規(guī)模較小的堆場(chǎng).為了解決這些問題，文獻(xiàn)[6]將分段移動(dòng)度作為優(yōu)化目標(biāo)，通過最短路徑算法求解分段運(yùn)輸?shù)闹苯钦劬€路徑，減少了調(diào)度過程中阻擋分段的移動(dòng).文獻(xiàn)[7]將運(yùn)輸分段的平板車數(shù)量作為優(yōu)化目標(biāo)，構(gòu)建分段搬運(yùn)兩階段優(yōu)化模型,通過遺傳算法求解運(yùn)輸路徑，降低了平板車數(shù)量.文獻(xiàn)[8]考慮了分段調(diào)度過程中的隨機(jī)擾動(dòng)，并利用改進(jìn)遺傳算法進(jìn)行求解.文獻(xiàn)[9]針對(duì)隨機(jī)進(jìn)場(chǎng)的分段，提出用反向傳播神經(jīng)網(wǎng)絡(luò)來預(yù)測(cè)一個(gè)周期內(nèi)進(jìn)出場(chǎng)的分段數(shù)量，并研究建立了以分段移動(dòng)度最小為目標(biāo)的優(yōu)化模型.文獻(xiàn)[2]考慮了分段進(jìn)場(chǎng)時(shí)間窗，提出了5種阻擋分段移動(dòng)策略，利用多鏈DNA遺傳算法進(jìn)行求解，并驗(yàn)證了其收斂性.上述研究從不同角度對(duì)分段在堆場(chǎng)內(nèi)的運(yùn)輸進(jìn)行了優(yōu)化，雖然將運(yùn)輸路線由單一的直線變?yōu)檎劬€，但降低堆場(chǎng)調(diào)度成本的關(guān)鍵在于減少阻擋分段的移動(dòng)數(shù)量.

除了堆場(chǎng)布局和運(yùn)輸路線外，堆場(chǎng)分段形狀對(duì)堆場(chǎng)調(diào)度問題也有著重要影響.文獻(xiàn)[10]將船體分段在場(chǎng)地上的加工抽象成凸多邊形在矩形平面上的二維空間布局問題，應(yīng)用可配置空間的概念定義可放置空間集，縮小了空間布局的搜索空間.文獻(xiàn)[11]基于分段形狀和投影交叉分析，研究梯形分段的空間約束，構(gòu)建時(shí)空利用率模型對(duì)分段進(jìn)行調(diào)度，提高了堆場(chǎng)利用率.文獻(xiàn)[12]針對(duì)帶有進(jìn)場(chǎng)時(shí)間窗的不規(guī)則分段在堆場(chǎng)中的調(diào)度，采用遺傳算法和最大平均空閑矩形的空間定位策略對(duì)分段的進(jìn)出場(chǎng)順序、位置和方向進(jìn)行了優(yōu)化，同時(shí)考慮了不規(guī)則分段的擺放角度對(duì)場(chǎng)地利用率的影響，解決了不規(guī)則分段的動(dòng)態(tài)場(chǎng)地堆放問題.但是，上述研究并沒有劃分堆場(chǎng)，僅適用于分段數(shù)量較少的情況，且大多采用吊裝設(shè)備直接運(yùn)輸?shù)轿唬⒉贿m用于平面運(yùn)輸.

目前，船舶的分段堆場(chǎng)調(diào)度研究中大部分針對(duì)的是單一規(guī)格、堆位固定且只能容納1個(gè)分段的情況，進(jìn)場(chǎng)分段堆位分配多數(shù)采用隨機(jī)分配的方式，阻擋分段的移動(dòng)策略大多采用放回式策略.然而，這些研究并沒有分析堆場(chǎng)四周道路通行情況對(duì)分段運(yùn)輸效率的影響.

針對(duì)上述問題，本文提出一種組合分段堆場(chǎng)調(diào)度模型，以及進(jìn)場(chǎng)分段堆位分配策略和阻擋分段移動(dòng)策略；基于運(yùn)輸方向的深度優(yōu)先搜索算法得到分段任務(wù)執(zhí)行時(shí)的路徑，并設(shè)計(jì)遺傳算法與禁忌搜索相結(jié)合的混合式算法求解任務(wù)分段的執(zhí)行順序；最后，討論了堆場(chǎng)四周道路通行能力對(duì)運(yùn)輸效率的影響，對(duì)比分析了場(chǎng)地規(guī)模、調(diào)度周期、堆場(chǎng)占用率等不同因素對(duì)調(diào)度結(jié)果的影響.

1 問題建模

1.1 問題描述

針對(duì)多規(guī)格梯形分段，在由W×H個(gè)矩形堆位組成的四面通行堆場(chǎng)中，每個(gè)堆位可以堆置1個(gè)大型分段或2個(gè)小型分段.堆置多個(gè)分段時(shí)，各分段之間存在相互干涉,會(huì)影響分段進(jìn)出堆場(chǎng)的方向.分段移動(dòng)有以下3種類型：① 將分段存放于堆場(chǎng)的空堆位或組合堆位；② 從堆場(chǎng)中取出分段；③ 將阻擋分段移動(dòng)至其他空堆位或組合堆位.

給定一組多規(guī)格分段進(jìn)出堆場(chǎng)的任務(wù)，分段進(jìn)出堆場(chǎng)時(shí)可能會(huì)有阻擋分段在其移動(dòng)路線上，進(jìn)而導(dǎo)致產(chǎn)生分段的無效移動(dòng).因此，通過規(guī)劃進(jìn)出場(chǎng)分段移動(dòng)路線、進(jìn)場(chǎng)分段堆位、阻擋分段堆位及分段任務(wù)的執(zhí)行順序能夠使調(diào)度周期內(nèi)阻擋分段的數(shù)量最小.為了保證調(diào)度的準(zhǔn)時(shí)性，分段任務(wù)需滿足進(jìn)出堆場(chǎng)的設(shè)定日期.

多規(guī)格分段堆場(chǎng)內(nèi)的調(diào)度應(yīng)遵循如下規(guī)則：

(1) 組合分段在堆場(chǎng)中的堆置不可堆疊，且不可超出堆位范圍，在堆位完全清空前禁止平板車的運(yùn)輸及通行.

(2) 堆場(chǎng)四周環(huán)繞道路，任務(wù)分段可以從上下左右4個(gè)方向進(jìn)出堆場(chǎng).

(3) 進(jìn)場(chǎng)分段至少在堆場(chǎng)中存放1天，若是分段當(dāng)天進(jìn)當(dāng)天出，則將其視為直接進(jìn)入下一工藝階段.

(4) 進(jìn)場(chǎng)分段和阻擋分段按照策略進(jìn)行移動(dòng)，進(jìn)場(chǎng)分段進(jìn)場(chǎng)時(shí)允許產(chǎn)生阻擋分段，但阻擋分段在位置再次分配時(shí)不允許再次產(chǎn)生阻擋.

(5) 分段移動(dòng)時(shí)遇到阻擋分段時(shí)的成本遠(yuǎn)大于無阻擋時(shí)的成本，故最短距離指路徑上的阻擋分段最少.

(6) 一個(gè)堆位需通過文獻(xiàn)[13]中的內(nèi)外接多邊形方法，依據(jù)分段的尺寸形狀判斷其能否組合堆置.若能，則為組合堆位，并得到組合內(nèi)分段移動(dòng)時(shí)相互干涉的方向.

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

一個(gè)4×5規(guī)格的組合分段堆場(chǎng)，其四周均為道路，可供載有分段的平板車進(jìn)出.該堆場(chǎng)第5天的狀態(tài)如圖1所示，75和56分別表示該堆位有7號(hào)和5號(hào)2個(gè)分段，其計(jì)劃出場(chǎng)時(shí)間分別是第5天和第6天.當(dāng)7號(hào)分段移出堆場(chǎng)時(shí)，其較短路徑有實(shí)線和虛線2條，由于組合分段存在干涉，向右或向下移動(dòng)時(shí)組合分段會(huì)產(chǎn)生阻擋，即在選擇虛線路徑時(shí)要移動(dòng)27號(hào)和5號(hào)2個(gè)分段，阻擋分段數(shù)量為2；而實(shí)線路徑僅需移動(dòng)9號(hào)分段，阻擋分段數(shù)量為1，因此選擇實(shí)線作為最短調(diào)度路線.

圖1 組合分段堆場(chǎng)實(shí)例Fig.1 Sketch of combined block storage yard

決策變量：

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

(1)

(2)

(3)

dRi,j∈di,j

(4)

(5)

(6)

bi,j≤bi,j′

(7)

目標(biāo)函數(shù)求解的是當(dāng)前周期內(nèi)分段調(diào)度任務(wù)產(chǎn)生的阻擋分段最小值.前半部分是進(jìn)場(chǎng)分段(sb)任務(wù)的阻擋分段數(shù)量，其中t+1表示分段i至少在堆場(chǎng)中停留1天；后半部分是出場(chǎng)分段(rb)任務(wù)的阻擋分段數(shù)量，其中t-1表示分段在出場(chǎng)之前堆位不變.阻擋分段在移動(dòng)后會(huì)重新分配堆位.

采用遺傳算法與禁忌搜索相結(jié)合的混合式算法求解上述問題，并利用深度優(yōu)先搜索算法逐一求出任務(wù)分段進(jìn)出堆場(chǎng)時(shí)的最短路徑.式(2)保證了每個(gè)分段只執(zhí)行1次進(jìn)場(chǎng)或出場(chǎng)任務(wù)；式(3)表示在堆場(chǎng)中同一個(gè)堆位上至多可以堆置2個(gè)小型分段；式(4)表示由于分段之間的相互干涉影響了分段進(jìn)出堆場(chǎng)時(shí)的移動(dòng)方向，所以任務(wù)分段最短路徑方向要與分段允許進(jìn)出堆位的方向一致，若兩者不同，則會(huì)增加阻擋分段數(shù)量；式(5)保證了進(jìn)場(chǎng)分段要在其規(guī)定進(jìn)場(chǎng)時(shí)間內(nèi)進(jìn)入堆場(chǎng)；式(6)保證了出場(chǎng)分段要在其規(guī)定出場(chǎng)時(shí)間內(nèi)移出堆場(chǎng)；式(7)保證了任務(wù)分段經(jīng)由阻擋最少的路徑進(jìn)出堆場(chǎng).

2 模型求解

2.1 求解組合分段最短移動(dòng)路線

在組合堆場(chǎng)中，相互組合的分段在運(yùn)輸時(shí)可能會(huì)限制彼此的移動(dòng)方向，此時(shí)將堆位作為節(jié)點(diǎn)處理會(huì)使得求解過程過于繁瑣.利用深度優(yōu)先搜索算法，遍歷任務(wù)分段行進(jìn)方向上的所有路線，即可找到進(jìn)場(chǎng)分段進(jìn)入某堆位或出場(chǎng)分段從某堆位運(yùn)輸?shù)蕉褕?chǎng)邊緣的最短路線，其詳細(xì)步驟如下.

步驟1確定分段的初始堆位，設(shè)最小阻擋分段數(shù)量bm=+∞，當(dāng)前阻擋分段數(shù)量b=0.選取分段允許的移動(dòng)方向作為初始移動(dòng)方向d.若選擇的方向被組合分段阻擋，則b=b+1.

步驟2選擇當(dāng)前堆位的分段移動(dòng)方向，注意不能與初始移動(dòng)方向或已選擇的移動(dòng)方向相反，記該方向?yàn)閐′.

步驟3判斷移動(dòng)方向上的堆位是否堆有分段，若有，則b=b+z(z為堆位上的阻擋分段數(shù)量)，并記錄該堆位.

步驟4判斷堆位是否位于堆場(chǎng)邊界.

(1) 若是邊緣堆位，則得到阻擋分段數(shù)量b.如果b

(2) 若不是邊緣堆位，則返回步驟2.

步驟5選擇當(dāng)前堆位的前驅(qū)堆位改變移動(dòng)方向并修正b值，執(zhí)行步驟3，直至將初始堆位移動(dòng)方向遍歷完畢，執(zhí)行下一步驟.

步驟6返回最短路徑堆位編號(hào)及bm.

2.2 組合分段堆位分配策略

分段任務(wù)分為進(jìn)場(chǎng)分段任務(wù)和出場(chǎng)分段任務(wù)，這些任務(wù)在執(zhí)行過程中可能會(huì)產(chǎn)生阻擋分段.為了減少進(jìn)場(chǎng)分段和阻擋分段對(duì)后續(xù)分段任務(wù)造成的影響，采用非放回式分段移動(dòng)方法(即在阻擋分段讓路后重新分配堆位)，通過進(jìn)場(chǎng)分段堆位分配策略和阻擋分段移動(dòng)策略，選擇進(jìn)場(chǎng)分段對(duì)堆場(chǎng)影響指標(biāo)最小的位置堆置分段，進(jìn)而減少阻擋分段的數(shù)量.

任務(wù)分段的堆位對(duì)堆場(chǎng)的影響分為兩種：① 可能阻擋出場(chǎng)分段的移動(dòng)；② 可能阻擋進(jìn)場(chǎng)分段進(jìn)入空堆位或組合堆位.由于每個(gè)堆置于堆場(chǎng)的分段或空堆位都有當(dāng)前進(jìn)出堆場(chǎng)的最短路徑，在空堆位或組合堆位上堆置新的分段可能會(huì)使阻擋分段有所增加，所以通過計(jì)算進(jìn)場(chǎng)分段對(duì)堆場(chǎng)已有分段移出堆場(chǎng)的影響指標(biāo)α和分段移入空堆位的影響指標(biāo)β，在候選堆位集合中選擇任務(wù)分段i的堆位.

圖2所示為分段在堆場(chǎng)中的布局示意圖和影響系數(shù)矩陣，標(biāo)紅部分分別是進(jìn)場(chǎng)分段(左)和預(yù)計(jì)產(chǎn)生的阻擋分段數(shù)量(右).由于影響分段出場(chǎng)的只能是出場(chǎng)時(shí)間較晚的分段，所以在預(yù)計(jì)某分段移出堆場(chǎng)的阻擋時(shí)可以忽略出場(chǎng)時(shí)間較早或同時(shí)出堆場(chǎng)的分段.例如，在圖2的案例3中，進(jìn)場(chǎng)8號(hào)分段允許與25號(hào)分段組合堆置，雖然進(jìn)場(chǎng)分段可能會(huì)限制25號(hào)分段的出場(chǎng)移動(dòng)方向，然而25號(hào)上方的分段出場(chǎng)時(shí)間較早，因此，該組合堆置并不會(huì)增加25號(hào)分段的出場(chǎng)難度，即可以計(jì)算得出α=0.

圖2 進(jìn)場(chǎng)分段堆位選擇策略示意圖Fig.2 Illustration of selecting location for the incoming block

進(jìn)場(chǎng)分段堆置于堆位k對(duì)堆場(chǎng)的影響指標(biāo)Vk=α+β.然而，通過這種方式計(jì)算得到分段進(jìn)場(chǎng)對(duì)整個(gè)堆場(chǎng)的影響時(shí)，可能會(huì)出現(xiàn)權(quán)重相同的情況.為了避免出現(xiàn)這種情況，在符合組合堆置要求的堆位中，應(yīng)首先選取移動(dòng)時(shí)間相近的堆位，或通過文獻(xiàn)[3]中的方式選取堆位編號(hào)較大的堆位進(jìn)行組合堆置.需要注意的是在選擇過程中仍需考慮進(jìn)場(chǎng)分段進(jìn)入堆場(chǎng)不同堆位后產(chǎn)生的阻擋分段數(shù)量.

2.2.2阻擋分段移動(dòng)策略 阻擋分段的運(yùn)輸需在任務(wù)分段執(zhí)行前完成.阻擋分段的堆位重新分配策略與進(jìn)場(chǎng)分段堆位分配策略類似，但在位置再分配時(shí)不允許再次產(chǎn)生阻擋分段，其具體步驟如下.

步驟1獲取任務(wù)分段執(zhí)行時(shí)的阻擋分段.

2.3 混合算法設(shè)計(jì)

在堆場(chǎng)調(diào)度時(shí)，組合分段的堆位選擇由啟發(fā)式算法確定，進(jìn)出堆場(chǎng)路線由組合干涉與深度優(yōu)先搜索算法產(chǎn)生，因此優(yōu)化任務(wù)分段執(zhí)行序列才是堆場(chǎng)內(nèi)調(diào)度問題的核心.遺傳算法有并行搜索能力，在一定程度上能保留歷史信息，適合求解大規(guī)模的全局優(yōu)化問題，但其局部搜索能力差，變異概率小，引入新染色體機(jī)會(huì)少，所以采用綜合了大范圍搜索的遺傳算法與局部搜索的禁忌算法的混合算法求解分段任務(wù)執(zhí)行序列.

2.3.1遺傳算法設(shè)計(jì) 初始種群由周期內(nèi)的任務(wù)分段按照各分段的執(zhí)行日期隨機(jī)產(chǎn)生，每條染色體代表1種任務(wù)執(zhí)行序列.染色體上的每個(gè)基因記錄了任務(wù)分段的執(zhí)行信息，包括進(jìn)場(chǎng)分段的位置分配、路徑的選擇和阻擋分段的移動(dòng).進(jìn)場(chǎng)任務(wù)用S表示，出場(chǎng)任務(wù)用R表示.

根據(jù)任務(wù)執(zhí)行序列，計(jì)算每條染色體產(chǎn)生的阻擋分段數(shù)量，具體步驟：① 取堆場(chǎng)初始的占用狀態(tài)；② 按照堆位分配策略選擇進(jìn)場(chǎng)分段堆位，利用深度優(yōu)先搜索選擇分段進(jìn)出堆場(chǎng)的路徑，得到任務(wù)執(zhí)行過程中的阻擋分段數(shù)量；③ 用阻擋分段移動(dòng)策略處理阻擋分段；④ 更新堆場(chǎng)狀態(tài)，執(zhí)行下一個(gè)任務(wù).由此得到目標(biāo)函數(shù)F，遺傳算法的適應(yīng)度f*=M-F，M為足夠大的整數(shù).為了提高算法的收斂速度，采用比例復(fù)制和輪盤賭的方法選取染色體.其中：比例復(fù)制為將適應(yīng)度靠前的個(gè)體直接復(fù)制到下一代；輪盤賭為根據(jù)個(gè)體適應(yīng)度計(jì)算出的概率決定是否復(fù)制到下一代.下一代的其余個(gè)體由單點(diǎn)交叉(見圖3(a))和交換變異(見圖3(b))產(chǎn)生.由于交換后的序列往往存在任務(wù)重復(fù)、任務(wù)遺漏、時(shí)間交錯(cuò)等問題，所以在染色體交叉后需要進(jìn)行基因修復(fù)，以保證任務(wù)分段的執(zhí)行時(shí)間不會(huì)發(fā)生變化.新一代種群由比例復(fù)制、輪盤賭、單點(diǎn)交叉及交換變異產(chǎn)生，其占比分別為PE,PR,PC,PM.

2.3.2禁忌搜索設(shè)計(jì) 對(duì)每一代種群中適應(yīng)度值最大的個(gè)體進(jìn)行禁忌搜索.禁忌搜索是組合堆場(chǎng)調(diào)度過程的局部最優(yōu)搜索.其鄰域搜索過程如圖4所示，解的鄰域空間通過以下步驟獲取：① 選擇當(dāng)前種群中適應(yīng)度值最大的個(gè)體；② 選擇周期內(nèi)的某一天將任務(wù)分段插入當(dāng)天其他的堆位執(zhí)行；③ 檢測(cè)搜索結(jié)果的可行性，保證堆場(chǎng)不會(huì)被分段堆滿.將鄰域操作的檢測(cè)結(jié)果記錄于禁忌表中，以避免循環(huán)操作.

圖3 染色體交叉變異Fig.3 Crossover and mutation for chromosomes

圖4 鄰域搜索Fig.4 Neighborhood search

每個(gè)任務(wù)用(t,x1,x2)表示，其中：x1表示隨機(jī)選擇調(diào)整位置的任務(wù)；x2表示任務(wù)x1將要插入的位置.禁忌表的長(zhǎng)度表示在迭代過程中不能選擇禁忌對(duì)象的步數(shù).迭代系數(shù)有2個(gè)：Iter代表總迭代次數(shù)；NIter代表計(jì)算結(jié)果沒有提升的迭代次數(shù).

2.3.3混合算法的流程

步驟1設(shè)定初始參數(shù)，包括最大迭代次數(shù)N，種群規(guī)模Z，子代生成比例PE、PR、PC、PM，禁忌搜索最大迭代次數(shù)MaxIter，和最大無效迭代次數(shù)NonIter.

步驟2按照周期內(nèi)的日期順序，對(duì)任務(wù)序列進(jìn)行編碼，當(dāng)前迭代次數(shù)n=0.

步驟4計(jì)算個(gè)體適應(yīng)度

其中適應(yīng)度最高的個(gè)體為xbest，其任務(wù)序列為seq，設(shè)最優(yōu)適應(yīng)度F*=f*(xbest).

步驟5對(duì)于任務(wù)序列seq，禁忌表TL=?，Iter=NIter=0.

步驟6隨機(jī)生成seq的鄰域變換(t,x1,x2)，產(chǎn)生鄰域集合S(seq).

步驟8Iter=Iter+1，NIter=NIter+1，若 Iter>MaxIter或NIter>NonIter，則執(zhí)行步驟9；否則返回步驟6.

步驟9將所有個(gè)體按照適應(yīng)度值由大到小排列，直接保留比例為PE的精英個(gè)體，利用輪盤賭選擇比例為PR的個(gè)體.

步驟10隨機(jī)選取父代中的2條染色體進(jìn)行單點(diǎn)交叉，產(chǎn)生比例為PC的子代.

步驟11隨機(jī)選取父代中的2條染色體進(jìn)行交換變異，產(chǎn)生比例為PM的子代.

步驟12若n

步驟13停止運(yùn)算，輸出xbest和任務(wù)序列seq.

3 算例分析

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

表1 3種調(diào)度方法的結(jié)果對(duì)比Tab.1 Comparisons of three scheduling strategies

由表1可知：M2和M3中組合分段堆場(chǎng)處理的任務(wù)分段數(shù)量更多；M2的目標(biāo)函數(shù)值較高，但阻擋分段的比例優(yōu)于M1，說明進(jìn)場(chǎng)分段及阻擋分段移動(dòng)策略較文獻(xiàn)[4]中的方法更好，在一定程度上減少了阻擋分段的產(chǎn)生；M3的調(diào)度結(jié)果明顯優(yōu)于M2，說明任務(wù)執(zhí)行序列對(duì)調(diào)度結(jié)果的影響十分顯著，任務(wù)執(zhí)行周期內(nèi)進(jìn)入堆場(chǎng)的分段會(huì)對(duì)后續(xù)分段的調(diào)度產(chǎn)生很大的干擾，而通過混合算法可以從一定程度上減少分段的再次阻擋，從而提高堆場(chǎng)的調(diào)度效率，減少阻擋分段數(shù)量.此外，堆場(chǎng)布局和堆場(chǎng)平均占用率也對(duì)調(diào)度結(jié)果有著一定的影響.隨著堆場(chǎng)與道路間通道的減少(3×20、4×15、5×12、6×10的堆場(chǎng)，通道數(shù)量依次為46, 38, 34, 32)，F(xiàn)及r隨之增加；隨著μ的增大，即堆置的分段越來越密集，F(xiàn)及r隨之增加；隨著調(diào)度周期長(zhǎng)短的變化，F(xiàn)及r并無直接的變化關(guān)系.由此可得，堆場(chǎng)布局以及堆位平均占用率是影響堆場(chǎng)調(diào)度成本的兩大因素，通過啟發(fā)式策略分配堆位和混合算法能有效地降低阻擋分段的數(shù)量.

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

圖5 通行能力及堆場(chǎng)平均占用率對(duì)調(diào)度結(jié)果的影響Fig.5 Influence of capacity and workload on different scheduling strategies

由圖5(a)可知： 堆場(chǎng)布局為3×20的堆場(chǎng)在所有通行情況中，r都是最小的；當(dāng)堆場(chǎng)四周為三面通行或兩面通行時(shí)，r較為固定(約為20%)，說明堆場(chǎng)布局對(duì)調(diào)度結(jié)果的影響較??；當(dāng)堆場(chǎng)為四面通行或單面通行時(shí)，r浮動(dòng)較大，變化范圍超過10%，說明在這2種條件下， 堆場(chǎng)布局對(duì)調(diào)度結(jié)果的影響十分顯著.由圖5(b)可知：當(dāng)μ相同(即任務(wù)數(shù)量相同)時(shí)，F(xiàn)隨堆場(chǎng)布局由“扁平”到“均勻”逐漸增大；當(dāng)μ逐漸增加，堆場(chǎng)布局為3×20的堆場(chǎng)F值的增幅明顯小于堆場(chǎng)布局為6×10的堆場(chǎng)，說明越“均勻”的堆場(chǎng)，場(chǎng)地復(fù)雜度越高，各分段之間更容易產(chǎn)生空間上的干涉.

4 結(jié)論

針對(duì)船舶分段堆場(chǎng)調(diào)度過程中經(jīng)驗(yàn)型堆場(chǎng)布局過多、作業(yè)效率低下、空間利用率過低等問題，提出一種組合分段堆場(chǎng)調(diào)度模型，有效地增加了堆場(chǎng)處理任務(wù)分段的能力.同時(shí)，通過對(duì)比堆位分配策略與傳統(tǒng)策略以及混合算法優(yōu)化前后的分析結(jié)果，證明了該調(diào)度分配策略與混合算法的有效性，獲得的主要結(jié)論如下：

(1) 構(gòu)建組合分段堆場(chǎng)調(diào)度模型，考慮單一堆位堆置組合分段的情況和堆位內(nèi)分段之間的干涉，并與深度優(yōu)先搜索相結(jié)合，規(guī)劃任務(wù)分段堆場(chǎng)內(nèi)的移動(dòng)路線，減少了分段的無效移動(dòng)，提高了堆場(chǎng)的利用率.

(2) 考慮任務(wù)分段分別對(duì)出場(chǎng)分段移動(dòng)和進(jìn)場(chǎng)分段進(jìn)入空堆位的影響，提出進(jìn)場(chǎng)分段堆位分配策略及阻擋分段移動(dòng)策略，相比原有的隨機(jī)分配進(jìn)場(chǎng)分段堆位方式，阻擋分段數(shù)量明顯減少.

(3) 考慮任務(wù)分段執(zhí)行順序，以阻擋分段最少為優(yōu)化目標(biāo)，通過混合算法求解得出進(jìn)場(chǎng)任務(wù)堆位、阻擋分段堆位、進(jìn)出場(chǎng)任務(wù)移動(dòng)路線以及任務(wù)分段執(zhí)行序列，進(jìn)一步減少了阻擋分段的數(shù)量，相比遺傳算法，從一定程度上避免了陷入局部最優(yōu)解.

由于船廠的條件限制，所提方法僅利用模擬數(shù)據(jù)進(jìn)行驗(yàn)證，并未使用船廠的實(shí)際生產(chǎn)數(shù)據(jù)，對(duì)實(shí)際生產(chǎn)中可能遇到的問題還需進(jìn)一步研究.另外，本文僅針對(duì)矩形堆場(chǎng)和2種規(guī)格的梯形分段進(jìn)行調(diào)度，對(duì)于形狀不規(guī)則堆場(chǎng)或任意規(guī)格分段的調(diào)度方法，還需進(jìn)一步深入研究.