雙邊拆卸線平衡問題建模與優(yōu)化

鄒賓森 張則強(qiáng) 李六柯 蔡 寧

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

0 引言

在當(dāng)今資源日益匱乏的背景下，產(chǎn)品回收再制造因其節(jié)能環(huán)保的優(yōu)良特性，受到了世界各國的重視。近年來，國家相關(guān)機(jī)構(gòu)出臺了《再生資源回收體系建設(shè)中長期規(guī)劃（2015～2020年）》等一系列政策法規(guī)，以推進(jìn)再制造行業(yè)的良好發(fā)展，拆卸作為從資源回收到再利用中重要的一步，受到了國內(nèi)外學(xué)者廣泛的研究和關(guān)注。

為保證拆卸作業(yè)高效流暢地進(jìn)行，當(dāng)前規(guī)?；牟鹦吨饕捎貌鹦毒€的作業(yè)形式，拆卸線具有效率高、節(jié)約生產(chǎn)空間等優(yōu)點(diǎn)，但在拆卸作業(yè)中當(dāng)任務(wù)在工作站內(nèi)分配不合理時(shí)會(huì)帶來拆卸線平衡問題（disassembly line balancing problem，DLBP）。

GUNGOR等［1］最先建立了多目標(biāo)DLBP數(shù)學(xué)模型以優(yōu)化拆卸生產(chǎn)線。結(jié)合實(shí)際生產(chǎn)情況，學(xué)者對DLBP模型進(jìn)行了拓展和完善。針對實(shí)際拆卸作業(yè)中復(fù)雜的工況和不確定性，KALAYCI等［2］對模糊環(huán)境下的DLBP展開了研究。結(jié)合U形布局節(jié)約生產(chǎn)空間、減低物流輸送成本的優(yōu)點(diǎn)，AGRAWAL等［3］建立了U形布局的DLBP模型。KALAYCILAR等［4］建立了工作站數(shù)固定、節(jié)拍時(shí)間不定的DLBP數(shù)學(xué)模型，以體現(xiàn)待拆卸零件特定限制供應(yīng)的工況。由于DLBP求解的復(fù)雜性，因而DLBP的求解方法成為學(xué)術(shù)研究重點(diǎn)。已有的DLBP求解方法包括變鄰域搜索［5］、強(qiáng)化學(xué)習(xí)算法［6］、貪婪算法［7］等啟發(fā)式方法，但因 DLBP 的NP-hard屬性，上述算法針對大規(guī)模DLBP無法在合理的時(shí)間內(nèi)求得理想的解。結(jié)合智能方法參數(shù)少、效率高的優(yōu)點(diǎn)，粒子群算法［8］、遺傳算法［9］和人工蜂群算法［10］等被廣泛應(yīng)用于求解DLBP，但這些方法均是將多目標(biāo)DLBP轉(zhuǎn)換為單目標(biāo)問題進(jìn)行求解，喪失了解的多樣性。為保證多目標(biāo)問題解的多樣性，文獻(xiàn)［11-12］分別提出了基于Pareto的蟻群算法和人工魚群算法，一次運(yùn)算能求得多種平衡方案，但其求解性能仍有待進(jìn)一步提升。

對于大型或受作業(yè)方位約束的產(chǎn)品，若采用傳統(tǒng)的單邊作業(yè)形式，拆卸中作業(yè)產(chǎn)品需要頻繁地調(diào)整方向，會(huì)產(chǎn)生大量的無效操作和降低生產(chǎn)效率，而采用雙邊作業(yè)形式能有效減少因作業(yè)方位約束導(dǎo)致的無用功［13-15］，從而提高作業(yè)效率、降低生產(chǎn)成本。

蝙蝠算法（bat algorithm，BA）［16］因具有算法參數(shù)少、收斂速度快和收斂精度高等優(yōu)點(diǎn)［17］，一經(jīng)提出便倍受關(guān)注，被廣泛地應(yīng)用于求解車間調(diào)度問題［18］、發(fā)電系統(tǒng)成本優(yōu)化［19］以及其他多目標(biāo)優(yōu)化問題［20］，均取得了良好的求解結(jié)果，表明蝙蝠算法在求解離散問題及多目標(biāo)問題上具有優(yōu)良的求解性能。但目前尚未有將蝙蝠算法用于求解DLBP的公開報(bào)道，因此將蝙蝠算法應(yīng)用于求解DLBP具有重要的研究價(jià)值。

本文對雙邊拆卸線平衡問題（two-sided disas?sembly line balancing problem，TDLBP）展開了研究，建立了多目標(biāo)TDLBP數(shù)學(xué)模型。針對所建立的TDLBP數(shù)學(xué)模型，提出一種基于Pareto的蝙蝠算法進(jìn)行求解。

1 雙邊拆卸線平衡問題

當(dāng)前DLBP研究中，如圖1所示，均假定工作站布置在輸送帶的同側(cè)，尚未有雙邊拆卸線平衡問題的公開研究報(bào)道，但經(jīng)實(shí)地調(diào)研后發(fā)現(xiàn)，雙邊拆卸被廣泛地應(yīng)用于實(shí)際拆卸作業(yè)中。圖2為雙邊拆卸線示意圖。

圖1 單邊拆卸線示意圖Fig.1 The schematic diagram of the one-sided disassembly line

如圖2所示，雙邊拆卸線中，工作站布置在輸送帶的左右兩側(cè)，在滿足拆卸優(yōu)先關(guān)系的前提下，左右兩邊可同時(shí)進(jìn)行拆卸作業(yè)。按零部件的拆卸方位約束，將零部件分為L、R、E三類。其中標(biāo)記L的任務(wù)只能在拆卸線左側(cè)工作站內(nèi)進(jìn)行拆卸；標(biāo)記R的任務(wù)只能在拆卸線右側(cè)工作站內(nèi)進(jìn)行拆卸；標(biāo)記E的任務(wù)在拆卸線左右兩側(cè)均可進(jìn)行拆卸。

圖2 雙邊拆卸線示意圖Fig.2 The schematic diagram of the two-sided disassembly line

理論假設(shè)：①相同產(chǎn)品的同一零部件的拆卸時(shí)間固定且相同；②雙邊同時(shí)作業(yè)時(shí)互不干擾。

符號說明：N為開啟的工作站數(shù)目；j為拆卸工作站編號；CT為拆卸生產(chǎn)節(jié)拍；STj為工作站 j的拆卸作業(yè)時(shí)間；l為分配至左側(cè)工作站中的拆卸序列編號；r為分配至右側(cè)工作站中的拆卸序列編號；nL為分配至左側(cè)工作站的任務(wù)總數(shù)；nR為分配至右側(cè)工作站的任務(wù)總數(shù)；為分配至左側(cè)工作站的拆卸序列中第l處的拆卸任務(wù)；為分配至右側(cè)工作站的拆卸序列中第r處的拆卸任務(wù)；dkL為任務(wù)的需求指數(shù)，若任務(wù)l拆卸的零部件定義為有需求零部件，根據(jù)零件的需求程度，dkL取大于零的整數(shù)，若任務(wù)拆卸l的零部件無需求價(jià)值，則為任務(wù)的危害指數(shù)，若任務(wù)klL拆卸的零部件定義為有害零部件，則hkL=1，否則 hkL=0；n為拆卸任務(wù)總數(shù)；li為拆卸任務(wù)編號；ti為任務(wù)i拆卸所需時(shí)間；WTj為工作站 j的等待時(shí)間；Ti為任務(wù)i的開始拆卸時(shí)刻；aii?為任務(wù)優(yōu)先關(guān)系，當(dāng)任務(wù)i優(yōu)先于任務(wù)i?時(shí)，則 aii?=1，否則 aii?=0 ；P 為任務(wù)優(yōu)先關(guān)系矩陣，P=[aii?]n×n；mi為任務(wù) i的拆卸方位屬性，當(dāng)任務(wù)i只能在生產(chǎn)線左邊拆卸時(shí)，mi={1}，當(dāng)任務(wù)i只能在生產(chǎn)線右邊拆卸時(shí)，mi={2}，任務(wù)i在生產(chǎn)線左右兩側(cè)均可拆卸時(shí)，mi={1，2}；zj為工作站 j的方位屬性，當(dāng)工作站 j布置在生產(chǎn)線左側(cè)時(shí)，zj=1，當(dāng)工作站 j布置在生產(chǎn)線右側(cè)時(shí)，zj=2；eij為拆卸任務(wù)分配屬性，當(dāng)任務(wù)i被分配到工作站 j中且 zj∈mi時(shí)，eij=1，否則eij=0。

目標(biāo)函數(shù)如下［6］：

約束條件如下：作站數(shù)目和最大工作站數(shù)目n之間。式（7）約束工作站作業(yè)時(shí)間與等待時(shí)間之和不超過生產(chǎn)節(jié)拍。式（8）確保拆卸滿足優(yōu)先關(guān)系。式（9）確保每一個(gè)零件均被拆卸且只能被分配在一個(gè)工作站內(nèi)進(jìn)行拆卸。

式（2）為開啟的工作站數(shù)目，為降低拆卸成本，應(yīng)最小化開啟的工作站數(shù)目。式（3）為拆卸線空閑時(shí)間指標(biāo)，為使工作站閑置時(shí)間最短和提高拆卸效率，應(yīng)最小化拆卸空閑時(shí)間指標(biāo)。式（4）為拆卸需求指標(biāo)，為盡可能早地拆卸需求價(jià)值高的零件，應(yīng)最小化拆卸需求指標(biāo)。式（5）為拆卸危害指標(biāo)，為盡可能降低有害零部件在拆卸過程中對環(huán)境的污染和對工人健康的損害，應(yīng)最小化拆卸危害指標(biāo)。式（6）約束實(shí)際開啟工作站數(shù)目介于最小工

2 Pareto蝙蝠算法

2.1 編碼

基于DLBP特性，本文采用拆卸序列進(jìn)行編碼。為保證算法能在盡可能大的空間內(nèi)進(jìn)行搜索尋優(yōu)以及避免人為因素對初始種群的影響，采用隨機(jī)產(chǎn)生的滿足優(yōu)先關(guān)系的拆卸序列作為初始種群。以包含5個(gè)任務(wù)的算例為例簡述初始種群個(gè)體的產(chǎn)生過程，該算例任務(wù)優(yōu)先關(guān)系如圖3所示。初始，可選任務(wù)集為｛1｝，因此選任務(wù)1為第一個(gè)拆卸任務(wù)，解除任務(wù)1的緊前性質(zhì)，可選任務(wù)集更新為｛2，5，3｝；隨機(jī)選取任務(wù)5作為第二個(gè)拆卸任務(wù)，解除任務(wù)5的緊前性質(zhì)，可選任務(wù)集更新為｛2，3｝；隨機(jī)選取任務(wù)2作為第三個(gè)任務(wù)，解除任務(wù)2的緊前性質(zhì)，可選任務(wù)集合更新為｛3，4｝；隨機(jī)選取任務(wù)4作為第四個(gè)拆卸任務(wù)；最后剩下的任務(wù)3作為第五個(gè)拆卸任務(wù)，得到一個(gè)初始個(gè)體即拆卸序列為｛1，5，2，4，3｝。

圖3 算例優(yōu)先關(guān)系圖Fig.3 The precedence diagram of the example

2.2 蝙蝠算法

借鑒蝙蝠精準(zhǔn)的捕食行為，將算法尋優(yōu)過程模擬為蝙蝠捕食過程。將獵物模擬為解空間中的可行解，將搜索和尋優(yōu)過程中用適應(yīng)度高的解替代適應(yīng)度低的解的迭代過程，類比為個(gè)體的優(yōu)勝劣汰過程。

蝙蝠算法中，當(dāng)rand1≤sq時(shí)，蝙蝠算法采用速度-位置模型對個(gè)體進(jìn)行更新，其中，rand1為［0，1］之間的隨機(jī)數(shù)，sq為第q只蝙蝠個(gè)體的脈沖頻度。

速度更新：

式中，(t+1)為第t+1次迭代中第q只蝙蝠的第d位的速度分量；(t)為第q只蝙蝠的第d位的位置分量；為當(dāng)前最優(yōu)位置的第d位位置分量；f為第q個(gè)q個(gè)體的脈沖頻率；fmin、fmax分別為脈沖頻率的最小值和最大值；rand2為［0，1］之間的隨機(jī)數(shù)。

拆卸線平衡問題是一個(gè)離散問題，因此將蝙蝠算法應(yīng)用于求解拆卸線平衡問題時(shí)需將算法離散化?？紤]拆卸線平衡問題采用拆卸序列編碼的特性，定義位置之差為兩個(gè)解對應(yīng)序列位置的不同任務(wù)的任務(wù)數(shù)組。如若 x1(t)=｛1，3，2，5，4｝、x2(t)=｛3，5，2，4，1｝，則可知、=3，則=｛1，3｝，每相減一次將 x2(t)中的對應(yīng)拆卸任務(wù)交換位置以更新x2(t)，即可知x1(t)-x2(t)=｛1，3，2，5，4｝-｛1，5，2，4，3｝+｛｛1，3｝｝=｛1，3，2，5，4｝-｛1，3，2，4，5｝+｛｛1，3｝，｛3，5｝｝=｛1，3，2，5，4｝-｛1，3，2，5，4｝+｛｛1，3｝，｛3，5｝，｛4，5｝｝=｛｛1，3｝，｛3，5｝，｛4，5｝｝=v 。定義 fq為(xq(t)-xbest(t))中實(shí)際參與速度更新的長度比例：若 vq(t)=｛｛1，2｝｝，(xq(t)-xbest(t))=｛｛2，3｝，｛3，4｝，｛4，5｝｝，fq=0.5，因｛｛2，3｝，｛3，4｝，｛4，5｝｝長度為3，則(xq(t)-xbest(t))中實(shí)際參與速度更新的對數(shù)為對，隨機(jī)取兩組｛｛2，3｝，｛3，4｝｝，則 vq(t+1)=vq(t)+(xq(t)-xbest(t))fq=｛｛1，2｝｝+｛｛2，3｝，｛3，4｝｝=｛｛1，2｝，｛2，3｝，｛3，4｝｝。

位置更新：

定義位置與速度相加為對原拆卸序列中的任務(wù)按速度數(shù)組進(jìn)行交換。如若 x2(t)=｛3，5，2，4，1｝、v=｛｛1，3｝，｛3，5｝，｛4，5｝｝，x2(t)與速度 v 中速度分量｛｛1，3｝｝相加表示將 x2(t)中任務(wù)1和任務(wù)3的位置互換，則 x2(t)+v=｛3，5，2，4，1｝+｛｛1，3｝，｛3，5｝，｛4，5｝｝=｛1，5，2，4，3｝+｛｛3，5｝，｛4，5｝｝=｛1，3，2，4，5｝+｛｛4，5｝｝=｛1，3，2，5，4｝。

蝙蝠算法中，當(dāng)rand1＞sq時(shí)，在當(dāng)前全局最優(yōu)附近進(jìn)行隨機(jī)搜索以尋找新的位置。鑒于拆卸線中優(yōu)先關(guān)系的存在，本文采用如下方式對當(dāng)前全局最優(yōu)進(jìn)行隨機(jī)搜索：從全局最優(yōu)中隨機(jī)選擇一個(gè)任務(wù)，將所選任務(wù)隨機(jī)插入到最近的緊前任務(wù)和最近的緊后任務(wù)之間，完成局部搜索。局部搜索如圖4所示。

圖4 局部搜索示意圖Fig.4 The schematic diagram of the loach search

蝙蝠算法中，當(dāng)個(gè)體新位置優(yōu)于原位置則接受新位置；若個(gè)體新位置劣于原位置且rand3＜Aq時(shí)，接受新位置以避免算法陷入局部最優(yōu)，其中rand3為［0，1］之間隨機(jī)數(shù)，Aq為第q只蝙蝠個(gè)體的脈沖音強(qiáng)。較小的脈沖音強(qiáng)能保證接受劣于當(dāng)前位置的新位置的概率越來越小。為更精準(zhǔn)地掌握目標(biāo)位置，隨著算法的不斷進(jìn)行，當(dāng)個(gè)體更新后優(yōu)于當(dāng)前全局最優(yōu)時(shí)，采用下式不斷增大脈沖頻度sq和減小脈沖音強(qiáng)Aq：

式中，sq(0)為初始脈沖頻度；γ為脈沖頻度增加系數(shù)，一般為一個(gè)大于零的常數(shù)；α為脈沖音強(qiáng)衰減系數(shù)。

2.3 解碼方式

TDLBP中，解的產(chǎn)生還需要對可行拆卸序列進(jìn)行解碼，為縮短工件在輸送帶上的輸送路徑以及使工作站內(nèi)空閑時(shí)間最短，本文在解碼中對于不受拆卸方位約束的任務(wù)優(yōu)先分配至開啟工作站較少的一邊，當(dāng)兩邊工作站開啟數(shù)目相同時(shí)，優(yōu)先將任務(wù)分配至空閑時(shí)間較多的工作站內(nèi)。具體解碼方式如圖5所示。其中，jL為左側(cè)當(dāng)前開啟的工作站編號；jR為右側(cè)當(dāng)前開啟的工作站編號；RjL為工作站 jL的剩余時(shí)間。

圖5 解碼方式Fig.5 The decoding method

2.4 Pareto非劣解

若最小化多目標(biāo)問題中可行解u和u?滿足：

則稱 uPareto支配 u?，記為 u?u?。如 F(u)=｛6，20，15，4｝，F(xiàn)(u?)=｛7，20，26，6｝，因?qū)τ??d ∈{1，2，3，4}， Fd(u)≤Fd(u?) 均 成 立 ；且 當(dāng) d=1 時(shí) ，F(xiàn)d(u)=6，F(xiàn)d(u?)=7，F(xiàn)d(u)＜ Fd(u?)成立，因此可知u?u?。解空間中不被支配的解稱為Pareto最優(yōu)解或非劣解，所有非劣解組成的集合稱為Pare?to最優(yōu)解集，對應(yīng)的目標(biāo)函數(shù)值稱為Pareto最優(yōu)前沿。

2.5 外部檔案更新

算法每迭代完成一次，將外部檔案中非劣解與當(dāng)前種群進(jìn)行一次Pareto比較，篩選出兩者合集的非劣解保存至外部檔案中，以確保外部檔案中的非劣解始終為當(dāng)前全局非劣解。如外部檔案Q={x3，x4}，當(dāng)前種群 X={x5，x6}，其中 x3、x4互不支配，x5支配 x4、x6，且 x5與 x3互不支配。外部檔案和當(dāng)前種群合集為 {x3，x4，x5，x6}，則可知外部檔案和當(dāng)前種群合集的非劣解集為{x3，x5}，因此外部檔案 Q 更新為{x3，x5}。

多目標(biāo)問題的解是多個(gè)互不占優(yōu)的非劣解，規(guī)模往往較大，但外部檔案規(guī)模過大則會(huì)降低算法運(yùn)行速度。為提高算法運(yùn)行效率和讓更具代表性的非劣解參與尋優(yōu)以加強(qiáng)算法尋優(yōu)能力，當(dāng)外部檔案大小超過設(shè)定規(guī)模時(shí)需對外部檔案進(jìn)行篩選，本文采用基于擁擠距離的外部檔案篩選方式［21］，依次剔除擁擠距離小的個(gè)體，直到外部檔案大小等于設(shè)定規(guī)模。采用精英策略，用外部檔案中的非劣解替換當(dāng)前種群中的部分個(gè)體參與算法迭代尋優(yōu)，加速算法的收斂。

2.6 算法步驟

（1）算法初始化：種群規(guī)模M ，脈沖頻率搜索范圍 fmin、fmax，最大脈沖頻度s，最大脈沖音強(qiáng) A，脈沖頻度增加系數(shù)γ，脈沖音強(qiáng)衰減系數(shù)α，算法最大迭代次數(shù)gmax，外部檔案規(guī)模 fN。

（2）算法當(dāng)前迭代次數(shù)Tc=1。

（3）外部檔案集初始化，令外部檔案集為空集。

（4）種群初始化。

（5）若rand 1＞sq，則對當(dāng)前最優(yōu)個(gè)體產(chǎn)生一個(gè)隨機(jī)擾動(dòng)，產(chǎn)生新個(gè)體 xnew；否則采用式（12）產(chǎn)生新個(gè)體xnew。

（6）若新個(gè)體優(yōu)于原個(gè)體，則用新個(gè)體替換原個(gè)體，轉(zhuǎn)至步驟（8）；否則轉(zhuǎn)至下一步。

（7）若rand 3＜Aq，則用新個(gè)體替換原個(gè)體。

（8）若更新后個(gè)體優(yōu)于當(dāng)前全局最優(yōu)，則更新 Aq和sq；否則轉(zhuǎn)至下一步。

（9）更新外部檔案。

（10）

（11）若Tc＞gmax，則執(zhí)行下一步；否則轉(zhuǎn)至步驟（5）。

（12）輸出外部檔案集。

（13）算法結(jié)束。

蝙蝠算法流程如圖6所示。

圖6 蝙蝠算法流程圖Fig.6 The flow diagram of BA

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

為驗(yàn)證算法的有效性，將模型應(yīng)用于實(shí)際拆卸線規(guī)劃中，本文在配置為 Inter（R）Core（TM）i3-2100 CPU@3.10GHz，4.00GB內(nèi)存的計(jì)算機(jī)上，在Win7系統(tǒng)下采用MATLAB R2014b開發(fā)了所提生算法的實(shí)驗(yàn)程序。

3.1 算法驗(yàn)證

已有的多目標(biāo)DLBP研究中，尚無雙邊布局的模型實(shí)例，因此無法通過求解雙邊拆卸模型驗(yàn)證算法的有效性。但已有的直線形DLBP是雙邊布局中某一邊開啟的工作站數(shù)目為0的一種特殊情況，與TDLBP相比，只在于解碼方式的不同，不會(huì)影響算法的結(jié)構(gòu)進(jìn)而不會(huì)影響算法的求解性能，因此通過求解直線形DLBP驗(yàn)證所提算法的有效性是可行的。

為驗(yàn)證算法的有效性，將蝙蝠算法應(yīng)用于求解移動(dòng)電話機(jī)拆卸實(shí)例［8］，該算例包含25個(gè)拆卸任務(wù)（以下簡稱“P25”），其中生產(chǎn)節(jié)拍CT=18，優(yōu)化目標(biāo)為 min(F1，F(xiàn)2，F(xiàn)3，F(xiàn)4)，該算例任務(wù)作業(yè)時(shí)間和任務(wù)優(yōu)先關(guān)系圖詳見文獻(xiàn)［8］。該算例的已有求解方法包括遺傳算法（GA）［9］、模擬退火算法（SA）［22］、粒子群優(yōu)化算法（PSO）［8］、強(qiáng)化學(xué)習(xí)算法（RL）［6］、變鄰域搜索（VNS）［5］以及人工魚群算法（AFSA）［12］。上述6種算法求解結(jié)果如表1所示。

表1 6種算法對P25求解結(jié)果Tab.1 The solutions of P25 of six algorithms

為保證算法最大的求解效率和最好的求解性能，經(jīng)多次測試對比后，蝙蝠算法參數(shù)設(shè)置如下：種群規(guī)模M=180，脈沖頻率搜索范圍 fmin=0，fmax=1.2，最大脈沖頻度s=0.6，最大脈沖音強(qiáng)A=0.85，脈沖頻度增加系數(shù)γ=0.03，脈沖音強(qiáng)衰減系數(shù)α=0.9，算法最大迭代次數(shù) gmax=200，外部檔案規(guī)模 fN=8，算法運(yùn)行30次，平均每次運(yùn)行時(shí)間為34.956 s，其中一次運(yùn)行結(jié)果如表2所示。

表2 蝙蝠算法對P25求解結(jié)果Tab.2 The solutions of P25 of bat algorithms

對比分析表1和表2可知，方案4和方案6完全優(yōu)于GA、SA、PSO、RL的求解結(jié)果，方案1～方案3、方案5、方案7和方案8與上述4種算法求解結(jié)果互不占優(yōu)，但上述4種算法沒有一種求解結(jié)果優(yōu)于本文算法；因此可知本文算法優(yōu)于上述4種算法。VNS求解結(jié)果與方案6相同，與其余7種方案互不占優(yōu)，但本文算法一次能求得多種平衡方案，同時(shí) F3指標(biāo)上能求得更優(yōu)的 807、823、802、819，在F4指標(biāo)能求得更優(yōu)的 70、72、73；因此可知本文算法優(yōu)于VNS。本文算法一次運(yùn)算能求得多種平衡方案，且在F3指標(biāo)和F4指標(biāo)能求得更優(yōu)異的值。

文獻(xiàn)［12］采用人工魚群算法對P25進(jìn)行了求解，一次求得了8個(gè)平衡方案，對比蝙蝠算法求解結(jié)果和AFSA求解結(jié)果。AFSA所求得前兩個(gè)平衡方案與本文所求得的方案6和方案4相同，其余方案與本文所求方案都互不占優(yōu)。對比單個(gè)目標(biāo)的求解結(jié)果可知，本文在F3指標(biāo)上所求得的最小值為802，優(yōu)于AFSA所求得的最小值809；本文在F4指標(biāo)上所求得的最小值為70，優(yōu)于AFSA所求得的最小值72。由此可知雖兩種算法求解結(jié)果互不占優(yōu)，但是本文算法在F3指標(biāo)和F4指標(biāo)上能求得更優(yōu)的值，能為決策者在F3指標(biāo)和F4指標(biāo)上提供更優(yōu)良的參考，即可知本文所提算法優(yōu)于AFSA。通過上述對比，驗(yàn)證了本文所提算法的有效性。

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

采用某公司某型號電冰箱拆卸作為求解算例以驗(yàn)證本文所提出模型和算法實(shí)際應(yīng)用情況。針對該型號電冰箱拆卸流水線，采用多次秒表測量并取整的方式，得到表3中各任務(wù)作業(yè)時(shí)間，結(jié)合該型號電冰箱材料屬性與市場需求，制訂了各任務(wù)的需求和危害指標(biāo)。結(jié)合實(shí)際生產(chǎn)情況，給定生產(chǎn)節(jié)拍CT=130 s。

表3 冰箱拆卸信息表Tab.3 The information of the refrigerator disassembly

經(jīng)多次觀察與記錄，制訂了如圖7所示的零件優(yōu)先關(guān)系圖，結(jié)合該型號電冰箱零部件的位置與構(gòu)造，在零部件編號右上方給出了該零件的拆卸方位。

圖7 冰箱拆卸優(yōu)先關(guān)系圖Fig.7 The precedence diagram of the refrigerator

針對該電冰箱拆卸實(shí)例，綜合求解時(shí)間與求解效率，經(jīng)多次參數(shù)設(shè)置比較，設(shè)定算法參數(shù)如下：種群規(guī)模M=200，脈沖頻率搜索范圍 fmin=0，fmax=1.2，最大脈沖頻度s=0.55，最大脈沖音強(qiáng) A=0.9，脈沖頻度增加系數(shù)γ=0.04，脈沖音強(qiáng)衰減系數(shù)α=0.91，算法最大迭代次數(shù) gmax=220，外部檔案規(guī)模 fN=8，算法運(yùn)行30次，平均每次運(yùn)行時(shí)間為93.431 s，其中一次運(yùn)行結(jié)果如表4所示，因拆卸線上任務(wù)時(shí)間之和、生產(chǎn)節(jié)拍固定，因此平衡率與開啟的工作站數(shù)目成反比。

表4中，LW表示在左側(cè)開啟的工作站，RW表示在右側(cè)開啟的工作站。方案4中右側(cè)第2個(gè)工作站未有任務(wù)分配，因此關(guān)閉該工作站以節(jié)約拆卸成本。由表4數(shù)據(jù)可知，針對包含25個(gè)任務(wù)的電冰箱雙邊拆卸實(shí)例，本文算法能一次求得多樣化的分配方案。開啟的工作站數(shù)目介于6和9之間，能為決策者提供多樣的工作站數(shù)目決策；空閑時(shí)間指標(biāo)包含介于5 907和51 679之間的不重復(fù)的8個(gè)值，保證需求指標(biāo)質(zhì)量的同時(shí)，危害指標(biāo)也具有良好的分布性。當(dāng)決策者注重F1指標(biāo)時(shí)，可以選擇方案1～方案3；當(dāng)決策者注重F2指標(biāo)時(shí)，可以選擇方案1；當(dāng)決策者注重F3指標(biāo)時(shí)，可以選擇方案7；當(dāng)決策者注重F4指標(biāo)時(shí)，可以選擇方案6，綜合決策時(shí)，可以從方案1～方案8之間挑選適合當(dāng)前實(shí)際條件的平衡方案，為拆卸線的設(shè)計(jì)提供了一定的參考。

表4 電冰箱平衡分配方案Tab.4 The balancing allocation scheme of the refrigerator

為更好地展示任務(wù)分配結(jié)果，以方案1為例，列出具體分配方案示意圖，見圖8，其中LW1表示拆卸線左邊開啟的第一個(gè)工作站，RW1表示拆卸線上右邊開啟的第一個(gè)工作站。

圖8 方案1任務(wù)分配圖Fig.8 The distribution of the scheme 1

4 結(jié)論

（1）根據(jù)拆卸方向，定義了零部件拆卸方位屬性，首次采用雙邊拆卸，并建立了雙邊拆卸線平衡問題數(shù)學(xué)模型。解碼中，任務(wù)優(yōu)先分配到工作站開啟較少的一邊，縮短了工件輸送路徑，降低了拆卸成本；任務(wù)次優(yōu)先分配至空閑時(shí)間較多的工作站，提高了拆卸效率。

（2）將Pareto思想引入蝙蝠算法，保留了解的多樣性。引入精英策略將外部檔案集作為部分種群參與迭代，有效加速了算法的收斂。采用擁擠距離精簡外部檔案，提高了算法的運(yùn)行效率。

（3）求解包含25個(gè)任務(wù)的經(jīng)典算例，并與已有的智能方法求解結(jié)果進(jìn)行對比，驗(yàn)證了所提算法的有效性。將所建立模型和所提算法應(yīng)用于電冰箱拆卸線設(shè)計(jì)研究中，能為決策者提供8種高質(zhì)量的拆卸方案。

參考文獻(xiàn)：

［1］ GUNGOR A，GUPTA S M，POCHAMPALLY K，et al.Complications in Disassembly Line Balancing［C］//1st InternationalConference on Environmentally Con?scious Manufacturing.Bellingham，WA：SPIE，2001：289-298.

［2］ KALAYCI C B，HANCILAR A，GUNGOR A，et al.Multi-objective Fuzzy Disassembly Line Balancing Us?ing a Hybrid Discrete Artificial Bee Colony Algorithm［J］.Journal of Manufacturing Systems，2014，37：672-682.

［3］ AGRAWAL S，TIWARI M K.A Collaborative Ant Col?ony Algorithm to Stochastic Mixed-model U-shaped Disassembly Line Balancing and Sequencing Problem［J］.International Journal of Production Research，2008，46（6）：1405-1429.

［4］ KALAYCILAR E G，AZIZOLU M，YERALAN S.A Disassembly Line Balancing Problem with Fixed Num?ber of Workstations［J］.European Journal of Operation?al Research，2016，249（2）：592-604.

［5］ KALAYCI C B，POLAT O，GUPTA S M.A Variable Neighborhood Search Algorithm for Disassembly Lines［J］.Journal of Manufacturing Technology Manage?ment，2015，26（2）：182-194.

［6］ TUNCEL E，ZEID A，KAMARTHI S.Solving Large Scale Disassembly Line Balancing Problem with Uncer?tainty Using Reinforcement Learning［J］.Journal of In?telligent Manufacturing，2014，25（4）：647-659.

［7］ MCGOVERN S M，GUPTA S M.Greedy Algorithm for Disassembly Line Scheduling［C］//IEEE International Conference on Systems，Man and Cybernetics.Piscat?away，NJ：IEEE，2003：1737-1744.

［8］ KALAYCI C B，GUPTA S M.A Particle Swarm Optimi?zation Algorithm for Solving Disassembly Line Balanc?ing Problem［C］//Proceedings of Northeast Decision Sciences Institute 2012 Annual Conference.Newport，Rhode Island，2012：347-357.

［9］ KALAYCI C B，POLAT O，GUPTA S M.A Hybrid Ge?netic Algorithm for Sequence-dependent Disassembly Line Balancing Problem［J］.Annals of Operations Re?search，2016，242（2）：321-354.

［10］ 張則強(qiáng)，胡揚(yáng)，陳沖.求解拆卸線平衡問題的改進(jìn)人工蜂群算法［J］.西南交通大學(xué)學(xué)報(bào)，2016，51（5）：910-917.ZHANG Zeqiang，HU Yang，CHEN Chong.Improved Artificial Bee Colony Algorithm for Disassembly Line Balancing Problem［J］.Journal of Southwest Jiaotong University，2016，51（5）：910-917.

［11］ DING L P，F(xiàn)ENG Y X，TAN J R，et al.A New Multi-objective Ant Colony Algorithm for Solving the Disassembly Line Balancing Problem［J］.The Inter?national Journal of Advanced Manufacturing Technol?ogy，2010，48（5）：761-771.

［12］ 汪開普，張則強(qiáng)，毛麗麗，等.多目標(biāo)拆卸線平衡問題的Pareto人工魚群算法［J］.中國機(jī)械工程，2017，28（2）：183-190.WANG Kaipu，ZHANG Zeqiang，MAO Lili，et al.Pa?reto Artificial Fish Swarm Algorithm for Multi-objec?tive Disassembly Line Balancing Problems［J］.China Mechanical Engineering，2017，28（2）：183-190.

［13］ DELICE Y，AYDOAN E K，?ZCAN U，et al.A Mod?ified Particle Swarm Optimization Algorithm to Mixed-model Two-sided Assembly Line Balancing［J］.Journal of Intelligent Manufacturing，2017，28（1）：23-36.

［14］ TANG Q H，LI Z X，ZHANG L P.An Effective Dis?crete Artificial Bee Colony Algorithm with Idle Time Reduction Techniques for Two-sided Assembly Line Balancing Problem of Type-Ⅱ［J］.Computers&In?dustrial Engineering，2016，97：146-156.

［15］ SEPAHI A，NAINI S G J.Two-sided Assembly Line Balancing Problem with Parallel Performance Capaci?ty［J］.Applied Mathematical Modelling，2016，40（13/14）：6280-6292.

［16］ YANG X S.A New Metaheuristic Bat-inspired Algo?rithm［J］.Computer Knowledge&Technology，2010，284：65-74.

［17］ YANG X S，GANDOMI A H.Bat Algorithm：a Novel Approach for Global Engineering Optimization［J］.Engineering Computations，2012，29（5）：464-483.

［18］ 徐華，張庭.混合離散蝙蝠算法求解多目標(biāo)柔性作業(yè)車間調(diào)度［J］.機(jī)械工程學(xué)報(bào)，2016，52（18）：201-212.

XU Hua，ZHANG Ting.Hybrid Discrete Bat Algo?rithm for Solving the Multi-objective Flexible Job Shop Scheduling Problem［J］.Journal of Mechanical Engineering，2016，52（18）：201-212.

［19］ HEMALATHA S，CHANDRAMOHAN S.Cost Opti?mization of Power Generation Systems Using Bat Al?gorithm for Remote Health Facilities［J］.Journal of Medical Imaging and Health Informatics，2016，6（7）：1646-1651.

［20］ THARAKESHWAR T K，SEETHARAMU K N，PRASAD B D.Multi-objective Optimization Using Bat Algorithm for Shell and Tube Heat Exchangers［J］.Applied ThermalEngineering，2017，110：1029-1038.

［21］ DEB K，PRATAP A，AGARWAL S，et al.A Fast and Elitist Multiobjective Genetic Algorithm：NSGA-Ⅱ［J］.IEEE Transactions on Evolutionary Computa?tion，2002，6（2）：182-197.

［22］ KALAYCI C B，GUPTA S M.Simulated Annealing Algorithm for Solving Sequence-dependent Disassem?bly Line Balancing Problem［J］.IFAC Proceedings Volumes，2013，46（9）：93-98.

（編輯 袁興玲）

作者簡介：鄒賓森，男，1990年生，碩士研究生。研究方向?yàn)樯a(chǎn)線平衡與智能優(yōu)化。張則強(qiáng)（通信作者），男，1978年生，教授、博士研究生導(dǎo)師。研究方向?yàn)橹圃煜到y(tǒng)與智能優(yōu)化。E-mail：zzq_22@163.com。