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

張則強, 汪開普, 朱立夏, 程文明

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

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

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

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

蟻群算法和遺傳算法在求解NP問題時具有良好的求解性能[5-7,21],將兩種算法融合用于求解復雜離散問題,能夠實現優勢互補.文獻[22]采用混合蟻群遺傳算法求解復雜裝配線平衡和調度問題,結果表明混合算法相對于單一算法求解質量顯著提高.查閱相關文獻,尚未有學者采用混合蟻群遺傳算法求解U型拆卸線平衡問題.

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

1 多目標U型拆卸線平衡問題

1.1 U型拆卸線描述

傳統的拆卸線一般采用直線型,待拆卸產品在直線排列的傳動設備上傳遞,工人在傳動設備的一側進行拆卸作業,直至所需拆卸的作業任務完成為止,在傳動設備的另一端輸出廢料,如圖1所示,圖中Ti(i=1,2,…,4)為工作站作業時間.直線型拆卸線具有布局簡單,容易實現拆卸作業任務的自動化、規模化等優點.

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

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

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

將直線型拆卸線改為U型拆卸線,如圖2所示,平衡方案為:{1,-10,-9,2}→{3,-8,4}→{5,6,-7},方案中負號表示拆卸位置位于U型拆卸線出口一側,一共開啟3個工作站,且每個工作站的作業時間都達到設定的生產節拍,各工作站間達到了完全均衡.通過上述對比可知,U型拆卸線布局較直線型拆卸線布局更具優勢.

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

1.2 數學模型

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

minf1=M;

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?sij=1,

(8)

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

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

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

2 Pareto蟻群遺傳算法

混合蟻群遺傳算法很好的結合了蟻群算法和遺傳算法的優點,具有更強的搜索能力[22],本文針對多目標U型拆卸線平衡問題的特點,結合Pareto解集思想,改進蟻群算法的初始可行解,構造遺傳操作,提出Pareto蟻群遺傳算法.

2.1 可行解的構造

在拆卸線平衡問題中,隨機生成的序列不一定滿足任務優先關系,故首先需要構造可行解.

用蟻群算法構造拆卸線平衡問題的可行解可視為螞蟻在信息素濃度的指引下尋找下一個拆卸任務,螞蟻經過的路徑組成問題的拆卸序列,隨著信息素的更新實現路徑的尋優.

蟻群算法中啟發式因子代表著選擇下一個拆卸任務的期望程度.結合拆卸線平衡問題的特征,以最長拆卸作業時間、最小拆卸成本差距為啟發式規則,構建任務l的啟發式函數為

(9)

式中:Aj為當前位置j(j≥2)的候選任務集;l∈Aj;s∈Aj;k為位置j的前一項位置(即j-1)處所對應的任務.

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

(10)

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

為保證可行解滿足拆卸線實際生產情況,每一項任務的選擇都要考慮拆卸優先關系約束.同時需判斷每一項任務在U型拆卸線兩側中的位置:無緊前約束的任務位于U型入口側,符號為“+”;無緊后約束的任務位于U型出口側,符號為“-”;若拆卸任務既無緊前約束,也無緊后約束,則符號與前一個任務相同.

構造可行解的具體步驟如下:

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

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

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

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

2.2 Pareto解集的更新

在含D個目標的多目標問題中,給定兩個可行拆卸序列X1、X2,若X1、X2滿足

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

(11)

fd(X1)

(12)

則稱X1Pareto支配X2,記為X1X2.

若可行解X*滿足:?X使得XX*,則稱X*為Pareto最優解或非劣解.所有X*的集合PS={X*|?XX*}構成Pareto最優解集,對應目標函數值稱為Pareto最優前沿.

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

2.3 信息素的更新

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

(13)

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

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

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

(14)

(15)

式中:ρ1為局部信息素揮發因子,0<ρ1<1;τ0為初始信息素.

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

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

(16)

(17)

式中:ρ2為全局信息素揮發因子,0<ρ2<1;q為調整參數.

2.4 選擇操作

在多目標拆卸線平衡問題中,無法直接通過某個目標值評價適應度的大小,而是根據可行解之間的支配關系評價個體的優劣,蟻群算法外部檔案中非劣解均為可選的優質個體,隨機挑選蟻群算法外部檔案中兩個非劣解作為下一步操作的個體.

2.5 交叉操作

在拆卸線平衡問題中,受任務間優先關系的約束,傳統方法中隨機交叉方式將產生大量不可行解,會降低算法效率.本文采用雙點映射交叉的方式,具體操作過程如圖3所示.

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

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

2.6 變異操作

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

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

2.7 算法步驟

在上述定義的基礎上,求解多目標U型拆卸線平衡問題的Pareto蟻群遺傳算法具體實現步驟如下:

步驟1算法參數設定:種群規模Nant,最大迭代次數T,外部檔案規模N0,信息素權值α,啟發式信息權值β,參數r1、r2,局部信息素揮發因子ρ1,全局信息素揮發因子ρ2,調整參數q,交叉概率Pc,變異概率Pm,生產節拍TC;

步驟2開始循環計數,令t=1;初始化蟻群,建立Pareto解集,令外部檔案Q=?;

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

步驟4計算目標函數值,篩選種群非劣解,更新外部檔案Q;

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

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

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

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

步驟9若t

步驟10算法終止,得到最優拆卸方案.

3 算法驗證與實例應用

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

3.1 算法驗證

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

(18)

(19)

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

(20)

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

表1 文獻[16]Pareto ACO求解結果Tab.1 Solution results of Pareto ACO in literature [16]

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

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

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

3.2 實例應用

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

表3 拆卸任務相關信息表Tab.3 Related data information of printer disassembly tasks

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

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

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

結合表4求解結果與圖5方案結果空間分布對比分析,綜合考慮某兩個指標進行方案選擇:若優先考慮空閑指標和拆卸成本,可以選擇方案1或方案6;若要求空閑指數小和拆卸方向改變次數少,可以選擇方案2或方案8;若要求拆卸成本低、拆卸方向改變次數少,可以選擇方案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 結 論

(1) 針對傳統直線型拆卸線的不足,構造了一種更符合實際生產情況的U型拆卸線模型,并設計了一種基于Pareto解集的多目標蟻群遺傳算法,克服了傳統方法求解多目標問題的缺陷,實現了求解結果的有效性與多樣性.

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

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

[1] 國務院. 國務院關于印發《中國制造2025》的通知[J]. 中華人民共和國國務院公報,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] 朱興濤,張則強,朱勛夢,等. 求解多目標拆卸線平衡問題的一種蟻群算法[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] 張則強,胡揚,陳沖. 求解拆卸線平衡問題的改進人工蜂群算法[J]. 西南交通大學學報,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蟻群算法的拆卸線平衡多目標優化[J]. 計算機集成制造系統,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] 李明,張則強,胡揚. U型布局的拆卸線平衡問題及其求解算法研究[J]. 現代制造工程,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] 張則強,胡俊逸,程文明. 第Ⅰ類雙邊裝配線平衡問題的改進蟻群算法[J]. 西南交通大學學報,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.