陳云云，張志英

(同濟大學 機械與能源工程學院，上海 201804)

?

船舶分段涂裝作業(yè)重入調(diào)度優(yōu)化算法

陳云云，張志英

(同濟大學 機械與能源工程學院，上海 201804)

針對分段涂裝過程中存在調(diào)度效率低、完工時間長等問題，本文將分段涂裝作業(yè)抽象為帶有時間和空間約束的批-離散機重入過程，以最小化最大完工時間為優(yōu)化目標建立數(shù)學模型，構造了基于重排策略的啟發(fā)式算法。通過聚類算法和基于模擬退火的組批重排策略獲得不考慮空間約束的分段分批結果，利用最大接觸策略實現(xiàn)分段的空間組批調(diào)度，提出基于最大剩余加工時間策略和遺傳算法的超啟發(fā)式算法進行分段的重入調(diào)度。仿真實驗表明，所提出的算法可以充分利用沖砂車間的空間，得到較優(yōu)的分段涂裝調(diào)度計劃。

分段涂裝；涂裝作業(yè);時間約束；空間約束；重入調(diào)度；啟發(fā)式算法； 聚類算法;優(yōu)化算法

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160624.1127.002.html

船舶制造過程包括分段組立、預舾裝，分段涂裝和分段搭載等工序。涂裝作業(yè)處于船體生產(chǎn)過程的中間位置，有著承前啟后的作用。前面工序由于場地、原材料供應等因素影響，延時嚴重；后續(xù)工序由于船塢搭載計劃變更，交貨期提前。這使得分段涂裝作業(yè)的加工時間要求非常嚴格。因此，提高分段涂裝作業(yè)的效率對縮短船舶制造周期有著重要的作用。分段涂裝作業(yè)包括沖砂和噴涂工序。分段沖砂指的是沖砂隊對砂房中的分段表面進行二次除銹。沖砂結束的分段應及時涂上底漆，防止表面氧化。分段噴涂是噴涂隊對分段涂漆作業(yè)。根據(jù)船舶建造質(zhì)量和工藝規(guī)劃要求，分段噴涂一般要分幾次進行，噴涂次數(shù)與規(guī)定的涂層厚度有關，并且各度噴涂之間要有一定的干燥時間。分段涂裝調(diào)度過程不僅要考慮沖砂和噴涂階段的時間約束，還需考慮沖砂車間和噴涂車間的空間約束及噴涂隊的派遣。因此，船舶分段涂裝作業(yè)可歸結為帶有時間和空間約束的重入調(diào)度問題。

現(xiàn)階段國內(nèi)外對分段涂裝調(diào)度的研究較少。Cho等[1]針對分段涂裝調(diào)度，設計了包含操作策略算法、分段調(diào)度算法、安排算法和分派算法的空間調(diào)度系統(tǒng)。在此基礎上，Kwon等[2]提出了分段涂裝調(diào)度的混合整數(shù)規(guī)劃模型，并采用結合優(yōu)先級調(diào)度規(guī)則和diagonal-fill空間調(diào)度方法的兩階段啟發(fā)式算法求解。但是上述文獻側(cè)重于分段的空間調(diào)度，未考慮分段的重入噴涂和時間約束。張志英等[3-4]研究了帶有時間和空間約束的分段涂裝重入調(diào)度問題。但假設所有分段只重入一次，且重入之間的干燥時間均相同。這很難滿足實際的分段涂裝調(diào)度要求。

Su[5]證明了帶有等待時間約束的兩階段單機調(diào)度過程是一個NP-Hard問題。顯然，帶有時間和空間約束的分段涂裝重入過程是一個更為復雜的NP-Hard問題。求解此類問題的常用方法為啟發(fā)式與元啟發(fā)式算法。前者可在合理時間內(nèi)求出較為滿意的解，但易陷入局部最優(yōu)解；后者通過亂數(shù)搜尋策略，提高了解的優(yōu)化能力, 但由于計算效率低而不能滿足復雜調(diào)度問題的需求。而超啟發(fā)式算法[6]結合了這兩者的優(yōu)勢，只需將底層算法修改便可在不同領域應用，因此近幾年在圖形著色[7]、課程表安排[8-9]等問題中得到了深入地研究。但在分段涂裝調(diào)度領域中的應用還很少見。

基于上述分析，本文針對分段涂裝作業(yè)重入調(diào)度問題，提出了以最小化最大完工時間為目標函數(shù)，帶有時間和空間約束的批-離散機重入調(diào)度模型。在此基礎上，構造基于重排策略的啟發(fā)式算法進行求解，得到優(yōu)化后的分段涂裝調(diào)度方案。

1　問題描述

分段涂裝作業(yè)重入調(diào)度過程如圖1所示：有m個沖砂車間，v個噴涂車間及r個噴涂隊。

圖1　分段涂裝作業(yè)重入調(diào)度過程Fig.1　Block-painting reentrant process

分段到達沖砂車間后，工人對砂房里的分段同時進行沖砂，每一個沖砂車間可等效為一臺并行批處理機。砂房中能放入的分段越多，沖砂效率越高。沖砂結束后的分段移至噴涂車間，由選定的噴涂隊在一定時間內(nèi)進行一度噴涂。分段至少要經(jīng)過2次噴涂才能結束加工，各度噴涂之間存在干燥時間下限約束。為了便于追溯和控制分段涂層的質(zhì)量，一個分段的各度噴涂作業(yè)均由同一支噴涂隊完成。分段噴涂作業(yè)要求在涂裝房內(nèi)完成，但由于船廠往往無法提供足夠的涂裝房。據(jù)IMO協(xié)會規(guī)范，除一度噴涂外，剩余噴涂作業(yè)可移至堆場完成。

2　模型建立

2.1模型假設

為研究方便，對分段涂裝作業(yè)重入調(diào)度問題，進行以下假設：1)分段的投影形狀為矩形。2)所有分段在初始時刻均可加工。3)各階段之間有足夠的緩存區(qū)；忽略分段進出各車間所需的搬運時間和其他生產(chǎn)準備時間。4)勞動力充足，不考慮罷工、缺勤等約束勞動力的情況。5)假定沖砂時間只與分段的投影面積有關，并事先確定。6)假定每個分段的各度噴涂時間相同，并事先確定。根據(jù)歷史數(shù)據(jù)，將檢查和報驗時間計入噴涂時間內(nèi)。7)同一分段在不同的溫度下干燥時間不同。為便于估算分段的干燥時間，假定所有分段在溫度25 ℃的環(huán)境下干燥。

2.2符號列表

2)參數(shù)：wti為分段i沖砂結束到一度噴涂之間的等待時間上限，h，i∈I；dtij為分段i第j道工序結束后的干燥時間下限，h，i∈I,j≥2；ptij為第i分段第j道工序的加工時間，h，i∈I，j∈J； si為分段i的投影面積，m2，i∈I； H為沖砂車間寬度，m；W為沖砂車間長度，m；sbf為第f個沖砂車間的面積，m2，f∈F；spl為第l個噴涂車間的面積，m2，l∈L；E為無窮大數(shù)。

2.3數(shù)學模型

模型的目標函數(shù)和約束條件如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

約束(2)規(guī)定每個分段的面積都小于沖砂車間的面積。約束(3)定義分段在放置過程中可正交旋轉(zhuǎn)。約束(4)表示各分段在擺放過程中互不重疊。約束(5)確保每個分段只能被分派到一個批中。約束(6)規(guī)定一個沖砂車間在同一時間至多加工一批分段。約束(7)確保每批分段的投影面積之和不超過沖砂車間的面積。約束(8)限定一個批次中的分段數(shù)不超過噴涂隊的數(shù)量，以保證沖砂后的分段，都能分派到不同的噴涂隊。約束(9)定義了分段實際沖砂時間為批中各分段單獨沖砂所需時間的最大值。約束(10)確保每批分段在沖砂過程中，一旦開始就不能中斷，直到完成沖砂作業(yè)。約束(11)和(12)分別定義了分段的沖砂開始時間和結束時間要求。約束(13)規(guī)定各噴涂車間內(nèi)的分段投影面積之和不能超過噴涂車間的面積。約束(14)確保一個噴涂隊在同一時間至多噴涂一個分段。約束(15)規(guī)定分段各度噴涂的加工時間相同。約束(16)保證噴涂階段，分段至少重入1次，且噴涂過程不能被中斷，由同一個噴涂隊完成作業(yè)。約束(17)表明分段一度噴涂必須在噴涂車間內(nèi)完成。約束(18)限定了分段沖砂后的等待時間不能超過相應的等待時間上限約束。約束(19)規(guī)定了分段重入之間的等待時間必須超過相應的干燥時間下限。約束(20)和(21)表明了分段在噴涂階段的加工順序要求。

3　基于重排策略的啟發(fā)式算法

圖2　基于重排策略的啟發(fā)式算法框圖(BRHA)Fig.2　Heuristic algorithm frame based on ranking strategy

3.1最大接觸策略

以沖砂車間左下角為坐標原點(0,0)，建立笛卡爾坐標系。其中，x、y分別為車間的長度和寬度方向。令第一個進入沖砂車間的分段左下角坐標(xi,yi)=(0,0)，后入分段置于其右方或上方。為便于確定分段的擺放位置，將已放置分段的右側(cè)輪廓線相連接的虛線稱為包絡線[13](圖3)，后入分段置于包絡線上。定義在包絡線上從垂直到水平的所有交點為可行位置P集合，如圖3中的位置1、2和3。由此得到后入分段的可行位置集合如式(22)，(x, y)為后入分段左下角的坐標。

(22)

考慮到包絡線越平滑，后入的分段越能充分地利用車間空間；因此，選擇分段與包絡線接觸最大的可行位置作為分段最終放入車間的位置。由于分段可正交旋轉(zhuǎn)，所以評判分段與包絡線接觸的量化函數(shù)PV(position value)如下所示：

(23)

圖3　可行位置S(p)Fig.3　Feasible position S(p)

圖4　基于最大接觸策略的PV函數(shù)示意圖 Fig.4　PV function based on the maximum contact strategy

3.2基于MRTS和GA的超啟發(fā)式算法

超啟發(fā)式算法的思想最早可追溯到1963年[14]，按規(guī)則生成機制分為選擇超啟發(fā)式和生成超啟發(fā)式算法。其中，選擇啟發(fā)式算法是將啟發(fā)式搜索規(guī)則進行選擇組合，對于求解復雜調(diào)度問題，比一般啟發(fā)式算法更具有優(yōu)勢。分段涂裝調(diào)度需將分段派給車間和噴涂隊，運用一種調(diào)度規(guī)則無法獲得合適的搜索空間，因此選用超啟發(fā)式算法通過不同調(diào)度規(guī)則的選擇組合，能得到更為合理的分段涂裝計劃。選擇超啟發(fā)式算法分為高層算法和底層規(guī)則。高層算法是采用元啟發(fā)式算法來選擇底層規(guī)則的搜索策略；底層規(guī)則為具體的調(diào)度方法。從均衡噴涂隊負荷的角度，研究確定了以下啟發(fā)式規(guī)則作為分段派遣到各個噴涂隊的方法。其中，RJk為t時噴涂隊k上待加工分段Oij的集合， p為分段當前待處理工序。

1)最大剩余加工時間規(guī)則(MRT)：剩余所需加工時間越大的分段，優(yōu)先安排加工，MRT的確定如式(24)。剩余加工時間相同的分段，選擇剩余重入次數(shù)最多的分段優(yōu)先加工。

(24)

2)最大重入次數(shù)規(guī)則(MRN)：分段剩余重入次數(shù)越多，越先加工，MRN的確定如式(25)。為了減少噴涂隊由于分段干燥造成的空閑狀態(tài)，當分段剩余重入次數(shù)相同時，選擇剩余加工時間大的分段，優(yōu)先噴涂。

(25)

3)最大平均加工時間規(guī)則(MPT)：分段的平均重入噴涂時間越大，越先加工，MPT的確定如下：

(26)

4)先到先加工規(guī)則(FIFS)：先到達噴涂隊的分段，優(yōu)先加工。

圖5　底層規(guī)則組合方案Fig.5　Bottom rule set

根據(jù)時間屬性的不同，噴涂隊加工待噴涂的分段分為待一度噴涂的分段和重入噴涂的分段。前者由于存在等待時間上限約束，所以一旦噴涂隊空閑，該分段將優(yōu)先加工。后者則存在干燥時間下限約束。為進一步確定重入噴涂分段在噴涂隊上的加工優(yōu)先級，引入MRTS策略：令Oi2加工優(yōu)先級為2；剩余加工時間最大的分段Oij優(yōu)先級為1，其余分段加工優(yōu)先級為0。若存在分段Oij既屬于一度噴涂，又擁有最大剩余加工時間，則其加工優(yōu)先級為2+1=3，依次類推；從而確定t時分段在噴涂隊k上的加工順序。綜上所述，采用目標函數(shù)作為適應度函數(shù)，得到基于MRTS策略和GA的超啟發(fā)式算法流程為：

4)執(zhí)行MRTS策略，按優(yōu)先級的高低加工分段，再用FIFO規(guī)則將分段分派給噴涂車間。計算各染色體的適應度函數(shù)，保存該代最佳染色體。

6)gener=gener+1；若gener

3.3BRHA算法框架

基于上述分析，得到求解分段涂裝重入調(diào)度問題的BRHA算法流程如下：

1)輸入起始溫度Ts，結束溫度Tf，冷卻率β。

2)初始化：執(zhí)行CACB算法、最大接觸策略、超啟發(fā)式算法得到分段空間分批結果Rβ，makespan和分段涂裝調(diào)度方案SS。

5)若Δ<0，則Rβ=R″β，SS=SS′，轉(zhuǎn)步驟7)。

7)T=β×T。若T>Tf，轉(zhuǎn)步驟3)。

4　實例驗證與數(shù)值分析

4.1實例驗證

為了驗證模型和BRHA算法的有效性，以上海某大型造船廠的涂裝車間為例，利用Matlab2013a軟件，在處理器為1.2 GHz，內(nèi)存為4 GB的計算機上進行求解。該造船廠有3個沖砂車間，4個噴涂車間和4個噴涂隊。分段在車間內(nèi)擺放時要留有一定的通道空間，因此取車間面積的60%作為有效面積。分段個數(shù)30，沖砂后的等待時間為1～4 h，干燥時間為12～24 h，部分分段的涂裝數(shù)據(jù)如表1所示，沖砂車間和噴涂車間的數(shù)據(jù)如表2所示。算法輸入?yún)?shù)：初始溫度Ts為運行10次BRHA所得平均最小完工時間的1.5倍，冷卻速率Ts=0.97，最終溫度Tf=0.1；種群規(guī)模為30，迭代次數(shù)為30，染色體交叉概率pc=0.9，變異概率pm=0.09。

運行程序，分段的空間分批結果如圖6所示，據(jù)此計算沖砂車間的平面利用率(表3)。分段第12批分批結束后，只有20號分段未分派至任何批中，所以第13批中只包含一個分段，車間的平面利用率比其他批低。從表3可得到車間的平均平面利用率為70.21%(不計第13批)。因此，BRHA算法得到的分段空間分批方案，能更好地利用沖砂車間的面積。

表1　部分分段涂裝數(shù)據(jù)

分段分派到噴涂隊時采用的調(diào)度規(guī)則如表4所示。當噴涂車間空間不足時，完成一度噴涂的分段必須搬到堆場。表5給出了分段離開噴涂車間的時間范圍。當分段最晚離開噴涂車間的時間為零時，表明該分段整個噴涂過程都在噴涂車間進行。分段的最終涂裝調(diào)度計劃如圖7所示。從圖7可得到分段涂裝作業(yè)最大完工時間為214.79 h。

表2　沖砂車間和噴涂車間數(shù)據(jù)

圖6　分段空間分批布置圖Fig.6　Blocks spatial batching

表3　沖砂車間平面利用率

4.2數(shù)值分析

分段涂裝重入調(diào)度過程需同時考慮車間和噴涂隊的分派，兼具時間和空間約束，比一般的調(diào)度問題復雜，難以找到合適的下界。因此，本文從超啟發(fā)式和整體算法兩個方面驗證算法的最優(yōu)性。為了驗證超啟發(fā)式算法的優(yōu)越性，選用HMRT、HMRN、HMPT、HFIFS這4個算法進行對比。這4個算法與BRHA算法的不同之處在于，前者分別選用調(diào)度規(guī)則中的一種完成分段到噴涂隊的派遣。引入相對偏差θ來表示算法所得目標值與相對最優(yōu)值的距離比值，θ越小，解的性能越好。θ由式(27)計算得到，refCmin表示對應算法所得的目標函數(shù)值。

(27)

在表6中，f2/l3/k4表示有2個沖砂車間，3個噴涂車間和4支噴涂隊，其他依次類推。從表6中可看出，BRHA算法解的平均相對偏差為0.1%，而對比算法的平均相對偏差在3%～17%。因此，在不同的問題模型和分段數(shù)量下，BRHA算法性能要明顯優(yōu)于HMRT、HMRN、HMPT和HFIFS算法。這充分說明了引入規(guī)則選擇的超啟發(fā)式算法可以很好地改善調(diào)度規(guī)則集合，進一步提升BRHA算法的性能。

此外，為了驗證BRHA整體算法的最優(yōu)性，增加了與文獻[4]HPSO算法的對比分析。在HPSO算法中，采用最大接觸和MRTS策略分別進行分段空間組批和噴涂隊上分段加工順序的確定。選取100個分段，噴涂車間和沖砂車間數(shù)據(jù)與實驗驗證部分一致。運行程序，算法的收斂曲線如圖8所示。

BRHA算法在130代左右趨于穩(wěn)定，得到分段涂裝結束時間為658 h；而HPSO算法在165代左右收斂，目標函數(shù)值為668 h。這表明了BRHA算法比HPSO算法提前收斂，并且得到的解更優(yōu)。因此，在求解帶有空間和時間約束的分段涂裝作業(yè)重入調(diào)度問題中，BRHA算法比HPSO算法更具有優(yōu)勢。

表4　分段噴涂派遣規(guī)則

表5　分段在噴涂車間內(nèi)的時間表

圖7　分段涂裝重入調(diào)度甘特圖Fig.7　Gantt chart of block-painting reentrant scheduling

表6　BRHA與HMRN，HMPT，HFIFS的對比

圖8　BRHA與HPSO算法收斂曲線Fig.8　BRHA and HPSO algorithm convergence curves

5　結論

本文研究了船舶分段涂裝作業(yè)的重入調(diào)度問題，得出以下結論：

1)綜合考慮分段干燥時間，重入時間及沖砂車間的平面約束，確定以最小化最大完工時間作為評價調(diào)度方案的評價指標；

2)提出了基于重排策略的啟發(fā)式算法來優(yōu)化分段調(diào)度方案；

3)通過不同分段數(shù)量、車間規(guī)模以及與其他算法的對比實驗分析，證明該算法可以提高分段涂裝作業(yè)效率，同時可為船廠制定車間級分段涂裝調(diào)度方案提供有效的依據(jù)。但是本文未考慮露天堆場的空間約束。如果涂裝作業(yè)的分段太多，在有限的場地和作業(yè)時間里，可能無法安排指定的工作計劃，需進一步研究。

[1]CHO K K, CHUNG K H, PARK C, et al. A spatial scheduling system for block painting process in shipbuilding[J]. CIRP annals-manufacturing technology, 2001, 50(1): 339-342.

[2]KWON B, LEE G M. Spatial scheduling for large assembly blocks in shipbuilding[J]. Computers & industrial engineering, 2015, 89: 203-212.

[3]張志英, 林晨, 楊連生, 等. 面向分段涂裝作業(yè)的混合流水車

間調(diào)度[J]. 上海交通大學學報, 2014, 48(3): 382-387, 393.

ZHANG Zhiying, LIN Chen, YANG Liansheng, et al. Block-painting-operation-oriented hybrid flow shop scheduling[J]. Journal of Shanghai JiaoTong University, 2014, 48(3): 382-387, 393.

[4]林晨, 張志英. 考慮運輸時間窗的批-離散混合流水車間調(diào)度[J]. 計算機集成制造系統(tǒng), 2014, 21(9): 2427-2434.

LIN Chen, ZHANG Zhiying. Batch-discrete hybrid flow shop scheduling with transportation in time windows[J]. Computer integrated manufacturing systems, 2014, 21(9): 2427-2434.

[5]SU L H. A hybrid two-stage flowshop with limited waiting time constraints[J]. Computers & industrial engineering, 2003, 44(3): 409-424.

[6]BURKE E K, GENDREAU M, HYDE M, et al. Hyper-heuristics: a survey of the state of the art[J]. Journal of the operational research society, 2013, 64(12): 1695-1724.

[7]ELHAG A, ?ZCAN E. A grouping hyper-heuristic framework: application on graph colouring[J]. Expert systems with applications, 2015, 42(13): 5491-5507.

[8]KALENDER M, KHEIRI A, ?ZCAN E, et al. A greedy gradient-simulated annealing selection hyper-heuristic[J]. Soft computing, 2013, 17(12): 2279-2292.

[9]AHMED L N, ?ZCAN E, KHEIRI A. Solving high school timetabling problems worldwide using selection hyper-heuristics[J]. Expert systems with applications, 2015, 42(13): 5463-5471.

[11]CHEN Huaping, DU Bing, HUANG G Q. Scheduling a batch processing machine with non-identical job sizes: a clustering perspective[J]. International journal of production research, 2011, 49(19): 5755-5778.

[12]LIN T L, HORNG S J, KAO T W, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization[J]. Expert systems with applications, 2010, 37(3): 2629-2636.

[13]WEI Lijun, ZHANG Defu, CHEN Qingshan. A least wasted first heuristic algorithm for the rectangular packing problem[J]. Computers & operations research, 2009, 36(5): 1608-1614.

[14]FISHER H, THOMPSON G L. Probabilistic learning combinations of local job-shop scheduling rules[C]//MUTH J F, THOMPSON G L. Industrial Scheduling. Englewood Cliffs, New Jersey: Prentice Hall, 1963: 225-251.

本文引用格式：

陳云云，張志英. 船舶分段涂裝作業(yè)重入調(diào)度優(yōu)化算法[J]. 哈爾濱工程大學學報, 2016, 37(8): 1103-1110.

CHEN Yunyun，ZHANG Zhiying. Optimization algorithm for reentrant scheduling in block painting operations[J]. Journal of Harbin Engineering University, 2016, 37(8): 1103-1110.

Optimization algorithm for reentrant scheduling in block painting operations

CHEN Yunyun，ZHANG Zhiying

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

To solve the problems associated with block painting operations, such as low efficiency and long painting time, in this study, we abstracted the reentrant process of batch-discrete machines with respect to time and spatial constraints. We also established a mathematical model to minimize the maximum makespan and proposed a heuristic algorithm based on ranking strategy. Specifically, we developed a clustering algorithm, batch-ranking strategy based on simulated annealing to obtain a block-batching result without considering spatial constraints. Then, we formulated a maximum contact strategy to achieve block spatial-batch scheduling. We addressed block reentrant scheduling using a hyper-heuristic algorithm that integrates the strategy of maximum remaining processing time with a genetic algorithm. Our simulation results indicate that the proposed algorithms can make full use of the blasting workshop and are effective in resolving the block-painting reentrant problem.

block painting; painting operation; time constraint; spatial constraint; reentrant scheduling; heuristic algorithm; clustering algorithm; optimization algorithm

2016-01-03.網(wǎng)絡出版日期：2016-06-24.

國家自然科學基金項目(70872076);上海市科技創(chuàng)新行動計劃(11dz1121803).

陳云云(1992- )，女，碩士研究生;

張志英(1971- )，男，副教授.

張志英，E-mail：zyzhang08@#edu.cn.

10.11990/jheu.201601002

TP301.6

A

1006-7043(2016)08-1103-08