趙博選,高建民,陳琨

(西安交通大學(xué)機(jī)械工程學(xué)院,710049,西安)

?

求解多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題的兩階段混合Pareto蟻群算法

趙博選,高建民,陳琨

(西安交通大學(xué)機(jī)械工程學(xué)院,710049,西安)

針對(duì)多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題(FJSP)分解得到的作業(yè)分派、排序子問(wèn)題仍是多目標(biāo)優(yōu)化問(wèn)題的情況,提出了一種求解該問(wèn)題的分層Pareto優(yōu)化框架,并采用該框架構(gòu)建了兩階段混合Pareto蟻群算法的求解算法,其中兩個(gè)Pareto蟻群系統(tǒng)分別求解多目標(biāo)作業(yè)分派、排序問(wèn)題。結(jié)合GT算法、排產(chǎn)規(guī)則評(píng)估和過(guò)濾第一階段的分派方案,將具有較好評(píng)估全局解的分派方案作為分派階段的精英檔案,并輸入給排序蟻群系統(tǒng)獲取其非支配調(diào)度解,進(jìn)而獲取問(wèn)題全局非支配解。子問(wèn)題算法混合了各目標(biāo)相關(guān)的鄰域搜索策略,與Pareto蟻群算法結(jié)合,以期提高解的質(zhì)量。通過(guò)求解帶有平均工件加權(quán)延遲時(shí)間指標(biāo)的多個(gè)FJSP基準(zhǔn)算例,驗(yàn)證了算法的有效性。計(jì)算結(jié)果表明,該分層Pareto優(yōu)化框架對(duì)原問(wèn)題進(jìn)行分層分解,有利于降低原問(wèn)題的復(fù)雜性,相比多數(shù)文獻(xiàn),算法能夠獲得各基準(zhǔn)算例Pareto非支配解,從而為分解求解復(fù)雜多目標(biāo)調(diào)度優(yōu)化問(wèn)題提供了一種途徑。

多目標(biāo)柔性作業(yè)車(chē)間調(diào)度;分層Pareto優(yōu)化;兩階段Pareto蟻群算法;鄰域搜索

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(FJSP)是傳統(tǒng)作業(yè)車(chē)間調(diào)度問(wèn)題的擴(kuò)展。在柔性作業(yè)車(chē)間調(diào)度問(wèn)題中,每道工序的加工設(shè)備是不確定的。工件可以在多個(gè)可選擇設(shè)備上加工,采用不同加工設(shè)備所需加工時(shí)間不同,且工件可能重復(fù)訪(fǎng)問(wèn)同一設(shè)備,設(shè)備不確定性和可重復(fù)訪(fǎng)問(wèn)性增加了FJSP調(diào)度優(yōu)化的復(fù)雜性,使FJSP成為更加復(fù)雜的NP-hard問(wèn)題。FJSP包含作業(yè)分派(OA)與排序(OS)兩部分內(nèi)容,其求解方法可分為集成求解和分層求解,集成求解同時(shí)考慮OA與OS的優(yōu)化[1-4],分層求解根據(jù)兩子問(wèn)題的繼承性分階段優(yōu)化,進(jìn)而得到問(wèn)題全局解,降低了問(wèn)題復(fù)雜性[5-7]。

多目標(biāo)FJSP求解方法分為加權(quán)和優(yōu)化及Pareto優(yōu)化兩類(lèi)。加權(quán)和優(yōu)化采用已知權(quán)重將多目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化[6-8],Pareto優(yōu)化基于Pareto最優(yōu)的思想獲取問(wèn)題解空間多樣化、近優(yōu)性的非支配前沿[9-10]。加權(quán)和優(yōu)化可在各目標(biāo)權(quán)重已知的情況快速得到問(wèn)題部分解,但大多數(shù)車(chē)間生產(chǎn)內(nèi)外部環(huán)境動(dòng)態(tài)變化,Pareto優(yōu)化為生產(chǎn)管理者提供數(shù)量較多的調(diào)度方案以供決策。

按照問(wèn)題分解求解的思想,原問(wèn)題被分解之后,子問(wèn)題圍繞與之相關(guān)的目標(biāo)子集優(yōu)化。例如,多目標(biāo)FJSP分解之后的OA子問(wèn)題根據(jù)問(wèn)題本身性質(zhì),其目標(biāo)子集包含總負(fù)荷與負(fù)荷均衡度等相關(guān)指標(biāo),而OS子問(wèn)題目標(biāo)子集包含完工周期與交付性相關(guān)指標(biāo),故多目標(biāo)FJSP分解之后得到兩個(gè)多目標(biāo)優(yōu)化子問(wèn)題。當(dāng)分層求解方法面對(duì)兩階段均屬于多目標(biāo)優(yōu)化問(wèn)題時(shí),除構(gòu)建子問(wèn)題求解算法外,如何選取前者解集進(jìn)入后者求解算法是該問(wèn)題的關(guān)鍵。分層加權(quán)和求解方法可采用加權(quán)和方式對(duì)前者結(jié)果進(jìn)行評(píng)估,選擇最優(yōu)結(jié)果進(jìn)入后者,但分層Pareto求解方法卻不能簡(jiǎn)單將前者非支配解集提交給后者求解算法。

本文結(jié)合分層求解和Pareto優(yōu)化方法,研究求解多目標(biāo)FJSP的分層Pareto求解方法,構(gòu)建兩階段混合Pareto蟻群算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題。Pareto蟻群算法混合各目標(biāo)相關(guān)的鄰域搜索算法,實(shí)現(xiàn)二者協(xié)同進(jìn)化。

1 FJSP描述

記J={Ji,1≤i≤n}為調(diào)度工件集合,工件序號(hào)為i;每個(gè)工件Ji包含ni道工序,工序順序預(yù)先確定,工件Ji的第j道工序可以表示為Oij;工件具有不同的權(quán)重系數(shù)ωi和交貨期di。記M={Mk,1≤k≤m}為加工設(shè)備集合,設(shè)備序號(hào)為k;可以加工工序Oij的設(shè)備集合為Mij?M,工序Oij在Mk上加工,不可中斷,且加工時(shí)間為tijk。

要求為每個(gè)工件的工序選擇合適的加工設(shè)備并確定各設(shè)備上的工序加工順序及開(kāi)始加工時(shí)間,同時(shí)滿(mǎn)足各工件的加工工藝等約束條件,實(shí)現(xiàn)多個(gè)調(diào)度性能指標(biāo)最優(yōu)。

考慮最大完工時(shí)間最小、總負(fù)荷最小、最大設(shè)備負(fù)荷最小和平均工件加權(quán)延遲時(shí)間最小4種性能指標(biāo),即

(1)

(2)

(3)

(4)

決策變量

(5)

(6)

約束條件

(7)

?1≤i≤n, 1≤j≤ni, 1≤i′≤n, 1≤j′≤n,

(8)

(9)

(10)

2 一種兩階段Pareto優(yōu)化算法框架

由于設(shè)備的非等效性、工藝的多樣性以及設(shè)備可重入性,FJSP分解之后的OA與OS子問(wèn)題兩者解空間的非支配性不具備繼承性,即OA子問(wèn)題的非支配前沿分派解經(jīng)過(guò)OS子問(wèn)題優(yōu)化后不一定是OS子問(wèn)題的非支配前沿調(diào)度解,且OS子問(wèn)題的非支配前沿調(diào)度解不一定是由OA子問(wèn)題的非支配前沿分派解得來(lái),所以不能簡(jiǎn)單保留OA子問(wèn)題的非支配前沿解作為第1階段的優(yōu)化結(jié)果。分層求解方法需要對(duì)前者子問(wèn)題的求解結(jié)果進(jìn)行評(píng)估和優(yōu)選,一方面盡可能過(guò)濾較差分派解進(jìn)入第2階段,另一方面不能丟失問(wèn)題最優(yōu)解對(duì)應(yīng)的分派解。采用啟發(fā)式規(guī)則排產(chǎn)算法快速構(gòu)建分派方案的優(yōu)秀調(diào)度解,得到分派解的全局目標(biāo)值參與評(píng)估和優(yōu)選,最終選擇評(píng)估后具有較優(yōu)全局目標(biāo)值的分派解作為第1階段的優(yōu)化結(jié)果。

通過(guò)大量仿真實(shí)驗(yàn)提出分層Pareto優(yōu)化算法框架前,總結(jié)2個(gè)改進(jìn)措施:①子問(wèn)題1優(yōu)化一定次數(shù)后,使其較優(yōu)解處于較穩(wěn)定時(shí)才進(jìn)行評(píng)估和優(yōu)選,有利于降低評(píng)估與優(yōu)選操作運(yùn)行次數(shù),根據(jù)非支配關(guān)系,子問(wèn)題1的非支配解集一定是問(wèn)題全局解(所有目標(biāo)集合)的非支配解集;②評(píng)估和優(yōu)選之后的較優(yōu)解暫時(shí)保留在第1階段精英檔案中,每次評(píng)估和優(yōu)選之后更新該精英檔案,等第1階段優(yōu)化完畢后,將該精英檔案輸出給第2階段進(jìn)行搜索。這樣可大量過(guò)濾算法運(yùn)行過(guò)程中的較差分派解,且將兩子問(wèn)題之間的嵌套關(guān)系改成并列關(guān)系,有利于減少算法運(yùn)行時(shí)間。求解多目標(biāo)FJSP的分層Pareto優(yōu)化算法框架如圖1所示。

圖1 分層Pareto優(yōu)化算法框架

3 兩階段混合Pareto蟻群算法

3.1 FJSP析取圖描述

為了應(yīng)用蟻群算法,FJSP問(wèn)題用析取圖表示為D=(O,A,B),其中O為節(jié)點(diǎn)集合,A為連接弧集合,B為析取弧集合。開(kāi)始節(jié)點(diǎn)OS和結(jié)束節(jié)點(diǎn)OE分別用于連接各工件的首尾工序;有向弧表示各工件的工藝路線(xiàn),連接具有順序約束的工序節(jié)點(diǎn);析取弧表示不同工件之間可能工序的順序關(guān)系,以待確定;同一工序的不同可選設(shè)備節(jié)點(diǎn)之間不存在析取弧。與JSSP問(wèn)題不同的是,該析取圖將可選設(shè)備添加在工序節(jié)點(diǎn)中,且不是所有的節(jié)點(diǎn)都要被遍歷,調(diào)度結(jié)果只是所有節(jié)點(diǎn)的部分連接圖。同一工序的設(shè)備節(jié)點(diǎn)具有互斥關(guān)系,當(dāng)某工序節(jié)點(diǎn)的加工設(shè)備確定,該工序的其他設(shè)備節(jié)點(diǎn)即被舍棄。每個(gè)節(jié)點(diǎn)被表述為(Oi,j,Mk),表示工件的第j道工序在設(shè)備k上加工,4個(gè)工件的析取圖描述如圖2所示。多目標(biāo)蟻群算法會(huì)得到多個(gè)加工路徑,這些加工路徑對(duì)應(yīng)的解在解空間具有非支配性。

圖2 FJSP問(wèn)題析取圖描述示例

3.2 兩階段混合Pareto蟻群系統(tǒng)構(gòu)建

詳細(xì)的Pareto蟻群算法關(guān)鍵操作可參考文獻(xiàn)[11-12]。OA蟻群系統(tǒng)根據(jù)信息素與啟發(fā)式信息確定各工序操作的加工設(shè)備,每只螞蟻遍歷路徑前隨機(jī)排列所有工序,并保證工藝可行性,如圖3所示。

圖3 父代蟻群系統(tǒng)搜索示例

給定x為工序總數(shù),y為設(shè)備總數(shù),信息素矩陣構(gòu)建為[τv,k]x×y,工序設(shè)備節(jié)點(diǎn)總負(fù)荷相關(guān)啟發(fā)式信息為其加工時(shí)間的倒數(shù),工序設(shè)備節(jié)點(diǎn)負(fù)荷偏差相關(guān)啟發(fā)式信息為該設(shè)備已分配負(fù)荷的倒數(shù)。為使分母不為0,預(yù)先給每個(gè)設(shè)備預(yù)設(shè)合適的已分配負(fù)荷初始值。

圖5 基于關(guān)鍵路徑及公共關(guān)鍵塊的完工周期相關(guān)鄰域搜索操作示意圖

如圖4所示,OS蟻群系統(tǒng)通過(guò)遍歷所有工序操作節(jié)點(diǎn)來(lái)構(gòu)建分派方案調(diào)度解,考慮到優(yōu)化目標(biāo)的正則性,本文結(jié)合GT算法[10]來(lái)縮小搜索范圍,減少算法搜索時(shí)間。具體流程為:①添加各工件首工序至可選工序任務(wù)集合,并計(jì)算集合中各工序操作最早可能開(kāi)工與完工時(shí)間;②找出任務(wù)集合中工序操作最早可能完工時(shí)間和分派設(shè)備;③找出任務(wù)集合中分派在設(shè)備上最早可能開(kāi)工時(shí)間小于完工時(shí)間的工序操作,形成沖突工序操作集合;④根據(jù)蟻群?jiǎn)l(fā)式策略從操作集合中選擇一個(gè)工序安排,從任務(wù)集合中剔除該工序,如果該工序不是工件末工序,添加其下一工序操作至任務(wù)集合;⑤更新任務(wù)集合中受影響工序操作最早可能開(kāi)工與完工時(shí)間,如果任務(wù)集合為空,停止,否則返回至流程②。

圖4 OS蟻群系統(tǒng)搜索示例

完工周期相關(guān)啟發(fā)式信息為該弧段后工序任務(wù)加工時(shí)間的倒數(shù);交付性相關(guān)啟發(fā)式信息為該弧段后工序任務(wù)分解交付期的倒數(shù)。計(jì)算各工件工序操作的分解交付期,即

(11)

3.3 鄰域搜索策略

單目標(biāo)優(yōu)化問(wèn)題中,當(dāng)鄰域搜索解較優(yōu)時(shí)代替初始解,而在多目標(biāo)優(yōu)化問(wèn)題中,若鄰域搜索得到的解與原先解比較具有非支配性時(shí),將該鄰域搜索解保存于緩沖池中。當(dāng)所有鄰域搜索執(zhí)行完畢后,從緩沖池取出非支配解,更新原始檔案。由于各目標(biāo)的互斥性,本文提出與各目標(biāo)相關(guān)的鄰域搜索策略,每次鄰域搜索以期某個(gè)目標(biāo)相比之前更優(yōu),鄰域搜索策略如下。

(1)總負(fù)荷目標(biāo)相關(guān)的鄰域搜索。找到分派工序數(shù)目最多的設(shè)備,隨機(jī)選擇該設(shè)備上某一工序,改派至其他較小加工時(shí)間可選設(shè)備上。

(2)最大設(shè)備負(fù)荷目標(biāo)相關(guān)的鄰域搜索。按照已分派負(fù)荷對(duì)設(shè)備排序,隨機(jī)選擇最大負(fù)荷設(shè)備上工序操作分派在其他較小負(fù)荷可選設(shè)備上。

(3)完工周期目標(biāo)相關(guān)的鄰域搜索。要想縮短完工周期,鄰域搜索只有通過(guò)移動(dòng)關(guān)鍵路徑上的工序才可能減少最大完工時(shí)間,而當(dāng)調(diào)度方案含有多條關(guān)鍵路徑時(shí),只有基于公共關(guān)鍵塊的鄰域結(jié)構(gòu)才會(huì)有助于縮短完工周期。本文基于公共關(guān)鍵塊采用以下鄰域結(jié)構(gòu):塊首工序插入到塊內(nèi)工序之后;塊尾工序插入到塊內(nèi)工序之前;塊內(nèi)工序插入到塊首之前;塊內(nèi)工序插入到塊內(nèi)之后;塊首或塊尾兩工序交換。圖5歸納了基于關(guān)鍵路徑及公共關(guān)鍵塊的完工周期相關(guān)鄰域搜索策略所包含的操作。

(4)加權(quán)延遲時(shí)間相關(guān)鄰域搜索。文獻(xiàn)[4]介紹了一種交換式交付期相關(guān)鄰域搜索策略,先比較工件完工時(shí)間與交貨期,將其分為提前類(lèi)和延遲類(lèi),逐個(gè)設(shè)備尋找相鄰工序滿(mǎn)足前工序?qū)儆谔崆邦?lèi)、后工序?qū)儆谘舆t類(lèi)的兩相鄰工序,然后交換它們。

3.4 兩階段混合Pareto蟻群算法流程

在OA、OS Pareto蟻群系統(tǒng)中,每次迭代得到的所有螞蟻解經(jīng)歷了新信息素矩陣和隨機(jī)權(quán)重的引導(dǎo),新的螞蟻解對(duì)檔案的補(bǔ)充增加了檔案解的多樣性,而鄰域搜索可進(jìn)一步提高解的質(zhì)量。在OS蟻群系統(tǒng)中對(duì)精英檔案EA_OS進(jìn)行鄰域搜索,而在OA蟻群系統(tǒng)中對(duì)所有螞蟻新解和精英檔案EA_OA進(jìn)行鄰域搜索,用所有新解更新EA_OA和最優(yōu)新分派解檔案Best_OA_New,Best_OA_New為多次迭代之后需要評(píng)估的分派解檔案。

本文采用算法迭代達(dá)到預(yù)定最大次數(shù)、非支配解集不再變化達(dá)到預(yù)定次數(shù)兩種算法為終止條件,算法詳細(xì)流程如圖6、7所示。

圖6 OA蟻群系統(tǒng)算法流程

3.5 OA分派解評(píng)估與優(yōu)選

本文結(jié)合GT算法與多種排產(chǎn)規(guī)則為分派解構(gòu)建可行調(diào)度方案,評(píng)估完工周期與平均加權(quán)延遲時(shí)間指標(biāo)。排產(chǎn)規(guī)則包括隨機(jī)選擇規(guī)則,最早完工時(shí)間優(yōu)先,最早操作分解交貨期優(yōu)先,最多工作量剩余優(yōu)先,最多操作數(shù)目剩余優(yōu)先。按照事先設(shè)計(jì)好的概率分配,選取排產(chǎn)規(guī)則確定GT算法中沖突工序順序,得到該分派方案的調(diào)度解參與評(píng)估,當(dāng)出現(xiàn)多種可選狀況時(shí)采用隨機(jī)選擇規(guī)則輔助選擇。對(duì)各個(gè)新分派解按照以上方法構(gòu)建多個(gè)可行調(diào)度解(本文設(shè)定為30),與分派解子目標(biāo)集聯(lián)合,并添加至分派解全局精英檔案gEA_OA,根據(jù)支配關(guān)系從gEA_OA中保留一定數(shù)量較優(yōu)分派方案,實(shí)現(xiàn)gEA_OA檔案更新,在該檔案中一個(gè)分派解可能對(duì)應(yīng)多個(gè)非支配全局精英解。

4 算例分析

為證實(shí)算法的有效性,本文應(yīng)用該算法求解了帶有平均加權(quán)延遲時(shí)間指標(biāo)的多組基準(zhǔn)算例,分別為Kacem8×8算例、10×7算例、10×10算例和15×10算例,工件交付期信息如表1所示,其中時(shí)間為無(wú)量綱單位時(shí)間。算法參數(shù):前3個(gè)算例螞蟻數(shù)目P=20,螞蟻信息素初值τ0=1;15×10算例螞蟻數(shù)目P=30,τ0=0.1,揮發(fā)系數(shù)ξ=0.1,全局釋放系數(shù)ρ=0.1,信息素權(quán)重因子α=1,啟發(fā)性知識(shí)權(quán)重因子β=1,偽隨機(jī)概率q0=0.6。仿真實(shí)驗(yàn)表明,該參數(shù)組合能使兩階段Pareto蟻群算法在禁用鄰域搜索操作時(shí)得到較好質(zhì)量的問(wèn)題解集。

圖7 OS蟻群系統(tǒng)算法

分派階段的全局精英檔案gEA_OA的規(guī)模會(huì)影響算法整體運(yùn)行時(shí)間。根據(jù)試驗(yàn)數(shù)據(jù),問(wèn)題Pareto非支配前沿對(duì)應(yīng)的分派解主要屬于分派解全局精英檔案gEA_OA的前幾個(gè)非支配等級(jí),說(shuō)明了評(píng)估和優(yōu)選的有效性,根據(jù)該特征、結(jié)合問(wèn)題規(guī)模,可控制該檔案的規(guī)模。本文前3個(gè)算例設(shè)置的gEA_OA檔案規(guī)模為30,15×10算例設(shè)置的gEA_OA檔案規(guī)模為40。按照以上設(shè)置,將算法運(yùn)行10次,對(duì)各算例的運(yùn)行時(shí)間(均值/方差)分別為152/28.3,162/23.7,168/31.2,445/34.8 s。編程語(yǔ)言為Matlab2010,運(yùn)行環(huán)境為CPU i3-2120,主頻為-3.30～3.30 GHz,內(nèi)存為4 GB。表2給出了附加平均工件加權(quán)延遲時(shí)間指標(biāo)的Pareto最優(yōu)解,粗體字符表示從文獻(xiàn)[3-4,6-10]獲取的Pareto非支配解。

5 結(jié) 論

多目標(biāo)問(wèn)題分解得到的子問(wèn)題往往也是多目標(biāo)優(yōu)化問(wèn)題,本文嘗試求解多目標(biāo)FJSP的兩階段Pareto優(yōu)化方法,構(gòu)建了兩階段混合Pareto蟻群算法,Pareto蟻群系統(tǒng)分別求解多目標(biāo)作業(yè)分派和排序問(wèn)題。評(píng)估操作快速對(duì)分派解進(jìn)行評(píng)估,并保留具有較好評(píng)估全局解的分派方案作為分派問(wèn)題的精英檔案,將精英檔案輸入給排序蟻群系統(tǒng)以獲取非支配調(diào)度解,最終獲取問(wèn)題全局非支配前沿。子問(wèn)題算法混合了與各目標(biāo)相關(guān)的鄰域搜索策略,以提高問(wèn)題解的質(zhì)量。通過(guò)求解多個(gè)基準(zhǔn)算例,算法可以獲取現(xiàn)有文獻(xiàn)各算例給出的非支配解,從而驗(yàn)證了該求解方法的有效性。本文為多目標(biāo)優(yōu)化問(wèn)題的分層Pareto優(yōu)化方法提供了一種途徑,未來(lái)將繼續(xù)改進(jìn)算法,并嘗試應(yīng)用該算法求解實(shí)際調(diào)度問(wèn)題。

表1 工件交付期

表2 附加平均工件加權(quán)延遲時(shí)間的部分Pareto最優(yōu)解

[1] 莫建麟, 吳喆. 基于混合遺傳禁忌的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度 [J]. 重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 30(2): 87-91. MO Jianlin, WU Zhe. Multi-objective flexible job shop scheduling based on hybrid genetic & tabu algorithm [J]. Journal of Chongqing Normal University (Natural Science), 2013, 30(2): 87-91.

[2] 張超勇, 董星, 王曉娟, 等. 基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度 [J]. 機(jī)械工程學(xué)報(bào), 2010, 46(11): 156-164. ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-II for the multi-objective flexible job-shop scheduling problem [J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164.

[3] MOSLEHI G, MAHNAM M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search [J]. International Journal of Production Economics, 2011, 129(1): 14-22.

[4] GAO K Z, SUGANTHAN P N, PAN Q K. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling [J]. Information Sciences, 2014, 289(1): 76-79.

[5] 張潔, 張朋, 劉國(guó)寶. 基于兩階段蟻群算法的帶非等效并行機(jī)的作業(yè)車(chē)間調(diào)度 [J]. 機(jī)械工程學(xué)報(bào), 2013, 49(6): 136-144. ZHANG Jie, ZHANG Peng, LIU Guobao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines [J]. Journal of Mechanical Engineering, 2013, 49(6): 136-144.

[6] XING Lining, CHEN Yingwu. An efficient search method for multi-objective flexible job shop scheduling problems [J]. Journal of Intelligent Manufacturing, 2009, 20(3): 283-293.

[7] XING Lining, CHEN Yingwu. Multi-objective flexible job shop schedule: design and evaluation by simulation modeling [J]. Applied Soft Computing, 2009, 9(1): 362-376.

[8] XIA Weijun, WU Zhiming. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems [J]. Computers & Industrial Engineering, 2005, 48(2): 409-425.

[9] LI Junqing, PAN Q, LIANG Y C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems [J]. Computers & Industrial Engineering, 2010, 59(4): 647-662.

[10]CHIANG T C, LIN H J. A simple and effective evolutionary algorithm for multi-objective flexible job shop scheduling [J]. International Journal of Production Economics, 2013, 141(1): 87-98.

[11]GARCIA-MARTINEZ C, CORDON O, HERRERA F. A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP [J]. European Journal of Operational Research, 2007, 180(1): 116-148.

[12]DOERNER K, GUTJAHR W J. Pareto ant colony optimization: a meta-heuristic approach to multi-objective portfolio selection [J]. Annals of Operations Research, 2004, 131(1): 79-99.

[本刊相關(guān)文獻(xiàn)鏈接]

劉岳鐳,馮祖仁,任曉棟.具有惡化效應(yīng)的雙代理單機(jī)最優(yōu)調(diào)度算法.2016,50(6):9-14.[doi:10.7652/xjtuxb201606002]

陳鵬飛,李昕怡,齊勇,等.單步啟發(fā)式策略的備份虛擬機(jī)復(fù)用策略.2016,50(1):100-107.[doi:10.7652/xjtuxb201601 016]

楊鵬飛,王泉.片上網(wǎng)絡(luò)異構(gòu)多核系統(tǒng)任務(wù)調(diào)度與映射.2015,49(6):72-76.[doi:10.7652/xjtuxb201506012]

王麗霞,曲樺,趙季紅,等.軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略.2015,49(6):67-71.[doi:10.7652/xjtuxb201506011]

周光輝,苗發(fā)祥,李彥廣.數(shù)控加工中心任務(wù)與刀具集成調(diào)度模型及改進(jìn)自適應(yīng)遺傳算法.2014,48(12):1-7.[doi:10.7652/xjtuxb201412001]

邵成成,王錫凡,王秀麗,等.主動(dòng)配電系統(tǒng)與主網(wǎng)的有功協(xié)調(diào).2014,48(11):58-63.[doi:10.7652/xjtuxb201411010]

李彬,宋立明,李軍,等.長(zhǎng)葉片透平級(jí)多學(xué)科多目標(biāo)優(yōu)化設(shè)計(jì).2014,48(1):1-6.[doi:10.7652/xjtuxb201401001]

(編輯 趙煒 杜秀杰)

Two-Stage Hybrid Pareto Ant Colony Algorithm for Multi-Objective Flexible Job Shop Scheduling

ZHAO Boxuan,GAO Jianmin,CHEN Kun

(School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Multi-objective flexible job shop scheduling can be divided into two sub-problems, namely job assignment and sorting, which are often multi-objective optimization problems. Aiming at this situation, this paper presents a layered Pareto optimization frame for multi-objective flexible job shop problem and proposes a two-stage hybrid Pareto ant colony algorithm for multi-objective operation assignment (OA) and operation sequencing (OS) sub-problems. Embedding multiple scheduling rules in GT algorithm is used to evaluate and filter the assignment solutions. The global optimal non-dominated front of the original problem is obtained by scheduling optimization as the elite archive of assignments. Each Pareto ant colony algorithm is combined with the neighborhood search strategies related to different objectives. The co-evolutionary can obtain high-quality solutions to multi-objective FJSP. Finally, by solving four benchmark instances considering minimizing the mean weighted tardiness time, the effectiveness of the method is testified. The simulation results show that the layered Pareto optimization frame helps to reduce complexity of the problem, and compared with other literatures, the proposed algorithm can obtain the Pareto non-dominant solutions of each instance, providing a new way for solving complex multi-objective scheduling problems.

multi-objective flexible job shop scheduling; layered Pareto optimization; two-stage Pareto ant colony algorithm; neighborhood search

2015-11-23。 作者簡(jiǎn)介:趙博選(1986—),男,博士生;高建民(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家科技重大專(zhuān)項(xiàng)資助項(xiàng)目(2012ZX04010-071)。

時(shí)間:2016-05-24

10.7652/xjtuxb201607022

F406.2

A

0253-987X(2016)07-0145-07

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160524.1204.002.html