李六柯 張則強(qiáng) 胡 揚(yáng) 鄒賓森

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

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

李六柯 張則強(qiáng) 胡 揚(yáng) 鄒賓森

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

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

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

0 引言

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

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

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

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

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

1.1符號(hào)說(shuō)明

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

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

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

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

(1)

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

(2)

(3)

(4)

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

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

F=min(f1,f2,f3)

(5)

約束條件

(6)

(7)

Tc≤Tt

(8)

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

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

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

2.1Pareto解集

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

(9)

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

2.2編碼和解碼方法

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

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

2.3種群初始化

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

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

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

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

表1 解碼操作過(guò)程Tab.1 The decode operation

2.4構(gòu)建疫苗庫(kù)

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

2.5遺傳算子

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

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

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

2.6免疫算子

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

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

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

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

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

(10)

式中，R為相似度半徑。

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

(11)

(12)

(13)

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

(14)

(15)

(16)

2.7算法流程

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

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

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

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

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

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

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

(7)更新外部檔案Q。

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

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

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

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

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

3 算法驗(yàn)證與應(yīng)用

3.1算法驗(yàn)證

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

(17)

(18)

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

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

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

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

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

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

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

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

表4 打印機(jī)拆卸實(shí)例信息表Tab.4 Data information of the printer disassembly instance

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

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

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

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

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

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

4 仿真優(yōu)化

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

4.1仿真建模

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

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

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

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

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

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

(a)無(wú)緩存

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

[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] 朱興濤, 張則強(qiáng), 朱勛夢(mèng), 等. 求解多目標(biāo)拆卸線平衡問(wèn)題的一種蟻群算法[J]. 中國(guó)機(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]. 計(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.

[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ìn)免疫遺傳算法的混合車(chē)間調(diào)度研究[J]. 中國(guó)機(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

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

TH165

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

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