李六柯 張則強 胡 揚 鄒賓森

西南交通大學(xué)機械工程學(xué)院，成都，610031

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

李六柯 張則強 胡 揚 鄒賓森

西南交通大學(xué)機械工程學(xué)院，成都，610031

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

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

0 引言

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

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

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

1 考慮調(diào)整時間的多目標(biāo)DLBP模型

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

1.1符號說明

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

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

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

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

(1)

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

(2)

(3)

(4)

考慮調(diào)整時間的多目標(biāo)拆卸線平衡問題模型如下：

目標(biāo)函數(shù)

F=min(f1,f2,f3)

(5)

約束條件

(6)

(7)

Tc≤Tt

(8)

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

2 Pareto免疫遺傳算法設(shè)計

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

2.1Pareto解集

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

(9)

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

2.2編碼和解碼方法

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

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

2.3種群初始化

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

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

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

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

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

2.4構(gòu)建疫苗庫

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

2.5遺傳算子

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

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

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

2.6免疫算子

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

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

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

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

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

(10)

式中，R為相似度半徑。

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

(11)

(12)

(13)

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

(14)

(15)

(16)

2.7算法流程

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

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

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

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

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

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

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

(7)更新外部檔案Q。

(8)執(zhí)行免疫平衡操作，計算外部檔案Q濃度概率Pd和適應(yīng)度概率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 算法驗證與應(yīng)用

3.1算法驗證

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

(17)

(18)

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

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

為便于比較算法性能，引用文獻[2]所提的3個目標(biāo)函數(shù)。算法參數(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雙核，內(nèi)存為2 GB，MATLAB R2010b環(huán)境下運行算法程序，可以求得10個非劣解的Pareto最優(yōu)解集，見表3。

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

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

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

3.2實例應(yīng)用

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

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

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

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

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

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

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

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

4 仿真優(yōu)化

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

4.1仿真建模

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

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

4.2仿真結(jié)果分析及改善

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

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

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

(a)無緩存

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

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

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

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

EC2C3C4C5產(chǎn)量(臺)總?cè)萘?臺)標(biāo)準(zhǔn)差1904661045002614.641994610845012813.37223481064501289.772394106845012813.433006410104503309.81314666845022613.963236610645022812.6234368864502289.693596104845032815.064208481045043015.86459884845002813.00488810664504309.84568106864505309.51

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

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

5 結(jié)論

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

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

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

[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] 朱興濤, 張則強, 朱勛夢, 等. 求解多目標(biāo)拆卸線平衡問題的一種蟻群算法[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蟻群算法的拆卸線平衡多目標(biāo)優(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] 湯洪濤, 丁彬楚, 李修琳,等. 基于改進免疫遺傳算法的混合車間調(diào)度研究[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

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

TH165

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

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