考慮工藝順序和組合分段的多堆場調度方法

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

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

符號說明:

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

Ey—堆場y與道路可直接通行的堆位集合

jy—堆場y中的堆位j

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

多堆場調度并不是單堆場調度的簡單疊加，雖然其調度過程也是通過規劃分段調度的位置以及路線，進而確定分段任務的執行順序，但仍有諸多不同之處.

對于四面通行的單堆場調度，平板車的運輸路徑多為直線.文獻[1]以減少無效移動為目標，規劃堆場布局和內部通道，用阻擋分段率驗證分段調度在船舶生產中的重要意義.文獻[2]在文獻[1]的基礎上重新定義了堆場分段位置的分配問題，以進出堆場阻擋分段為優化目標，設計遺傳算法優化分段 堆位，提高了堆場調度效率.文獻[3]在遺傳算法優化分段堆位的基礎上，設計進場分段和阻擋分段的啟發式移動策略用于求解四面通行堆場的堆位分配問題.文獻[4]以阻擋分段數量為優化目標，設計進場分段的堆位選擇策略和阻擋分段的移動策略，得出分段任務的執行順序對調度結果有著重要影響的結論.

在實際應用中，直線運輸路徑一般用于場地資源不緊張的情況.當場地資源有限時，平板車的運輸路徑主要為折線.節點狀態模型是適用于折線運輸的調度模型且其分段形狀均為矩形.文獻[5]設計了啟發式規則以確定分段移動路線，并通過遺傳算法優化分段在堆場中的堆位.文獻[6]結合了分段質量和移動距離，用雙層遺傳算法確定分段的調度順序及其在堆場中的停放位置，并設計了啟發式算法規劃分段最優移動路線.文獻[7]在文獻[4]的基礎上，以分段移動度為優化目標，針對單面通行堆場設計了5種阻擋分段的移動策略，并用多鏈DNA遺傳算法對分段任務的執行順序進行求解.文獻[8]以分段移動度為優化目標，考慮分段工藝階段和多堆場堆位優先級，針對多個堆場的分段調度問題，設計了阻擋分段啟發式調度規則.文獻[9]提出將分段進行組合堆置，但僅研究了組合分段在單堆場中的調度問題，并沒有涉及多堆場調度.

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

以上研究都是只針對單一規格分段、堆位固定且只能容納一個分段的堆場調度問題，可處理的分段數量和種類較少，簡化了分段在各個堆場流轉過程中任務的連續性，忽略了分段的工藝順序.針對上述問題，本文在文獻[13]的基礎上提出了組合分段多堆場調度模型，考慮堆位內組合分段之間的干涉，設計了多堆場分段堆位選擇策略和阻擋分段跨堆場移動策略，以確定分段的目標堆位；改進了傳統的任務順序調整策略，并用禁忌搜索算法進行優化；最后，討論了不同調度策略對運輸成本的影響，并通過實例求解得到多堆場內任務和阻擋分段的多堆場調度方案.

1 問題模型

1.1 問題描述

分段多堆場調度示意圖如圖1所示，多堆場調度與單堆場調度的差異如表1所示.

圖1 分段多堆場調度示意圖Fig.1 Sketch of block transportation in multi-stockyard scheduling

表1 多堆場調度與單堆場調度的差異Tab.1 Difference between multi-stockyard scheduling and stockyard scheduling

多堆場調度遵循以下假設：

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

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

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

(4) 堆場之間由道路連接，不考慮道路寬度對平板車運輸的影響；

(5) 堆場外運輸先將分段運輸至堆場邊緣，再進行堆場內運輸，且堆場外運輸時將堆場視為節點；

(6) 堆場可進行部分后期加工，如完成預舾裝、涂裝等工序；

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

(8) 任務分段和阻擋分段根據下一個工序選擇堆場.

1.2 數學模型

多堆場調度主要從兩個角度對調度進行優化：① 減少調度過程中產生阻擋分段的數量，降低分段重復搬運造成的資源浪費；② 優化分段移動路線，降低平板車油耗.目標函數將綜合這兩個方面進行考慮.

決策變量：

目標函數：

(1) 任務分段移動時產生的阻擋分段總數

(1)

(2) 任務分段和阻擋分段在堆場內的運輸距離

(2)

(3) 任務分段及阻擋分段跨堆場間的運輸距離

(3)

優化目標函數表示為

F=

(4)

式中：wm表示移動阻擋分段的權重；wl表示平板車負載運輸的權重.

s.t.

(1) 分段運輸在調度周期內執行，

(5)

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

(6)

(3) 任務分段所在堆場符合分段所處的工藝階段，分段的下一個工藝階段是在合適的堆場進行,

(7)

(8)

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

(9)

(6) 在執行任務的過程中，進入目標堆場時，不能超過堆場容量，因此需要在目標堆場中找出能滿足大型分段或組合分段的堆位，

(10)

對目標函數求解之前，首先要獲取各堆場已知的初始狀態，包括堆場規格、分段布局和堆場四周的通行情況，分段只能經過堆場與道路可直接通行的堆位(即矩形堆場的某些邊)進出堆場.若分段按照策略無候選堆位或堆場已經堆滿分段時，則將分段運輸到6號堆場，并在目標函數中加入懲罰值Z.

2 模型求解

2.1 組合分段干涉方向判斷

利用啟發式規則判斷組合分段在一個堆位內的干涉方向：在可行的空域內，分段的最終參考點位置要盡可能靠近可行域最左下角的頂點，也就是文獻[13]中的最左最下規則.如圖2所示，b1為堆位中已經堆置好的分段，需要將分段b1的頂點G1靠近堆位最左下角的頂點；b2是將要與b1組合堆置的分段，頂點G2需要盡量靠近分段b1.因此，分段b1的可移動方向為上、左、下，即移動方向db1,j=j-N,j+N,j-1；當db1,j=j+1時，阻擋分段數量會增加.

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

使用空域的方法，對組合分段通過包絡轉角進行16種判斷，判斷過程如圖3所示.分段b1通過4次90° 的順時針旋轉調整其在堆位j中的堆置方向(圖3(a))，每種b1的堆置方向對應4種組合分段b2的堆置方向(圖3(b)).如圖3(b)所示，可以組合堆置的方式有0°、180° 兩種，因此，在分段組合堆置后，當移動b1時，對應的干涉方向分別為右方(0°)、右方和上方(180°)；當移動b2時，對應的干涉方向為左方、左方和下方.當有多種方式可以堆置分段時，需要選擇干涉方向較少的組合方式堆置分段.

實際上，在組合堆位的分段進入堆場的過程中，目標堆位上已有分段的堆置方式已經確定，需要根據不同的組合方式調整進場分段的堆置方向.整個調整過程依靠平板車的液壓驅動、液壓懸掛、獨立轉向、車架自動調平等技術完成.需要注意的是本文忽略了因再次調整組合分段位置產生的調度成本.

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

2.2 任務執行順序調整策略

表2 調度周期第t天的任務分段時間余量Tab.2 Time information of block transportation tasks on Day t of scheduling

分段在移動過程中應盡量減少阻擋分段的產生，因此若任務分段的阻擋分段中包含后續分段，則要將后續分段的運輸提前.如圖4所示，165,175表示計劃第5天出場的組合堆置的分段16和17，在實線標出的路徑上，3號分段是17號分段的阻擋分段，因此可以將3號分段提前運輸.具體步驟如下：

圖4 堆場內的分段任務執行順序Fig.4 Sequence of block transportation tasks in stockyard

步驟1先執行出場分段任務，將任務組內的出場分段按照移動成本進行排序.若成本相同，則按照時間余量進行排序.

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

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

步驟4判斷后續分段任務中是否有到當前分段的無阻擋路徑.若有，則將分段提前至任務分段之后執行；否則，返回步驟1繼續執行任務序列中的任務，直至所有任務執行完畢，得到最終的任務出場執行順序.

2.3 多堆場分段堆位選擇策略

步驟2選擇p′

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

步驟4得到集合A1和A2.

步驟5若A1和A2都為空集，則說明該堆場已經達到堆場容量上限.

候選堆位是允許堆置進場分段的堆位，具體堆位的選擇有如下兩種策略.

策略1若任務分段是組合分段，則選擇候選集合A2中出場時間相同的分段進行組合堆置；若分段是大型分段，或者無出場時間相同的組合分段，則計算每個空堆位與周圍分段的平均出場間隔時間

其中：R表示候選堆位四周的分段數量；τht,τr分別表示任務分段和四周各個分段的預計出場時間.選擇與周圍分段平均出場間隔時間最小的位置作為進場堆位.

策略2綜合考慮進場分段對在場分段及空堆位的影響，選擇合適的堆位堆置進場分段.堆位候選集合中每個可行堆位在放置任務分段后，需計算當前階段預計產生的調度成本，并選擇對后續分段移動影響最小的堆位，具體步驟如下：

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

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

步驟4對堆場中每個可推置堆位j″∈A1∪A2，同理計算有分段進入該堆位時的預計移動成本α2=∑j″∈A1∪A2(wmnj″+λwldj″)，得到分段i堆置于堆位j對整個堆場的影響指標Vj′=α+α1+α2.

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

步驟6選擇Vj′值最小的堆位作為分段i的進場堆位j.

2.4 阻擋分段跨堆場移動策略

在多堆場調度阻擋分段的堆位選擇過程中，阻擋分段可以在原有堆場中進行調度，也可以在完成當前堆場的部分加工后直接運輸到其他堆場.若需要移動到其他堆場，則要首先確定阻擋分段接下來要被運輸的目標堆場.目標堆場可以是符合阻擋分段下一階段工藝屬性的堆場或僅僅是臨時堆場，但不能返回阻擋分段當前工藝階段之前的堆場，否則將影響其他堆場內部的周轉，進而增大運輸成本.為了降低運輸的嵌套性，阻擋分段在位置重新分配的過程中不允許再次產生阻擋分段，只可以選取平板車能夠直接到達的堆場堆位.

策略3將阻擋分段就近堆置在原堆場，剔除原堆場中的任務分段路徑，選擇通行無阻擋的堆位；區分大型分段和組合分段，挑選與周圍分段出場時間較為接近的堆位進行堆置.

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

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

2.5 禁忌搜索

2.5.1禁忌搜索結構 通過鄰域搜索優化任務的執行順序.設:π為初始解；TL為一個空的禁忌搜索集合；Iter和NIter分別表示總迭代次數和結果沒有提升的次數.當Iter≥MaxIter或者NIter≥NonImpIter 時，則終止循環.計算步驟見文獻[9].

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

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

3 算例分析

3.1 調度結果分析

為了驗證模型以及算法的可行性，本文設計了多組實驗對其進行驗證.為了提高數據的實用性，所生成的數據在分段規模、堆場占用率、堆場布局等方面均參考了船廠的實際調度數據.程序采用java代碼編寫，在 3.2 GHz雙核處理器、8 GB內存的計算機上運行.

輸入參數設定如下：

(1) 調度周期10天；滾動周期2天；分段在堆場中的平均停留時間3天.

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

(3)wm=1，w1=0.01，當分段按照策略無候選堆位或堆場已經堆滿分段時，則將分段運輸到6號堆場，并在目標函數中加入懲罰Z=5.

(4) 堆場狀態為5個單面通行的堆場.堆場1為4×5；堆場2為5×6；堆場3為5×6；堆場4為 6×10；堆場5為6×10；堆場6為最終的總組堆場，不考慮堆場6內的分段如何移動(相當于節點)，共有200個堆位.堆場編號決定了分段按照工藝要求只能運輸到堆場編號較大的堆場，堆場內每個堆位的間距為10 m，堆場布局及初始狀態如圖7所示，堆場之間的距離如表3所示.

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

圖7 多堆場調度堆場布局實例Fig.7 Example of multi-stockyard layout

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

任務執行順序策略：① 按照搭載時間余量確定任務的執行順序；② 改進任務的執行順序并用禁忌搜索進行優化.

堆場堆位選擇策略：① 以平均出場間隔時間最小為依據選擇進場堆位；② 綜合考慮進場分段對在場分段及空堆位的影響后選擇堆位.

阻擋分段移動策略：① 根據工藝階段，在下游堆場中以平均出場間隔時間最小為依據選擇阻擋分段堆位；② 在①的基礎上，根據阻擋分段對堆場空堆位及在場分段的影響指標確定阻擋分段堆位.

組合對比任務執行順序策略、進場分段堆位選擇策略及阻擋分段移動策略(共8種策略組合方式)，在新進入堆場的分段數量為0或與進入堆場6的分段數量相同的條件下進行實驗.

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

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

進場分段位置選擇策略②相較于策略①對調度結果的優化有一定程度的提升，說明考慮進場分段對整個堆場影響的堆位選擇策略同樣適用于多堆場調度.通過考慮相鄰堆位分段相對出場時間均值的方式選擇堆位，而不是直接根據阻擋分段數量或是移動距離長短進行判斷，其相鄰分段的出場時間可能較為接近，但在處理組合分段時有一定的局限性.策略①中組合分段只能與出場時間相同的分段進行組合堆置，當堆場較為復雜、占用率較高時，組合分段可選擇的堆位較少，可能會出現組合分段獨占一個堆位的情況，使調度成本上升.

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

3.2 實例驗證

當堆場占用率為70%時，分別使用任務執行策略②、進場堆位選擇策略②、阻擋分段移動策略②作為分段調度策略.由于數據量較大，表5只列出了第1天和第2天的分段調度任務，表中第1組數據表示分段3于第1天執行從堆場1的堆位2運輸到3號堆場的任務.

圖8 堆場4示意圖Fig.8 Illustration of stockyard 4

表5 分段調度任務Fig.5 Block scheduling tasks

第1天以及第2天的任務調度結果如表6所示.其中，任務1表示分段158首先執行，從堆場5的堆位22，經過堆位12-11-1，最終運輸至堆場6.但是，在執行任務1時，將會遇到阻擋分段，而分段144是堆場5中出場時間比較晚的分段，因此將該分段任務提前執行，經過堆位11-1出場，然后再運輸到堆場6.

表6 分段任務調度結果Fig.6 Results of block scheduling tasks

(續表)

4 結論

針對船舶分段多堆場調度過程中成本高、效率低的問題，提出考慮分段工藝階段的組合分段多堆場調度模型，增加了阻擋分段調度的靈活性，并通過改進和優化傳統多堆場調度任務的執行順序得到了新的調度方案.主要結論如下：

(1) 分析對比了單堆場和多堆場調度的區別，構建了組合分段多堆場調度模型，考慮了分段工藝階段、堆場容量及堆場四周通行情況，量化了多堆場調度的運輸成本.

(2) 在考慮分段搭載節點的基礎上設計了啟發式規則用于調整任務的執行順序，并通過禁忌搜索進行優化，結果表明該方法對于平均占用率較高的堆場效果明顯，可以有效地降低多堆場調度的運輸成本.

(3) 考慮阻擋分段的跨堆場調度，設計了阻擋分段的移動策略，將已完成當前工藝的阻擋分段提前運輸至目標堆位，提升了多堆場調度的效率.

本文的研究對象為兩種規格的直角梯形分段多堆場調度，對于形狀不規則的堆場或任意規格分段的堆場調度方法還需進一步深入研究.