鄒賓森 張則強(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)點，但在拆卸作業(yè)中當(dāng)任務(wù)在工作站內(nèi)分配不合理時會帶來拆卸線平衡問題（disassembly line balancing problem，DLBP）。

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

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

蝙蝠算法（bat algorithm，BA）［16］因具有算法參數(shù)少、收斂速度快和收斂精度高等優(yōu)點［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的公開報道，因此將蝙蝠算法應(yīng)用于求解DLBP具有重要的研究價值。

本文對雙邊拆卸線平衡問題（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è)，尚未有雙邊拆卸線平衡問題的公開研究報道，但經(jīng)實地調(diào)研后發(fā)現(xiàn)，雙邊拆卸被廣泛地應(yīng)用于實際拆卸作業(yè)中。圖2為雙邊拆卸線示意圖。

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

如圖2所示，雙邊拆卸線中，工作站布置在輸送帶的左右兩側(cè)，在滿足拆卸優(yōu)先關(guān)系的前提下，左右兩邊可同時進(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)品的同一零部件的拆卸時間固定且相同；②雙邊同時作業(yè)時互不干擾。

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

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

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

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

2 Pareto蝙蝠算法

2.1 編碼

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

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

速度更新：

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

拆卸線平衡問題是一個離散問題，因此將蝙蝠算法應(yīng)用于求解拆卸線平衡問題時需將算法離散化?？紤]拆卸線平衡問題采用拆卸序列編碼的特性，定義位置之差為兩個解對應(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))中實際參與速度更新的長度比例：若 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ù)為對，隨機(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時，在當(dāng)前全局最優(yōu)附近進(jìn)行隨機(jī)搜索以尋找新的位置。鑒于拆卸線中優(yōu)先關(guān)系的存在，本文采用如下方式對當(dāng)前全局最優(yōu)進(jìn)行隨機(jī)搜索：從全局最優(yōu)中隨機(jī)選擇一個任務(wù)，將所選任務(wù)隨機(jī)插入到最近的緊前任務(wù)和最近的緊后任務(wù)之間，完成局部搜索。局部搜索如圖4所示。

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

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

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

2.3 解碼方式

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

圖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 時 ，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)問題的解是多個互不占優(yōu)的非劣解，規(guī)模往往較大，但外部檔案規(guī)模過大則會降低算法運行速度。為提高算法運行效率和讓更具代表性的非劣解參與尋優(yōu)以加強(qiáng)算法尋優(yōu)能力，當(dāng)外部檔案大小超過設(shè)定規(guī)模時需對外部檔案進(jìn)行篩選，本文采用基于擁擠距離的外部檔案篩選方式［21］，依次剔除擁擠距離小的個體，直到外部檔案大小等于設(shè)定規(guī)模。采用精英策略，用外部檔案中的非劣解替換當(dāng)前種群中的部分個體參與算法迭代尋優(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)個體產(chǎn)生一個隨機(jī)擾動，產(chǎn)生新個體 xnew；否則采用式（12）產(chǎn)生新個體xnew。

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

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

（8）若更新后個體優(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īng)用

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

3.1 算法驗證

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

為驗證算法的有效性，將蝙蝠算法應(yīng)用于求解移動電話機(jī)拆卸實例［8］，該算例包含25個拆卸任務(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è)時間和任務(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，算法運行30次，平均每次運行時間為34.956 s，其中一次運行結(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)，但本文算法一次能求得多種平衡方案，同時 F3指標(biāo)上能求得更優(yōu)的 807、823、802、819，在F4指標(biāo)能求得更優(yōu)的 70、72、73；因此可知本文算法優(yōu)于VNS。本文算法一次運算能求得多種平衡方案，且在F3指標(biāo)和F4指標(biāo)能求得更優(yōu)異的值。

文獻(xiàn)［12］采用人工魚群算法對P25進(jìn)行了求解，一次求得了8個平衡方案，對比蝙蝠算法求解結(jié)果和AFSA求解結(jié)果。AFSA所求得前兩個平衡方案與本文所求得的方案6和方案4相同，其余方案與本文所求方案都互不占優(yōu)。對比單個目標(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。通過上述對比，驗證了本文所提算法的有效性。

3.2 實例應(yīng)用

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

針對該電冰箱拆卸實例，綜合求解時間與求解效率，經(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，算法運行30次，平均每次運行時間為93.431 s，其中一次運行結(jié)果如表4所示，因拆卸線上任務(wù)時間之和、生產(chǎn)節(jié)拍固定，因此平衡率與開啟的工作站數(shù)目成反比。

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

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

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

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

4 結(jié)論

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

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

（3）求解包含25個任務(wù)的經(jīng)典算例，并與已有的智能方法求解結(jié)果進(jìn)行對比，驗證了所提算法的有效性。將所建立模型和所提算法應(yīng)用于電冰箱拆卸線設(shè)計研究中，能為決策者提供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)，胡揚，陳沖.求解拆卸線平衡問題的改進(jìn)人工蜂群算法［J］.西南交通大學(xué)學(xué)報，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é)報，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年生，碩士研究生。研究方向為生產(chǎn)線平衡與智能優(yōu)化。張則強(qiáng)（通信作者），男，1978年生，教授、博士研究生導(dǎo)師。研究方向為制造系統(tǒng)與智能優(yōu)化。E-mail：zzq_22@163.com。