基于多目標算法與動態(tài)仿真的帶調整時間的拆卸線平衡優(yōu)化方法

李六柯 張則強 胡 揚 鄒賓森

西南交通大學機械工程學院，成都，610031

基于多目標算法與動態(tài)仿真的帶調整時間的拆卸線平衡優(yōu)化方法

李六柯 張則強 胡 揚 鄒賓森

西南交通大學機械工程學院，成都，610031

針對拆卸方向改變對作業(yè)時間的影響，以最小化拆卸成本、無效作業(yè)率和不平滑率為優(yōu)化目標，構建了考慮調整時間的多目標拆卸線平衡問題模型，并提出了一種Pareto免疫遺傳算法與仿真技術相結合的求解方法。算法融合了遺傳算子和免疫算子，能有效避免解出現(xiàn)退化和陷入局部最優(yōu)。通過求解25項拆卸任務算例，并與現(xiàn)有5種算法進行對比，驗證了所提算法的有效性。進而將所提模型和算法應用于某打印機拆卸線實例，進一步考慮拆卸時間不確定、存在故障等實際情況，運用仿真技術分析與優(yōu)化，結果表明所提方法能有效降低等待和堵塞造成的無效作業(yè)時間，提高拆卸效率。

拆卸線平衡問題；多目標優(yōu)化；調整時間；免疫遺傳算法；仿真

0 引言

文獻[1]針對拆卸線中的任務排序及流水作業(yè)控制問題，首次正式提出了拆卸線平衡問題，并設計了一種基于多維優(yōu)先級值累加篩選策略的啟發(fā)式算法。在DLBP的早期研究中以啟發(fā)式算法[2-3]為主，如貪婪算法與2-opt算法結合[3]。啟發(fā)式算法具有原理直觀、操作簡單，能快速求得一個可行解等優(yōu)點，但求解結果完全依賴啟發(fā)式規(guī)則，具有不確定性。為提高求解質量，一些學者嘗試采用數(shù)學規(guī)劃方法[4]，但由于DLBP是NP完全問題[5]，求解難度隨著問題規(guī)模的增大呈幾何級增長，因而數(shù)學規(guī)劃方法不適用于求解大規(guī)模問題。智能算法因能很好兼顧求解質量和求解效率而被廣泛使用，如遺傳算法[6]、蟻群算法[7-8]、人工蜂群算法[9]和粒子群算法[10]等。上述文獻在建模階段雖然考慮了多個優(yōu)化目標，但使用智能算法求解時卻將多目標問題轉化為帶有優(yōu)先順序的單目標問題，而多個優(yōu)化目標間往往是相互沖突的，這種處理方法難以保證所有目標間的均衡性。丁力平等[11]提出了一種多目標蟻群算法，結合Pareto解集篩選策略，為求解多目標DLBP提供了一種新思路。

前述文獻中DLBP模型均假設忽略調整時間，或將其歸為作業(yè)時間，然而，在實際拆卸操作中，當調整時間占比比較大或調整工作由前后任務共同決定時，則不能忽略調整時間的影響。文獻[12]將拆卸方向改變次數(shù)作為優(yōu)化目標，但未深入研究拆卸方向改變對拆卸線平衡性的影響，同時也未考慮由拆卸方向改變引起的調整時間。

基于此，本文引入因拆卸方向改變帶來的調整時間，構建了考慮調整時間的多目標DLBP模型;在節(jié)拍時間已知、拆卸工作站數(shù)目和周期時間未知情況下，綜合拆卸成本、無效作業(yè)率和不平滑率等三個目標，采用一種基于Pareto思想的多目標免疫遺傳算法(multi-objective immune genetic algorithm, MIGA)進行求解;進而針對實際生產中由于拆卸時間不確定及零部件或設備故障導致的生產延誤等情況，應用仿真技術對理論方案進行建模仿真，并提出改善方案。

1 考慮調整時間的多目標DLBP模型

為建立DLBP模型，現(xiàn)作如下假設：報廢產品足夠多，不存在缺貨情況；在拆卸線上拆除全部零件；拆卸線采用直線型布局；所有零部件齊全、連接可靠、能夠正常拆卸；標準化拆卸作業(yè)，拆卸時間已知；不考慮零部件在拆卸線上的流轉時間；在滿足優(yōu)先關系約束條件下，得到拆卸任務序列，并根據(jù)節(jié)拍時間開啟工作站，分配拆卸任務。該問題為尋求一組滿足約束條件的拆卸序列，同時優(yōu)化多個目標。

1.1符號說明

n為待拆卸產品包含的總任務數(shù)目；M為拆卸過程開啟的工作站數(shù)目；ti為任務i的作業(yè)時間；A為優(yōu)先關系矩陣，A=(aij)n×n，若任務i為任務j的緊前工作，則aij=1，否則aij=0；xim表示當任務i分配到第m個拆卸工作站，則xim=1，否則xim=0；Tc為周期時間；Tt為由產量和工作時間估計的節(jié)拍時間；hm為第m個工作站的作業(yè)時間；TSm為第m個工作站的調整時間。ci為任務i的單位時間拆卸成本；ri為任務i的拆卸方向；qi為任務i在拆卸序列的位置；di為任務i的需求量。

1.2數(shù)學模型

在實際生產中，當某工作站完成了所分配的拆卸任務，且下游工作站處于空閑狀態(tài)時，作業(yè)對象不必等到周期時間結束即可直接輸送到下游工作站；若下游工作站仍在工作狀態(tài)，則該工作站處于堵塞狀態(tài)，因此，對實際拆卸線進行平衡優(yōu)化時，目標值的計算應以實際周期時間Tc為準。周期時間由工作站作業(yè)時間和調整時間共同決定，其計算公式如下：

Tc=max(hm+TSm)
m∈{1,2,…,M}

(1)

出于節(jié)約成本、提高效率的考慮，選取拆卸成本f1、無效作業(yè)率f2和不平滑率f3為優(yōu)化目標，則有

(2)

(3)

(4)

考慮調整時間的多目標拆卸線平衡問題模型如下：

目標函數(shù)

F=min(f1,f2,f3)

(5)

約束條件

(6)

(7)

Tc≤Tt

(8)

其中，式(6)保證所有拆卸任務分配完畢且任務不可再分；式(7)保證拆卸序列滿足優(yōu)先關系約束；式(8)保證周期時間不超過節(jié)拍時間。

2 Pareto免疫遺傳算法設計

免疫遺傳算法是一種基于迭代搜索機制的混合智能優(yōu)化算法，通過將免疫操作融入遺傳算法，為個體及種群更新提供指導，從而有效避免解出現(xiàn)退化和早熟。該混合算法能夠在解的質量和多樣性方面取得很好平衡，全局搜索能力強，已在諸多組合優(yōu)化問題中得到了成功應用，如調度問題[13]、旅行商問題[14]和設施布局問題[15]等，并表現(xiàn)出優(yōu)異的求解性能。本文結合多目標拆卸線平衡問題的特點，引入Pareto思想，提出了一種求解DLBP的Pareto多目標免疫遺傳算法。

2.1Pareto解集

DLBP的目標函數(shù)F(X)是最小化多目標優(yōu)化函數(shù)，決策變量X表示可行拆卸序列。多目標優(yōu)化問題中各目標間量綱不同，互相沖突，難以進行比較。借鑒Pareto思想評價多目標問題解的優(yōu)劣，決策空間中的任意兩個解X1、X2滿足：

(9)

則稱X1支配X2，記為X1X2，X2稱為被支配解。若X1不被任意可行解支配，則稱X1為非劣解，互不占優(yōu)的非劣解構成Pareto最優(yōu)解集。Pareto最優(yōu)解集映射在目標空間的集合稱為Pareto最優(yōu)前沿。其中，Z為子目標函數(shù)個數(shù)；fi(X)、fj(X)為第i、j個子目標函數(shù)。

2.2編碼和解碼方法

DLBP屬于典型的組合優(yōu)化問題，帶有復雜的約束條件，需避免非法解和不可行解。其解的形式為滿足約束條件的最優(yōu)排列，合理的編碼方式是智能算法求解問題的關鍵。本文采用基于零件編號的編碼方式，即長度為n的整數(shù)編碼表示拆卸序列。

解碼是指將拆卸序列還原為任務分配方案，結合式(1)中拆卸任務的作業(yè)時間和調整時間，在保證周期時間不超過節(jié)拍時間的前提下，依次將拆卸序列中的任務分配到工作站，直至所有的任務分配完畢。具體的解碼操作見表1。

2.3種群初始化

在滿足優(yōu)先關系約束條件下隨機生成一個長度為n的一維數(shù)組，其元素與拆卸任務編號一一對應，該數(shù)組表示可行拆卸序列，重復執(zhí)行N次得到初始種群。生成可行拆卸序列的步驟如下。

(1)根據(jù)優(yōu)先關系約束搜索無緊前工作的拆卸任務，構成待分配任務集V，隨機在V中選擇一個任務，分配到拆卸序列。

(2)約束已分配任務，解除已分配任務對未分配任務的約束。

(3)重復執(zhí)行步驟(1)、步驟(2)，直至所有任務分配完畢。

表1 解碼操作過程Tab.1 The decode operation

2.4構建疫苗庫

疫苗庫是某一問題特征信息的集合，反映了拆卸任務分配的一種優(yōu)先順序。針對問題特點，以加權值和拆卸時間為疫苗產生規(guī)則：拆卸任務按加權值降序排列，若加權值相等，則優(yōu)先分配作業(yè)時間長的拆卸任務，其中某任務的加權值等于該任務與前序任務的作業(yè)時間之和。確定某拆卸任務在該排列中的位置，則排序位置在其前的任務即為該任務的疫苗。

2.5遺傳算子

遺傳算子包括交叉、變異兩個操作，以實現(xiàn)個體間的信息交換和局部搜索。

(1)交叉操作。采用兩點交叉方式，種群中個體隨機兩兩配對且不重復，根據(jù)交叉概率Pc判斷配對個體是否執(zhí)行交叉操作，隨機選擇兩個不同的交叉點，交換兩父代在交叉點間的元素。由于父代均為可行序列，交叉操作未改變拆卸任務的相對位置，交叉子代仍滿足優(yōu)先關系約束，保證了拆卸序列的可行性。

(2)變異操作。采用多點變異方式，根據(jù)變異概率Pm選擇執(zhí)行變異操作的任務。為保證變異操作后的個體仍為可行序列，變異位置必須滿足以下兩個條件：①其所有緊前工作的最后一項任務后的位置；②其所有緊后工作的最前一項任務前的位置。其余任務的相對位置保持不變，變異子代繼承了父代的局部信息，同時保證了拆卸序列的可行性。

2.6免疫算子

免疫算子包括接種疫苗、免疫檢測、更新外部檔案、免疫平衡和免疫選擇等操作，為個體進化提供方向，維持種群多樣性。

(2)免疫檢測操作。計算接種疫苗前后抗體的適應度，根據(jù)Pareto思想，判斷抗體是否得到優(yōu)化。若X2X1，則保留子代；否則，若接種疫苗次數(shù)在最大嘗試次數(shù)L=n/2?范圍內，則需重新接種疫苗；若超出最大嘗試次數(shù)，則保留父代。該操作有效地避免了遺傳算法因交叉、變異操作后子代不如父代的退化現(xiàn)象，為個體更新提供優(yōu)化方向，只有進化的個體才有可能參與下一次迭代。

(3)更新外部檔案。交叉、變異、接種疫苗和免疫檢測等操作實現(xiàn)了個體更新，其中接種疫苗操作為個體更新提供了進化方向，并通過免疫檢測操作篩選了進化個體。在算法搜索過程中使用外部檔案保留精英解：計算初始種群的目標值，根據(jù)式(9)篩選出非劣解，并將其作為初始化的外部檔案，在迭代過程中，判斷新解與外部檔案中非劣解的支配關系，在外部檔案中剔除受支配解，同時保留非劣解以更新外部檔案。

(4)免疫平衡操作。隨著迭代次數(shù)的增加，外部檔案中高適應度抗體濃度不斷提高，為了平衡抗體的質量與多樣性，當抗體濃度達到設定閾值時，抑制高適應度抗體，而促進低適應度抗體。

抗體i、j的相似度Jij定義為

(10)

式中，R為相似度半徑。

第i個抗體濃度Ci定義為種群中的抗體與第i個抗體相似的抗體數(shù)目占種群規(guī)模N的比例，即

(11)

(12)

(13)

描述抗體適應度在種群總適應度的占比，第i個抗體的適應度概率

(14)

(15)

(16)

2.7算法流程

Pareto免疫遺傳算法求解DLBP的步驟如下。

(1)輸入待求解問題的參數(shù)：拆卸時間、單位時間拆卸成本和拆卸方向等相關信息、優(yōu)先關系矩陣A、節(jié)拍時間Tc、任務數(shù)目n。

(2)設定算法參數(shù)：種群規(guī)模N、最大迭代次數(shù)Gmax、交叉概率Pc、變異概率Pm、疫苗接種比例β、最大嘗試次數(shù)L、相似度半徑R和免疫選擇參數(shù)α，種群初始化，令外部檔案Q=?。

(3)構建疫苗庫，開始循環(huán)計數(shù)，令循環(huán)次數(shù)g=1。

(4)執(zhí)行交叉、變異等遺傳操作。

(5)判斷抗體是否需要接種疫苗，若需要則執(zhí)行接種疫苗操作，令接種疫苗次數(shù)l=1，否則轉至步驟(7)。

(6)執(zhí)行免疫檢測操作。計算接種疫苗操作前后抗體X1、X2的適應度，若X2X1，則保留子代，否則判斷嘗試次數(shù)是否滿足要求l

(7)更新外部檔案Q。

(8)執(zhí)行免疫平衡操作，計算外部檔案Q濃度概率Pd和適應度概率Pf。

(9)執(zhí)行免疫選擇算子，根據(jù)式(15)、式(16)分別計算高低濃度抗體的選擇概率Ps，執(zhí)行免疫選擇操作，更新種群。

(10)判斷循環(huán)次數(shù)g

Pareto免疫遺傳算法的流程如圖1所示。

圖1 Pareto免疫遺傳算法流程圖Fig.1 The flow chart of Pareto MIGA

3 算法驗證與應用

3.1算法驗證

文獻[2]研究了包含25項拆卸任務的某手機拆卸實例(P25問題)，考慮工作站數(shù)目M，空閑時間均衡指數(shù)I和需求指數(shù)D等多目標，具體為

(17)

(18)

現(xiàn)有求解P25問題的方法包括H-K算法[7]、單目標蟻群算法[7]、單目標粒子群算法[10]和多目標蟻群算法[11]，上述算法的結果見表2。

表2 現(xiàn)有算法求解P25問題的結果Tab.2 Solution of P25 of the existing algorithms

為便于比較算法性能，引用文獻[2]所提的3個目標函數(shù)。算法參數(shù)設置如下：N=200，Gmax=20，Pc=0.7，Pm=0.1，β=0.9，L=13，R=0.1，α=0.7。在計算機硬件配置為Intel(R) Pentium(R) CPU，主頻為2.90 GHz雙核，內存為2 GB，MATLAB R2010b環(huán)境下運行算法程序，可以求得10個非劣解的Pareto最優(yōu)解集，見表3。

對比上述5種算法，啟發(fā)式算法和H-K算法依據(jù)某一規(guī)則分配拆卸任務，所得結果與啟發(fā)式規(guī)則直接相關，無法同時優(yōu)化多個目標；單目標蟻群算法和單目標粒子群算法將多目標問題轉化為具有優(yōu)先順序的單目標問題，求解結果較為單一；多目標蟻群算法能求得多個互不占優(yōu)的分配方案。分析表2可知，單目標粒子群算法在求解P25問題時表現(xiàn)優(yōu)異：M=9，I= 9，D= 853，所得結果能支配上述4種方法的解；多目標蟻群算法能求解出包含兩個非劣解的Pareto解集。

對比表2與表3，MIGA算法可求出包含10個非劣解的Pareto解集，其中解1的工作站數(shù)目和空閑時間均衡指標與單目標粒子群算法的結果相同，但需求指標較優(yōu)，因此解1能支配上述5種算法的解；余下9個解中空閑時間均衡指標最小為11，需求指標最大為849，與單目標粒子群算法所求結果比較互不占優(yōu)。綜上所述，本文MIGA算法能夠求得多樣的、高質量的解，表明了所提MIGA算法的有效性。

表3 MIGA求解P25問題的結果Tab.3 The solution results of MIGA for P25

3.2實例應用

針對某型號打印機的拆卸回收工作，擬規(guī)劃一條專門的拆卸線。經實地調研得到打印機拆卸作業(yè)信息見表4，包括零件的拆卸時間t(s)、單位時間拆卸成本c(元/s)和拆卸方向r，各作業(yè)單元的拆卸優(yōu)先關系如圖2所示。

表4 打印機拆卸實例信息表Tab.4 Data information of the printer disassembly instance

圖2 打印機拆卸實例的優(yōu)先關系圖Fig.2 The precedence relationships graph of the printer disassembly instance

該打印機拆卸線的規(guī)劃產量是4500臺/月，每月工作30天，每天有效作業(yè)時間為6.5 h，總有效作業(yè)時間與規(guī)劃產量的商即為節(jié)拍時間Tt，經計算節(jié)拍時間Tt=156 s，假設每次方向改變所需的調整時間為2 s。

權衡搜索能力和收斂性能，經多次測算，將算法參數(shù)設置為：N=200，Gmax=40，Pc=0.7，Pm=0.1，β=0.9，L=28，R=0.1，α=0.7。運行MIGA求得3個非劣解，根據(jù)打印機拆卸線的平衡方案，可以計算出調整次數(shù)Ns、工作站數(shù)目M、周期時間Tc和產量，各平衡方案的指標見表5。

表5 打印機拆卸線三種平衡方案的指標Tab.5 The indicators for three balancing schemes ofprinter disassembly line

實際生產中，作業(yè)人員針對同一拆卸任務的作業(yè)時間不為定值，并且存在設備或零部件故障以致無法正常拆卸，需要花費額外的時間，采用特殊手段處理后才能繼續(xù)拆卸作業(yè)。為了確定上述情況是否會對平衡方案的生產能力產生較大影響，采用仿真的方法對方案進行模擬分析。

表6 方案1的拆卸任務分配情況(Tc=148 s)Tab.6 The disassembly task assignment of scheme 1(Tc=148 s)

4 仿真優(yōu)化

拆卸線規(guī)劃設計階段，由于尚未搭建拆卸線實體，難以驗證給定的平衡方案。若生產線投產后再對方案進行檢查，則會產生時間成本，同時耽誤生產進度，因此對平衡方案的預先評估顯得尤為重要。對于生產中可能出現(xiàn)的作業(yè)時間波動、設備或零部件故障等情況，采用Plant Simulation仿真軟件對拆卸線平衡方案進行仿真分析，動態(tài)掌握生產線的實際運行狀況，完善拆卸線的平衡設計。

4.1仿真建模

根據(jù)表6中的拆卸任務分配方案， 建立打印機拆卸線Plant Simulation仿真模型，如圖3所示。假設工作站Mm的作業(yè)時間服從均值為hm、方差為0.05hm的正態(tài)分布，結合“作業(yè)信息表Time”中工作站作業(yè)時間和調整時間，用封裝程序“時間設置Set_time”生成工作站的時間參數(shù)。此外，考慮到零部件損壞、設備故障等無法正常拆卸的故障情況，設置工作站出現(xiàn)故障的概率為4%，平均故障處理時間為2 min。

圖3 打印機拆卸線仿真模型Fig.3 The simulation model of the printer disassembly line

4.2仿真結果分析及改善

為便于數(shù)據(jù)統(tǒng)計，設定每天為連續(xù)作業(yè)，忽略產品在各工作站間的流轉時間，只有在上游工作站完成拆卸作業(yè)且下游工作站空閑時才能進行產品流轉，仿真時間設定為一個月(30天)。設置緩沖區(qū)前后工作站各狀態(tài)時間占比如圖4所示，工作站狀態(tài)包括工作、等待、堵塞和失效狀態(tài)。無緩存仿真模型的工作站各狀態(tài)時間占比如圖4a所示，具體數(shù)據(jù)見表7中無緩存值一欄，無緩存仿真模型的月拆卸產量為3855臺。

由圖4a和表7可知，作業(yè)時間的波動性及存在故障等實際情況，使得生產過程中出現(xiàn)了大量的堵塞與等待現(xiàn)象，且靠前的工作站堵塞現(xiàn)象較嚴重，靠后的工作站等待時間較長。為提高工作站的利用率，通過將圖3仿真模型的緩存區(qū)Bm連接到工作站Mm前來設置緩存區(qū)，其中工作站1緊挨供貨源，待拆卸產品持續(xù)供貨，不存在缺貨情況，故工作站1前未設置緩存區(qū)，而工作站2～5受相鄰工作站作業(yè)狀態(tài)的干擾，出現(xiàn)等待或堵塞情況，因此需要設置緩存區(qū)。

由于設置緩存區(qū)會導致拆卸線的在制品增多，增加企業(yè)的成本，因此必須在盡可能高的利用率和盡可能低的緩存區(qū)容量間作出權衡，在此采用仿真軟件內置的ExperimentManager控件進行多水平因子試驗設計，以確定每個緩存區(qū)的最佳容量。設置第i個緩存區(qū)的容量Ci從2變化到10且每次遞增2，共計625組試驗，由于作業(yè)時間不為定值，采取多次重復試驗取平均值的方法統(tǒng)計數(shù)據(jù)，重復次數(shù)設為10，置信水平設為95%，試驗結果如圖5所示，橫坐標表示試驗編號，縱坐標表示10次重復試驗的月平均拆卸產量。

(a)無緩存

(b)有緩存圖4 設置緩存區(qū)前后工作站各狀態(tài)時間百分比Fig.4 Percentage of each state of the workstation before and after setting cache

由圖5可知，縱坐標在水平線4500以上的點表示滿足產量要求的緩存區(qū)配比。E1最小配比2/2/2/2對應的月平均產出最小為4388臺，未達到產量規(guī)劃要求，但與未設置緩存區(qū)時相比多拆卸533臺，產量提高了13.8%，表明在工作站前增加緩存區(qū)可提高工作站利用率，從而增加產量。最大平均產量4515臺對應E370配比為6/10/8/10，產量極差為127臺。E625最大配比10/10/10/10對應的平均產量為4512臺，并不為所有結果中的最大值，由此說明將各緩存區(qū)全部設為最大容量的做法過于粗糙從而造成浪費。以規(guī)劃產量4500臺作為可接受的產出指標，總共有85組平均產量達標，其中有13組較低容量的緩存區(qū)容量配比見表8。

表7 理論作業(yè)狀態(tài)與有無緩存區(qū)仿真作業(yè)狀態(tài)時間占比Tab.7 The time proportion of the workstations in three different status %

圖5 多水平因子試驗結果Fig.5 Multilevel factor test results

EC2C3C4C5產量(臺)總容量(臺)標準差1904661045002614.641994610845012813.37223481064501289.772394106845012813.433006410104503309.81314666845022613.963236610645022812.6234368864502289.693596104845032815.064208481045043015.86459884845002813.00488810664504309.84568106864505309.51

使用總容量、標準差為評價目標，試驗E314、E343和E568為Pareto最優(yōu)解，綜合兩目標選擇E343的配比6/8/8/6為緩存區(qū)容量。設置仿真模型中的緩存區(qū)容量6/8/8/6，運行仿真模型可得工作站各狀態(tài)時間占比如圖4b所示，具體數(shù)據(jù)見表7中有緩存值一欄，月拆卸量為4512臺。

對比圖4和表7可知，設立緩存區(qū)后，工作站的平均利用率提高了17.17%，工作站內的堵塞與等待現(xiàn)象得到了顯著改善，堵塞率平均下降了33.36%，等待率平均下降了73.34%，產量提高了14.56%。仿真模型考慮了拆卸時間不確定及存在故障等因素，故該打印機拆卸線的月產量在一定范圍內波動。設置工作站的故障率為4%、故障處理時間為2 min、緩存區(qū)容量配比為6/8/8/6，置信水平為95%，運行10次，置信區(qū)間為[4495,4509]，仿真結果中月拆卸產量的波動范圍為[4483,4519]，標準差為9.69。

5 結論

(1)考慮調整時間，建立了以最小化拆卸成本、無效作業(yè)率和不平滑率為優(yōu)化目標的多目標帶調整時間拆卸線平衡問題模型，更加符合實際生產。

(2)針對拆卸線平衡問題的特點，提出了一種基于Pareto思想的免疫遺傳算法，引入接種疫苗操作、免疫檢測操作、免疫平衡操作和免疫選擇操作等免疫機制，提高了算法的搜索能力。經測試，所提算法在求解DLBP時表現(xiàn)優(yōu)異。

(3)考慮了服從正態(tài)分布的隨機拆卸時間及存在故障率的拆卸過程，采用Plant Simulation軟件建模仿真，針對該條件下產量不達標問題，通過增加緩存區(qū)來改善生產過程，運用多因子水平試驗方法確定緩存區(qū)最優(yōu)配比，最后仿真結果表明了所設計拆卸線方案的有效性。

[1] GUNGOR A, GUPTA S M. Disassembly Line in Product Recovery[J]. International Journal of Production Research,2002,40(11):2569-2589.

[2] GUPTA S M, MCGOVERN S M. Disassembly Sequencing Problem: a Case Study of a Cell Phone[C]// Proceedings of the 2004 SPIE International Conference on Environmentally Conscious Manufacturing. Bellingham, USA: SPIE,2004:43-52.

[3] MCGOVERN S M, GUPTA S M. 2-opt Heuristic for the Disassembly Line Balancing Problem[C]//Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing III. Bellingham, USA: SPIE,2004:71-84.

[4] KOC A, SABUNCUOGLU I, EREL E. Two Exact Formulations for Disassembly Line Balancing Problems with Task Precedence Diagram Construction Using an AND/OR Graph[J]. IIE Transactions,2009,41(10):866-881.

[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] ZHANG Z F, FENG Y X, TAN J R, et al. A Novel Approach for Parallel Disassembly Design Based on a Hybrid Fuzzy-time Model[J]. Journal of Zhejiang Universityence A,2015,16(9):724-736.

[7] MCGOVERN S M, GUPTA S M. Uninformed and Probabilistic Distributed Agent Combinatorial Searches for the Unary NP-complete Disassembly Line Balancing Problem[C]//Proceedings of SPIE-The International Society for Optical Engineering. Bellingham, USA: SPIE,2005:81-92.

[8] 朱興濤, 張則強, 朱勛夢, 等. 求解多目標拆卸線平衡問題的一種蟻群算法[J]. 中國機械工程,2014,25(8):1075-1079. ZHU Xingtao, ZHANG Zeqiang, 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.

[9] KALAYCI C B, GUPTA S M. Artificial Bee Colony Algorithm for Solving Sequence-dependent Disassembly Line Balancing Problem[J]. Expert Systems with Applications,2013,40(18):7231-7241.

[10] KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm with Neighborhood-based Mutation for Sequence-dependent Disassembly Line Balancing Problem[J]. Proceedings for the Northeast Region Decision Sciences Institute,2013,69(1/4):197-209.

[11] 丁力平, 譚建榮, 馮毅雄, 等. 基于Pareto蟻群算法的拆卸線平衡多目標優(yōu)化[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.

[12] MCGOVERN S M, GUPTA S M. Ant Colony Optimization for Disassembly Sequencing with Multiple Objectives[J]. International Journal of Advanced Manufacturing Technology,2006,30(5/6):481-496.

[13] 湯洪濤, 丁彬楚, 李修琳,等. 基于改進免疫遺傳算法的混合車間調度研究[J]. 中國機械工程,2014,25(9):1189-1194. TANG Hongtao, DING Binchu, LI Xiulin. Improved Immune Genetic Algorithm for Mixed-model Scheduling Problem[J]. China Mechanical Engineering,2014,25(9):1189-1194.

[14] PAN G, LI K, OUYANG A, et al. Hybrid Immune Algorithm Based on Greedy Algorithm and Delete-cross Operator for Solving TSP[J]. Soft Computing,2016,20(2):1-12.

[15] GHOSH T, DOLOI B, DAN P K. An Immune Genetic Algorithm for Inter-cell Layout Problem in Cellular Manufacturing System[J]. Production Engineering,2015,10(2):1-18.

(編輯王艷麗)

OptimizationofDisassemblyLineBalancingProblemswithSetupTimesBasedon
Multi-objectiveAlgorithmandDynamicSimulation

LI Liuke ZHANG Zeqiang HU Yang ZOU Binsen

School of Mechanical Engineering, SouthwestJiaotong University, Chengdu, 610031

In view of the influences of disassembly direction changes on operation times, a multi-objective model of disassembly line balancing problem considering the setup times was established involving three optimization objectives, i.e. minimizing the disassembly costs, minimizing the invalid work rates and minimizing the non-smooth rates. And a Pareto immune genetic algorithm integrated with the simulation technology was proposed. The proposed algorithm introduced the genetic operator and the immune operator which might avoid the local optimum and ensure the global convergence. The proposed algorithm was applied to a 25-task disassembly case, the results of which indicate the effectiveness of the proposed algorithm by comparing with the other 5 algorithms. Further, the proposed model and the algorithm were applied to design a printer disassembly line. Finally, considering the uncertainty of the disassembly times and failures in the actual disassembly productions, simulation technology was used to analyze and optimize the disassembly line. And the simulation results show that the proposed method may effectively reduce the invalid times caused by waiting and blocking and improve the disassembly efficiency.

disassembly line balancing problem; multi-objective optimization; setup time; immune genetic algorithm; simulation

2016-10-17

國家自然科學基金資助項目(51205328，51405403)；教育部人文社會科學研究青年基金資助項目(12YJCZH296)；四川省應用基礎研究計劃資助項目(2014JY0232)

TH165

10.3969/j.issn.1004-132X.2017.17.016

李六柯，男，1993年生。西南交通大學機械工程學院碩士研究生。主要研究方向為生產線平衡與智能優(yōu)化。張則強(通信作者)，男，1978年生。西南交通大學機械工程學院教授、博士研究生導師。E-mail：zzq_22@163.com。胡揚，男，1990年生。西南交通大學機械工程學院碩士。鄒賓森，男，1990年生。西南交通大學機械工程學院碩士研究生。