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

陳云云，張志英

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

?

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

陳云云，張志英

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

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

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

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

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

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

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

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

1　問題描述

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

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

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

2　模型建立

2.1模型假設(shè)

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

2.2符號(hào)列表

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

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

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

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

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

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

3.1最大接觸策略

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

(22)

考慮到包絡(luò)線越平滑，后入的分段越能充分地利用車間空間；因此，選擇分段與包絡(luò)線接觸最大的可行位置作為分段最終放入車間的位置。由于分段可正交旋轉(zhuǎn)，所以評(píng)判分段與包絡(luò)線接觸的量化函數(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ī)則生成機(jī)制分為選擇超啟發(fā)式和生成超啟發(fā)式算法。其中，選擇啟發(fā)式算法是將啟發(fā)式搜索規(guī)則進(jìn)行選擇組合，對(duì)于求解復(fù)雜調(diào)度問題，比一般啟發(fā)式算法更具有優(yōu)勢。分段涂裝調(diào)度需將分段派給車間和噴涂隊(duì)，運(yùn)用一種調(diào)度規(guī)則無法獲得合適的搜索空間，因此選用超啟發(fā)式算法通過不同調(diào)度規(guī)則的選擇組合，能得到更為合理的分段涂裝計(jì)劃。選擇超啟發(fā)式算法分為高層算法和底層規(guī)則。高層算法是采用元啟發(fā)式算法來選擇底層規(guī)則的搜索策略；底層規(guī)則為具體的調(diào)度方法。從均衡噴涂隊(duì)負(fù)荷的角度，研究確定了以下啟發(fā)式規(guī)則作為分段派遣到各個(gè)噴涂隊(duì)的方法。其中，RJk為t時(shí)噴涂隊(duì)k上待加工分段Oij的集合， p為分段當(dāng)前待處理工序。

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

(24)

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

(25)

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

(26)

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

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

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

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

6)gener=gener+1；若gener

3.3BRHA算法框架

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

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

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

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

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

4　實(shí)例驗(yàn)證與數(shù)值分析

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

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

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

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

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

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

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

表3　沖砂車間平面利用率

4.2數(shù)值分析

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

(27)

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

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

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

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

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

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

表6　BRHA與HMRN，HMPT，HFIFS的對(duì)比

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

5　結(jié)論

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

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

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

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

[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]. 上海交通大學(xué)學(xué)報(bào), 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]林晨, 張志英. 考慮運(yùn)輸時(shí)間窗的批-離散混合流水車間調(diào)度[J]. 計(jì)算機(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]. 哈爾濱工程大學(xué)學(xué)報(bào), 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)絡(luò)出版日期：2016-06-24.

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

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

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

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

10.11990/jheu.201601002

TP301.6

A

1006-7043(2016)08-1103-08