多目標(biāo)U型拆卸線平衡問題的Pareto蟻群遺傳算法

張則強(qiáng), 汪開普, 朱立夏, 程文明

(西南交通大學(xué)機(jī)械工程學(xué)院, 四川 成都 610031)

隨著我國經(jīng)濟(jì)的高速增長,產(chǎn)品更新?lián)Q代的步伐加快,產(chǎn)生了大量廢舊機(jī)電產(chǎn)品,廢舊機(jī)電產(chǎn)品的回收再利用是生態(tài)文明建設(shè)的重要組成部分.綠色發(fā)展已經(jīng)成為國家戰(zhàn)略,國務(wù)院印發(fā)的《中國制造2025》[1]中明確提出,要“發(fā)展循環(huán)經(jīng)濟(jì),提高資源回收利用效率,構(gòu)建綠色制造體系”.拆卸是實(shí)現(xiàn)資源回收再利用的關(guān)鍵一環(huán),也是綠色制造系統(tǒng)的重要組成部分,通過拆卸可實(shí)現(xiàn)貴重材料和有價(jià)值零部件的回收,是構(gòu)筑產(chǎn)品生命周期完整性與封閉性的必要環(huán)節(jié).拆卸線是廢舊機(jī)電產(chǎn)品規(guī)?；鹦渡a(chǎn)的最佳方式之一,具有規(guī)范性好、效率高等優(yōu)點(diǎn).然而在實(shí)際生產(chǎn)過程中,拆卸生產(chǎn)線上各工作站間普遍存在著作業(yè)不平衡等現(xiàn)象,對拆卸企業(yè)生產(chǎn)效率的提升產(chǎn)生了較大影響,由此產(chǎn)生了拆卸線平衡問題(disassembly line balancing problem, DLBP)[2],并引起了國內(nèi)外學(xué)者的高度關(guān)注[3-16].

GUNGOR等[2]對多目標(biāo)拆卸線平衡問題進(jìn)行了全面描述,進(jìn)而分析了影響拆卸線生產(chǎn)率的各種因素.傳統(tǒng)的啟發(fā)式算法[2-3]、數(shù)學(xué)規(guī)劃法[4]在求解拆卸線平衡問題時(shí)能夠得到精確解,但只適用于小規(guī)模問題.拆卸線平衡問題是NP (non-deterministic polynomial)完全問題[5],當(dāng)拆卸任務(wù)規(guī)模增大到一定程度時(shí),在有效時(shí)間內(nèi)很難求得最優(yōu)解.亞啟發(fā)式算法[5-15]在求解不同規(guī)模任務(wù)的多目標(biāo)拆卸線平衡問題時(shí)表現(xiàn)出良好的求解性能,能夠得到較優(yōu)解.文獻(xiàn)[5-15]在描述拆卸線平衡問題時(shí)考慮了多個(gè)優(yōu)化目標(biāo),但在處理多目標(biāo)問題時(shí)卻將其轉(zhuǎn)化為為單目標(biāo)問題,一次只能求得一個(gè)解,所得平衡方案無法均衡存在沖突關(guān)系的各目標(biāo).文獻(xiàn)[16]應(yīng)用Pareto蟻群算法在求解多目標(biāo)拆卸線平衡問題上做了很好的研究工作,得到多個(gè)Pareto最優(yōu)解,所得方案兼顧了各目標(biāo)間的均衡性,但其求解性能還有進(jìn)一步提升的空間.

文獻(xiàn)[2-16]中拆卸線布局形式均為直線型,U型布局相較于直線型布局具有占地面積小、柔性高、生產(chǎn)效率高等優(yōu)點(diǎn),有助于生產(chǎn)線效率的進(jìn)一步提高[17-18],基于此,U型布局在拆卸線中也得到了應(yīng)用[19-20].但現(xiàn)有的文獻(xiàn)多是對直線型拆卸線平衡問題展開研究,甚少有對U型拆卸線平衡問題(U-shaped disassembly line balancing problem, UDLBP)進(jìn)行探討.國外文獻(xiàn)中,僅文獻(xiàn)[19]采用協(xié)同蟻群算法求解隨機(jī)混流U型拆卸線平衡問題,以最小化工作站空閑時(shí)間和停工概率為優(yōu)化目標(biāo),采用單目標(biāo)求解思想處理該問題,無法實(shí)現(xiàn)各目標(biāo)間的均衡.國內(nèi)方面,只有文獻(xiàn)[20]應(yīng)用人工蜂群算法按目標(biāo)分級方式處理多目標(biāo)U型拆卸線平衡問題,依然是將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進(jìn)行求解.針對現(xiàn)有文獻(xiàn)對多目標(biāo)U型拆卸線平衡問題研究的不足,有必要對該問題展開研究.

蟻群算法和遺傳算法在求解NP問題時(shí)具有良好的求解性能[5-7,21],將兩種算法融合用于求解復(fù)雜離散問題,能夠?qū)崿F(xiàn)優(yōu)勢互補(bǔ).文獻(xiàn)[22]采用混合蟻群遺傳算法求解復(fù)雜裝配線平衡和調(diào)度問題,結(jié)果表明混合算法相對于單一算法求解質(zhì)量顯著提高.查閱相關(guān)文獻(xiàn),尚未有學(xué)者采用混合蟻群遺傳算法求解U型拆卸線平衡問題.

鑒于現(xiàn)有文獻(xiàn)對拆卸線平衡問題研究的不足,本文結(jié)合Pareto解集思想[23]以及蟻群算法和遺傳算法求解NP問題的優(yōu)勢,提出一種求解U型拆卸線平衡問題的多目標(biāo)Pareto蟻群遺傳算法(ant colony and genetic algorithm, ACGA),改進(jìn)算法的蟻群操作和遺傳操作.通過對比測試與實(shí)例應(yīng)用,驗(yàn)證了所提算法的求解性能.

1 多目標(biāo)U型拆卸線平衡問題

1.1 U型拆卸線描述

傳統(tǒng)的拆卸線一般采用直線型,待拆卸產(chǎn)品在直線排列的傳動(dòng)設(shè)備上傳遞,工人在傳動(dòng)設(shè)備的一側(cè)進(jìn)行拆卸作業(yè),直至所需拆卸的作業(yè)任務(wù)完成為止,在傳動(dòng)設(shè)備的另一端輸出廢料,如圖1所示,圖中Ti(i=1,2,…,4)為工作站作業(yè)時(shí)間.直線型拆卸線具有布局簡單,容易實(shí)現(xiàn)拆卸作業(yè)任務(wù)的自動(dòng)化、規(guī)?；葍?yōu)點(diǎn).

圖1 直線型拆卸線示意Fig.1 Schematic diagram of linear disassembly line

U型拆卸線是將拆卸傳動(dòng)裝置沿逆時(shí)針方向按U型布置,工人可以在傳動(dòng)設(shè)備兩側(cè)作業(yè).在同一個(gè)工作站內(nèi),工人可對無緊前任務(wù)或無緊后任務(wù)的零部件進(jìn)行拆卸.相對于傳統(tǒng)直線型拆卸線,U型拆卸線布局更加合理,可減少工人的行走距離,提高工作效率;待拆卸產(chǎn)品入口和廢料出口在同一側(cè),可降低物流成本;同時(shí),合理的任務(wù)分配能有效減少工作站數(shù)量.

現(xiàn)以含10個(gè)拆卸任務(wù)的某機(jī)械部件的拆卸線為例,對比U型拆卸線和直線型拆卸線的性能.圖1中,箭頭連接的任務(wù)間存在優(yōu)先關(guān)系,各零部件的拆卸時(shí)間分別為2、4、3、5、6、2、4、4、3、3，設(shè)定生產(chǎn)節(jié)拍TC=12.由圖1可知,直線型拆卸線中拆卸方案為:{1,2,3}→{4,5}→{6,7,8}→{9,10},一共開啟4個(gè)工作站;每個(gè)工作站的作業(yè)時(shí)間分別為T1=9,T2=11,T3=10,T4=6,各工作站間作業(yè)時(shí)間非常不均衡.

將直線型拆卸線改為U型拆卸線,如圖2所示,平衡方案為:{1,-10,-9,2}→{3,-8,4}→{5,6,-7},方案中負(fù)號(hào)表示拆卸位置位于U型拆卸線出口一側(cè),一共開啟3個(gè)工作站,且每個(gè)工作站的作業(yè)時(shí)間都達(dá)到設(shè)定的生產(chǎn)節(jié)拍,各工作站間達(dá)到了完全均衡.通過上述對比可知,U型拆卸線布局較直線型拆卸線布局更具優(yōu)勢.

圖2 U型拆卸線示意Fig.2 Schematic diagram of U-shaped disassembly line

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

針對U型拆卸線平衡問題的特點(diǎn),考慮了以下幾種情況:為減少拆卸設(shè)施成本,應(yīng)盡量減少開啟工作站數(shù)目;為提高作業(yè)效率和公平性,應(yīng)最大限度滿足各個(gè)工作站間的均衡性;最大限度降低拆卸作業(yè)成本,以便實(shí)現(xiàn)經(jīng)濟(jì)效益最大化;同時(shí)應(yīng)該避免拆卸方向頻繁改變,盡量減少非作業(yè)時(shí)間.建立多目標(biāo)U型拆卸線平衡問題模型[5,16]為

minf1=M;

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?sij=1,

(8)

式中:M為工作站數(shù);m為工作站編號(hào);N為拆卸任務(wù)數(shù);tn為第n個(gè)拆卸任務(wù)的作業(yè)時(shí)間;xmn為0-1分配變量,若第n個(gè)任務(wù)被分配到第m個(gè)工作站的入口側(cè),則xmn=1,否則xmn=0;ymn為0-1分配變量,若第n個(gè)任務(wù)被分配到第m個(gè)工作站的出口側(cè),則ymn=1,否則ymn=0;Un為第n個(gè)拆卸任務(wù)的單位時(shí)間拆卸成本;rn為序列中第n個(gè)拆卸任務(wù)的拆卸方向;Rn為拆卸序列中方向改變次數(shù),若前后兩任務(wù)的拆卸方向不同(rn≠rn-1),則Rn=1,否則Rn=0;i,j為拆卸序列中任務(wù)的編號(hào);sij為任務(wù)i,j間優(yōu)先關(guān)系值,若拆卸任務(wù)i是拆卸任務(wù)j的緊前任務(wù),則sij=1,否則sij=0,構(gòu)造任務(wù)間優(yōu)先關(guān)系矩陣S,有S=[sij]N×N.

式(1)～(4)為U型拆卸線平衡問題的目標(biāo)函數(shù),分別表示最小化開啟工作站數(shù)、平衡工作站的空閑時(shí)間、最小化拆卸成本、最小化拆卸方向改變次數(shù),其中工作站的單位時(shí)間拆卸成本定義為該工作站內(nèi)拆卸任務(wù)的最大單位時(shí)間拆卸成本,需要指出的是U型拆卸線中拆卸任務(wù)方向的改變不同于直線型拆卸線中工人進(jìn)行作業(yè)任務(wù)的方向改變,而是生產(chǎn)線上拆卸任務(wù)方向的改變.

式(5)～(8)為U型拆卸線平衡問題的約束條件,式(5)表示拆卸生產(chǎn)線所開啟的工作站數(shù)不少于理論工作站數(shù),且每個(gè)工作站均在生產(chǎn)作業(yè),所開啟的工作站不應(yīng)超過拆卸任務(wù)數(shù);式(6)表示分配到每個(gè)工作站的作業(yè)任務(wù)時(shí)間上限為生產(chǎn)節(jié)拍;式(7)表示拆卸線為完全拆卸,所有零部件都必須進(jìn)行拆卸作業(yè),且每一項(xiàng)任務(wù)只能在一個(gè)工作站中完成;式(8)表示拆卸任務(wù)的進(jìn)行須符合任務(wù)間的幾何約束,即滿足拆卸任務(wù)間的拆卸優(yōu)先關(guān)系.

2 Pareto蟻群遺傳算法

混合蟻群遺傳算法很好的結(jié)合了蟻群算法和遺傳算法的優(yōu)點(diǎn),具有更強(qiáng)的搜索能力[22],本文針對多目標(biāo)U型拆卸線平衡問題的特點(diǎn),結(jié)合Pareto解集思想,改進(jìn)蟻群算法的初始可行解,構(gòu)造遺傳操作,提出Pareto蟻群遺傳算法.

2.1 可行解的構(gòu)造

在拆卸線平衡問題中,隨機(jī)生成的序列不一定滿足任務(wù)優(yōu)先關(guān)系,故首先需要構(gòu)造可行解.

用蟻群算法構(gòu)造拆卸線平衡問題的可行解可視為螞蟻在信息素濃度的指引下尋找下一個(gè)拆卸任務(wù),螞蟻經(jīng)過的路徑組成問題的拆卸序列,隨著信息素的更新實(shí)現(xiàn)路徑的尋優(yōu).

蟻群算法中啟發(fā)式因子代表著選擇下一個(gè)拆卸任務(wù)的期望程度.結(jié)合拆卸線平衡問題的特征,以最長拆卸作業(yè)時(shí)間、最小拆卸成本差距為啟發(fā)式規(guī)則,構(gòu)建任務(wù)l的啟發(fā)式函數(shù)為

(9)

式中:Aj為當(dāng)前位置j(j≥2)的候選任務(wù)集;l∈Aj;s∈Aj;k為位置j的前一項(xiàng)位置(即j-1)處所對應(yīng)的任務(wù).

為使螞蟻以最大概率收斂到全局最優(yōu)解,綜合考慮多種規(guī)則,構(gòu)造混合搜索機(jī)制[21],被分配到特定序列位置j的任務(wù)i為

(10)

式中:r為(0,1)間的隨機(jī)數(shù);r1、r2為定義的參數(shù);τie為任務(wù)i到后續(xù)任務(wù)e的信息素;Aj為當(dāng)前分配序列位置j的候選任務(wù)集;α為信息素權(quán)值;β為啟發(fā)式信息權(quán)值.

為保證可行解滿足拆卸線實(shí)際生產(chǎn)情況,每一項(xiàng)任務(wù)的選擇都要考慮拆卸優(yōu)先關(guān)系約束.同時(shí)需判斷每一項(xiàng)任務(wù)在U型拆卸線兩側(cè)中的位置:無緊前約束的任務(wù)位于U型入口側(cè),符號(hào)為“+”;無緊后約束的任務(wù)位于U型出口側(cè),符號(hào)為“-”;若拆卸任務(wù)既無緊前約束,也無緊后約束,則符號(hào)與前一個(gè)任務(wù)相同.

構(gòu)造可行解的具體步驟如下:

(1) 從矩陣Y中按式(10)挑選任務(wù)i作為位置j處的任務(wù),要求所選任務(wù)無緊前約束或無緊后約束,在矩陣中表現(xiàn)為行列全為零,并判斷拆卸任務(wù)的符號(hào);存在多個(gè)可選任務(wù)時(shí),從可選任務(wù)集中隨機(jī)挑選;

(2) 將與任務(wù)i有優(yōu)先關(guān)系的約束從Y中刪除:?k∈{1,2,…,N},令yik=0,yki=0;

(3) 尋找下一位置處的任務(wù),令j=j+1;

(4) 重復(fù)上述3步驟,完成所有任務(wù)分配.

2.2 Pareto解集的更新

在含D個(gè)目標(biāo)的多目標(biāo)問題中,給定兩個(gè)可行拆卸序列X1、X2,若X1、X2滿足

fd(X1)≤fd(X2), ?d∈{1,2,…,D},

(11)

fd(X1)

(12)

則稱X1Pareto支配X2,記為X1X2.

若可行解X*滿足:?X使得XX*,則稱X*為Pareto最優(yōu)解或非劣解.所有X*的集合PS={X*|?XX*}構(gòu)成Pareto最優(yōu)解集,對應(yīng)目標(biāo)函數(shù)值稱為Pareto最優(yōu)前沿.

根據(jù)可行解之間的支配關(guān)系,保留支配解于外部檔案中,剔除非支配解,完成外部檔案的更新.

2.3 信息素的更新

采用非支配排序遺傳算法(non-dominated sorting genetic algorithm Ⅱ, NSGA-Ⅱ)擁擠距離機(jī)制[23]評價(jià)外部檔案中的非劣解,定義邊界個(gè)體的擁擠距離L1=Lk=∞,擁擠距離表達(dá)式為

(13)

式中:g=2,…,k-1,k為非劣解的個(gè)數(shù);fd,max、fd,min分別為第d個(gè)目標(biāo)函數(shù)值的最大值和最小值.

螞蟻在行走過后的路徑上留下信息素,隨著時(shí)間的推移,信息素會(huì)不斷更新.局部信息素的更新使得螞蟻能夠擺脫已選任務(wù)的影響,跳出局部最優(yōu),增強(qiáng)探索未選任務(wù)的能力.螞蟻將任務(wù)i分配到位置j,該路徑上局部信息素更新方式為

τij=(1-ρ1)τij+ρ1τ0,

(14)

(15)

式中:ρ1為局部信息素?fù)]發(fā)因子,0<ρ1<1;τ0為初始信息素.

在算法迭代過程中,只有全局最優(yōu)的螞蟻才允許釋放信息素,所對應(yīng)的拆卸方案路線上的信息素會(huì)增加,即非劣解所對應(yīng)的拆卸方案存在信息素的增加,其他方案路線上不會(huì)有信息素增加.全局信息素增加方式為

τij=(1-ρ2)τij+ρ2Δτij,

(16)

(17)

式中:ρ2為全局信息素?fù)]發(fā)因子,0<ρ2<1;q為調(diào)整參數(shù).

2.4 選擇操作

在多目標(biāo)拆卸線平衡問題中,無法直接通過某個(gè)目標(biāo)值評價(jià)適應(yīng)度的大小,而是根據(jù)可行解之間的支配關(guān)系評價(jià)個(gè)體的優(yōu)劣,蟻群算法外部檔案中非劣解均為可選的優(yōu)質(zhì)個(gè)體,隨機(jī)挑選蟻群算法外部檔案中兩個(gè)非劣解作為下一步操作的個(gè)體.

2.5 交叉操作

在拆卸線平衡問題中,受任務(wù)間優(yōu)先關(guān)系的約束,傳統(tǒng)方法中隨機(jī)交叉方式將產(chǎn)生大量不可行解,會(huì)降低算法效率.本文采用雙點(diǎn)映射交叉的方式,具體操作過程如圖3所示.

圖3 交叉操作示意Fig.3 Schematic diagram of crossover operation

在父代Xcurrent 1、Xcurrent 2中隨機(jī)選取兩點(diǎn)作為交叉點(diǎn),保持Xcurrent 1中交叉點(diǎn)1之前的序列{6,3,7}和交叉點(diǎn)2之后的序列{2,4,9}不變,兩交叉點(diǎn)之間的序列{8,5,1}在Xcurrent 2中順序?yàn)閧1,5,8},組成子代Xnew 1={6,3,7,1,5,8,2,4,9},因{1,5,8}在Xcurrent 2中滿足優(yōu)先關(guān)系,則生成的子代必然滿足優(yōu)先關(guān)系.同理可以得到子代Xnew 2.因U型拆卸線中當(dāng)前拆卸任務(wù)可從無緊后任務(wù)中選擇,導(dǎo)致交叉后的任務(wù)可能在其緊后任務(wù)之前,不滿足拆卸優(yōu)先關(guān)系,需要重新選擇交叉點(diǎn).

2.6 變異操作

同交叉操作類似,受任務(wù)間優(yōu)先關(guān)系約束,變異操作中隨機(jī)交換兩點(diǎn)將產(chǎn)生大量不可行解.本文采用如圖4所示的單點(diǎn)變異操作.在父代Xcurrent中隨機(jī)選取一點(diǎn)作為變異點(diǎn)4,受優(yōu)先關(guān)系約束,需要找到任務(wù)4的緊前任務(wù)和緊后任務(wù),而任務(wù)4可以變換的位置在最近的緊前任務(wù)8和最近的緊后任務(wù)2之間,即任務(wù)1、5之前或是任務(wù)9、6之后,隨機(jī)選擇一點(diǎn)進(jìn)行插入,如選擇任務(wù)9之后,則子代Xnew={3,8,1,5,9,4,6,2,7}.在挑選變異位置時(shí),若沒有可選的插入位置,則需重新選擇變異點(diǎn).

圖4 變異操作示意Fig.4 Schematic diagram of mutation operation

2.7 算法步驟

在上述定義的基礎(chǔ)上,求解多目標(biāo)U型拆卸線平衡問題的Pareto蟻群遺傳算法具體實(shí)現(xiàn)步驟如下:

步驟1算法參數(shù)設(shè)定:種群規(guī)模Nant,最大迭代次數(shù)T,外部檔案規(guī)模N0,信息素權(quán)值α,啟發(fā)式信息權(quán)值β,參數(shù)r1、r2,局部信息素?fù)]發(fā)因子ρ1,全局信息素?fù)]發(fā)因子ρ2,調(diào)整參數(shù)q,交叉概率Pc,變異概率Pm,生產(chǎn)節(jié)拍TC;

步驟2開始循環(huán)計(jì)數(shù),令t=1;初始化蟻群,建立Pareto解集,令外部檔案Q=?;

步驟3根據(jù)2.1節(jié)內(nèi)容生成可行拆卸序列,按式(14)更新局部信息素;

步驟4計(jì)算目標(biāo)函數(shù)值,篩選種群非劣解,更新外部檔案Q;

步驟5執(zhí)行選擇、交叉、變異等遺傳操作;

步驟6對遺傳操作后的個(gè)體篩選種群非劣解,更新外部檔案Q;

步驟7按式(16)更新全局信息素;

步驟8計(jì)算Q中非劣解個(gè)數(shù)NQ:若NQ>N0,按式(13)評價(jià)非劣解,選取N0個(gè)Lg較大的非劣解置于Q中,進(jìn)入下一步;否則,直接進(jìn)入下一步;

步驟9若t

步驟10算法終止,得到最優(yōu)拆卸方案.

3 算法驗(yàn)證與實(shí)例應(yīng)用

所設(shè)計(jì)的Pareto蟻群遺傳算法部分參數(shù)設(shè)置如下:α=1.5,β=1.5,r1=0.6,r2=0.9,ρ1=0.4,ρ2=0.3,q=10,Pc=0.9,Pm=0.1.其它參數(shù)需根據(jù)實(shí)例具體情況而設(shè)定.選用MATLAB 7.11進(jìn)行測試驗(yàn)證.

3.1 算法驗(yàn)證

以文獻(xiàn)[16]中算例為研究對象,驗(yàn)證所提算法在的求解性能.該算例相關(guān)數(shù)據(jù)見文獻(xiàn)[16].該文獻(xiàn)的優(yōu)化目標(biāo)為最小化平均閑置率Fidle、最大化負(fù)荷均衡指標(biāo)Fsmooth、最小化拆卸成本Fcost.目標(biāo)函數(shù)Fcost與本文目標(biāo)函數(shù)f3相同,引入該文獻(xiàn)的前兩個(gè)目標(biāo)函數(shù),如下式(18)、(19)所示,將多目標(biāo)函數(shù)轉(zhuǎn)化為式(20).

(18)

(19)

minF=min(Fidle,1-Fsmooth,Fcost).

(20)

現(xiàn)將文獻(xiàn)[16]利用多目標(biāo)Pareto蟻群算法(ant colony optimization, ACO)求得的6種平衡方案結(jié)果列于表1中.采用本文所提多目標(biāo)Pareto蟻群遺傳算法對該算例進(jìn)行求解,算法需設(shè)定的參數(shù)有:Nant=50,T=200,N0=8,TC=600.共求得8個(gè)非劣解的Pareto解集,將非劣解的平衡方案列于表2中.

表1 文獻(xiàn)[16]Pareto ACO求解結(jié)果Tab.1 Solution results of Pareto ACO in literature [16]

將表2中Pareto ACGA結(jié)果與表1中Pareto ACO結(jié)果進(jìn)行比較.在Fidle指標(biāo)上,ACGA的8個(gè)非劣解均求得最優(yōu)解0.057 9,平均值為0.057 9,ACO只有3個(gè)非劣解求得最優(yōu)解0.057 9,其他3個(gè)解為0.175 7,平均值為0.116 8,ACGA在Fidle上較ACO提高了50.43%;在Fsmooth指標(biāo)上,ACGA結(jié)果范圍為91.5%～99.0%,平均值為95.31%,ACO結(jié)果范圍為85.9%～97.5%,平均值為92.31%,ACGA在Fsmooth上較ACO方案提高了3.25%,ACGA平衡率更高;在Fcost指標(biāo)上,ACGA結(jié)果在130.332～146.994之間,平均值為139.430,ACO結(jié)果在150.546～173.388之間,平均值為162.310,ACGA在Fcost上較ACO提高了14.10%,ACGA成本更低.綜上單目標(biāo)對比可知ACGA結(jié)果明顯優(yōu)于ACO.

綜合3個(gè)目標(biāo)比較:按Pareto支配關(guān)系的定義,ACGA的非劣解1、7、8支配ACO的所有非劣解;ACGA的非劣解2、3支配ACO的非劣解1、3,與ACO的其他4個(gè)非劣解互不占優(yōu);ACGA的非劣解4、6支配ACO的非劣解1、2、3,與ACO另3個(gè)非劣解互不占優(yōu);ACGA的非劣解5支配ACO的非劣解1、2、3、6,與ACO的另兩個(gè)非劣解4、5互不占優(yōu).通過對比可知,所提多目標(biāo)Pareto ACGA能有效求解U型拆卸線平衡問題,且求解性能較多目標(biāo)Pareto ACO更具優(yōu)勢.

表2 所提Pareto ACGA求解平衡方案Tab.2 Balance schemes of proposed Pareto ACGA

3.2 實(shí)例應(yīng)用

現(xiàn)以某型號(hào)打印機(jī)拆卸線為研究對象,分析所提多目標(biāo)Pareto ACGA在U型拆卸線實(shí)例中的應(yīng)用情況.該拆卸線所涉及到的零件的拆卸時(shí)間t(s)、單位時(shí)間拆卸成本U(元/s)、拆卸方向r及其緊前任務(wù)P等拆卸信息如表3所示.表3中拆卸時(shí)間是經(jīng)多次拆卸計(jì)時(shí)取平均值測定.

表3 拆卸任務(wù)相關(guān)信息表Tab.3 Related data information of printer disassembly tasks

綜合實(shí)際拆卸生產(chǎn)情況,設(shè)定生產(chǎn)節(jié)拍TC=145,算法其他參數(shù)設(shè)置為:Nant=50,T=100,N0=8.經(jīng)20次運(yùn)行,計(jì)算平均運(yùn)行時(shí)間為54.36 s,每次運(yùn)行均能求得8個(gè)非劣解,表明所提算法求解結(jié)果具有多樣性.取其中一次結(jié)果的非劣解任務(wù)分配方案列于表4中.

由表4可知,8種平衡方案均求得5個(gè)最優(yōu)工作站,故在方案選擇上只需考慮工作站空閑指標(biāo)、拆卸成本以及拆卸方向改變次數(shù).非劣解在3個(gè)目標(biāo)f2、f3、f4的空間分布如圖5所示.

由表4的求解結(jié)果對比分析可知:8個(gè)方案的空閑指標(biāo)范圍在506～718之間,若要求空閑指數(shù)最小,可以考慮方案8;拆卸成本范圍為6.192～6.917,若要求成本最小,可以選擇方案7;拆卸方向改變次數(shù)范圍為26～39,若要求拆卸方向改變次數(shù)最少,可以選擇方案4.

結(jié)合表4求解結(jié)果與圖5方案結(jié)果空間分布對比分析,綜合考慮某兩個(gè)指標(biāo)進(jìn)行方案選擇:若優(yōu)先考慮空閑指標(biāo)和拆卸成本,可以選擇方案1或方案6;若要求空閑指數(shù)小和拆卸方向改變次數(shù)少,可以選擇方案2或方案8;若要求拆卸成本低、拆卸方向改變次數(shù)少,可以選擇方案3、方案5或方案7.所提算法求得的8種平衡方案可以為決策者提供多種選擇,避免方案選擇上的盲目性.

表4 Pareto ACGA非劣解的平衡方案Tab.4 Non-inferior solution balance schemes of Pareto ACGA

注：?表示方案圖5 ACGA非劣解在f2、f3、f4上空間分布Fig.5 Non-inferior solutions spatial distribution of f2, f3, f4

4 結(jié) 論

(1) 針對傳統(tǒng)直線型拆卸線的不足,構(gòu)造了一種更符合實(shí)際生產(chǎn)情況的U型拆卸線模型,并設(shè)計(jì)了一種基于Pareto解集的多目標(biāo)蟻群遺傳算法,克服了傳統(tǒng)方法求解多目標(biāo)問題的缺陷,實(shí)現(xiàn)了求解結(jié)果的有效性與多樣性.

(2) 蟻群遺傳算法將蟻群算法和遺傳算法各自的優(yōu)點(diǎn)相結(jié)合,能有效避免算法陷入局部最優(yōu).改進(jìn)蟻群算法的啟發(fā)式規(guī)則,使任務(wù)的分配更符合問題的實(shí)際生產(chǎn)情況.通過擁擠距離評價(jià)篩選機(jī)制,實(shí)現(xiàn)了精英保留.采用擁擠度更新螞蟻的全局信息素,能夠平衡各個(gè)目標(biāo)對信息素濃度的影響.將非劣解作為遺傳操作的個(gè)體,且遺傳操作的結(jié)果正反饋于最優(yōu)路徑上的信息素濃度,豐富了螞蟻的尋優(yōu)路徑,同時(shí)加快了算法的收斂速度.

(3) 運(yùn)用所提算法對52項(xiàng)拆卸任務(wù)的測試問題進(jìn)行驗(yàn)算,并與多目標(biāo)Pareto蟻群算法進(jìn)行對比,所提算法求解方案優(yōu)于Pareto蟻群算法的方案,驗(yàn)證了所提算法求解多目標(biāo)U型拆卸線平衡問題的有效性.最后,將所提算法應(yīng)用于具有55項(xiàng)拆卸任務(wù)的某打印機(jī)拆卸實(shí)例中,得到8種候選平衡方案,為決策者提供了廣泛的決策空間.

[1] 國務(wù)院. 國務(wù)院關(guān)于印發(fā)《中國制造2025》的通知[J]. 中華人民共和國國務(wù)院公報(bào),2015(16): 10-26.

[2] GUNGOR A, GUPTA S M. Disassembly line in product recovery[J]. International Journal of Production Research, 2002, 40(11): 2569-2589.

[3] AVIKAL S, MISHRA P K, JAIN R. A Fuzzy AHP and PROMETHEE method-based heuristic for disassembly line balancing problems[J]. International Journal of Production Research, 2014, 52(5): 1306-1317.

[4] BENTAHA M L, BATTAIA O, DOLGUI A. Lagrangian relaxation for stochastic disassembly line balancing problem[J]. Procedia CIRP, 2014(17): 56-60.

[5] MCGOVERN S M, GUPTA S M. A balancing method and genetic algorithm for disassembly line balancing[J]. European Journal of Operational Research, 2007, 179(3): 692-708.

[6] 朱興濤,張則強(qiáng),朱勛夢,等. 求解多目標(biāo)拆卸線平衡問題的一種蟻群算法[J]. 中國機(jī)械工程,2014,25(8): 1075-1079.

ZHU Xingtao, ZHANG Zeqaing, ZHU Xunmeng, et al. An ant colony optimization algorithm for multi-objective disassembly line balancing problem[J]. China Mechanical Engineering, 2014, 25(8): 1075-1079.

[7] MCGOVERN S M, GUPTA S M. Ant colony optimization for disassembly sequencing with multiple objectives[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(5): 481-496.

[8] KALAYCI C B, GUPTA S M. A particle swarm optimization algorithm for solving disassembly line balancing problem[C]∥Proceedings for the Northeast Region Decision Sciences Institute.[S.l.]: Newport, 2012: 347-357.

[9] KALAYCI C B, GUPTA S M, NAKASHIMA K. Bees colony intelligence in solving disassembly line balancing problem[C]∥Proceedings of the 2011 Asian Conference of Management Science and Applications. Sanya: [s.n.], 2011: 34-41.

[10] 張則強(qiáng),胡揚(yáng),陳沖. 求解拆卸線平衡問題的改進(jìn)人工蜂群算法[J]. 西南交通大學(xué)學(xué)報(bào),2016,51(5): 910-917.

ZHANG Zeqiang, HU Yang, CHEN Chong. An improved artificial bee colony algorithm for disassembly line balancing problem[J]. Journal of Southwest Jiaotong University, 2016, 51(5): 910-917.

[11] KALAYCI C B, POLAT O, GUPTA S M. A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2015, 26(2): 182-194.

[12] TUNCEL E, ZEID A, KAMARTHI S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4): 647-659.

[13] KALAYCI C B, GUPTA S M. Tabu search for disassembly line balancing with multiple objectives[C]∥Proceedings of the 41st International Conference on Computers & Industrial Engineering. Los Angeles: [s.n.], 2011: 477-482.

[14] KALAYCI C B, GUPTA S M, NAKASHIMA K. A simulated annealing algorithm for balancing a disassembly line[C]∥Proceedings of the Seventh International Symposium on Environmentally Conscious Design and Inverse Manufacturing. Netherlands: [s.n.], 2011: 713-718.

[15] METE S, CIL Z A, AGPAK K, et al. A solution approach based on beam search algorithm for disassembly line balancing problem[J]. Journal of Manufacturing Systems, 2016, 41: 188-200.

[16] 丁力平,譚建榮,馮毅雄,等. 基于Pareto蟻群算法的拆卸線平衡多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng),2009,15(7): 1406-1413.

DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15(7): 1406-1413, 1429.

[17] ALAVIDOOST M, BABAZADEH H, SAYYARI S. An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem[J]. Applied Soft Computing, 2016, 40: 221-235.

[18] ALAVIDOOST M H, ZARANDI M H, TARIMORADI M, et al. Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times[J]. Journal of Intelligent Manufacturing, 2017, 28(2): 313-336.

[19] AGRAWAL S, TIWARI M K. A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem[J]. International Journal of Production Research, 2008, 46(6): 1405-1429.

[20] 李明,張則強(qiáng),胡揚(yáng). U型布局的拆卸線平衡問題及其求解算法研究[J]. 現(xiàn)代制造工程,2015(7): 7-12.

LI Ming, ZHANG Zeqaing, HU Yang. Research on U-shaped disassembly line balancing problem and solving algorithm[J]. Modern Manufacturing Engineering, 2015(7): 7-12.

[21] 張則強(qiáng),胡俊逸,程文明. 第Ⅰ類雙邊裝配線平衡問題的改進(jìn)蟻群算法[J]. 西南交通大學(xué)學(xué)報(bào),2013,48(4): 724-730.

ZHANG Zeqiang, HU Junyi, CHENG Wenming. Improved ant colony algorithms for two-sided assembly line balancing problem of type Ⅰ[J]. Journal of Southwest Jiaotong University, 2013, 48(4): 724-730.

[22] KUCUKKOC I, ZHANG D Z. Integrating ant colony and genetic algorithms in the balancing and scheduling of complex assembly lines[J]. The International Journal of Advanced Manufacturing Technology, 2016, 82(1/2/3/4): 265-285.

[23] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.