求解拆卸線平衡問題的改進(jìn)人工蜂群算法

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

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

大規(guī)模拆卸線平衡問題（disassembly line balancing problem，DLBP）是NP完全問題.為克服傳統(tǒng)算法求解DLBP搜索過于隨機(jī)、易于早熟，且求解難度隨任務(wù)規(guī)模的增加呈指數(shù)級增長等不足，構(gòu)建了基于最小化工作站、均衡負(fù)荷、盡早拆卸有危害和高需求零部件的DLBP多目標(biāo)優(yōu)化模型，在此基礎(chǔ)上，提出了改進(jìn)人工蜂群算法.該算法包括以下4個(gè)階段：在初始解生成階段，引入危害指標(biāo)和需求指標(biāo)，提升算法收斂性能；在雇傭蜂搜索階段，采取可變步長搜索策略，增加對較優(yōu)解的搜索深度，加速淘汰劣解；在觀察蜂搜索階段，采用常規(guī)搜索與蠕動(dòng)搜索相結(jié)合的混合搜索策略；在偵察蜂搜索階段，構(gòu)造了基于分布估計(jì)的搜索策略，引導(dǎo)搜索過程.應(yīng)用本文算法對70個(gè)測試問題進(jìn)行求解，其中65個(gè)求得了最優(yōu)解，尋優(yōu)率為92.86%；對10個(gè)任務(wù)實(shí)例求得最優(yōu)解的需求指標(biāo)為9 730個(gè)，比蟻群算法減少了360個(gè)；52個(gè)任務(wù)實(shí)例的開啟工作站數(shù)目、平滑率和拆卸成本3項(xiàng)指標(biāo)均取得了更優(yōu)的結(jié)果，求解較大規(guī)模問題的性能顯著提升.

拆卸線平衡；人工蜂群算法；優(yōu)化；拆卸

隨著現(xiàn)代化進(jìn)程的發(fā)展，物質(zhì)資源極大豐富化，但同時(shí)也面臨著大量壽命終了的機(jī)械、汽車、電器等產(chǎn)品等待回收處理問題.另一方面，當(dāng)前資源、能源短缺問題日趨嚴(yán)重，傳統(tǒng)的高投入、高產(chǎn)出模式難以持續(xù)，社會環(huán)境與資源問題日益突顯，加之公民環(huán)保意識的不斷增強(qiáng)，所有這些都在推動(dòng)尋求廢舊機(jī)電產(chǎn)品的新出路.

廢舊機(jī)電產(chǎn)品的回收資源化處理是構(gòu)建靜脈產(chǎn)業(yè)的必由之路，在產(chǎn)品的回收過程中，產(chǎn)品拆卸過程是重要的環(huán)節(jié)，無論是對于具有眾多零部件的大型產(chǎn)品還是對于回收數(shù)量很多的小型產(chǎn)品，實(shí)現(xiàn)拆卸過程的流水作業(yè)，在極大提高產(chǎn)品回收效率的同時(shí)，能有效降低拆卸成本，因此，受到了越來越多企業(yè)的重視.為解決流水化拆卸過程中拆卸任務(wù)分配不均衡等問題，學(xué)術(shù)界對拆卸線平衡問題展開了深入的研究.

文獻(xiàn)［1］比較了拆卸線平衡問題（disassembly line balancing problem，DLBP）與裝配線平衡問題［2］的異同點(diǎn)，并對影響拆卸線平衡的眾多復(fù)雜因素進(jìn)行了詳細(xì)分析.文獻(xiàn)［3］建立了破壞性拆卸影響下的單目標(biāo)DLBP模型，并用分支定界法來求解該模型.其求解方法局限在數(shù)學(xué)規(guī)劃層面，然而文獻(xiàn)［4］證明了拆卸線平衡問題是一個(gè)NP（nondeterministic polynomial）完全問題，問題的求解難度會隨著任務(wù)規(guī)模的增加呈幾何級增長，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法不適用于對大規(guī)模問題的求解.文獻(xiàn)［5］提出了一種基于Pareto的蟻群算法求解多目標(biāo)DLBP問題，其在建模階段引入對拆卸成本的考量，使得研究的問題更加貼近生產(chǎn)實(shí)際，但其算法求解質(zhì)量還有提升空間.文獻(xiàn)［6］建立了關(guān)于拆卸費(fèi)用的DLBP模型，并用啟發(fā)式算法求解該模型.文獻(xiàn)［7］考慮了最小化工作站數(shù)、平衡指數(shù)、危害指數(shù)、需求指數(shù)、最小化拆卸方向改變5個(gè)目標(biāo)函數(shù).文獻(xiàn)［8］提出一種改進(jìn)的蟻群算法，采用混合搜索策略，提高了算法在多目標(biāo)優(yōu)化方面的能力.文獻(xiàn)［9］采用一種基于網(wǎng)絡(luò)的最短路模型法求解并行DLBP問題，但該方法難以求解大規(guī)模問題.文獻(xiàn)［10］引入變鄰域搜索算法求解序列相關(guān)的拆卸線平衡問題，拓展了解決DLBP問題的新途徑.文獻(xiàn)［11］考慮了不確定拆卸時(shí)間的特殊情況，其所提算法對于多目標(biāo)的優(yōu)化能力不強(qiáng)，求解過程一味追求平衡而增加了大量的時(shí)間消耗.

本文針對傳統(tǒng)算法在求解DLBP問題時(shí)的搜索過于隨機(jī)、易陷入局部最優(yōu)等不足，提出了一種改進(jìn)的人工蜂群算法（artificialbeecolony algorithm，ABC）.ABC算法是一種模擬自然界中蜜蜂覓食行為而發(fā)展起來的群集智能優(yōu)化算法［12］，與粒子群算法［13-14］等均屬于群智能優(yōu)化算法，具有結(jié)構(gòu)簡單、穩(wěn)定性好等優(yōu)點(diǎn)，在諸多優(yōu)化問題中得到了廣泛應(yīng)用［15］，并表現(xiàn)出良好性能.本文根據(jù)ABC算法原理并結(jié)合DLBP問題的特點(diǎn)，構(gòu)造了由一般產(chǎn)品通用的優(yōu)化目標(biāo)組成的多目標(biāo)DLBP模型，并從初始解生成、雇傭蜂和觀察蜂的鄰域搜索策略、偵察蜂搜索策略等方面對算法進(jìn)行了改進(jìn)，進(jìn)而通過對不同規(guī)模算例的測試來驗(yàn)證所提算法的求解性能.

1 多目標(biāo)拆卸線平衡問題的數(shù)學(xué)模型

1.1 模型描述

假定待拆卸產(chǎn)品的每個(gè)零件對應(yīng)一個(gè)拆卸任務(wù)，n為零件數(shù)目，T代表拆卸任務(wù)集合，則有

m為開啟的工作站的數(shù)目，工作節(jié)拍用C表示，ti表示第i個(gè)工作站上分配的所有拆卸任務(wù)作業(yè)時(shí)間之和.用φij表示任務(wù)與工作站的關(guān)系，若任務(wù)j被分配到工作站i，則φij=1，否則φij=0.本文從4個(gè)方面構(gòu)建DLBP問題的數(shù)學(xué)模型：最小化工作站數(shù)、均衡各工作站作業(yè)負(fù)荷、盡早拆除有危害零部件、盡早拆除高需求零部件.作業(yè)任務(wù)之間的優(yōu)先關(guān)系用P表示，若任務(wù)p為任務(wù)q的前序任務(wù)，則P（p，q）=1，否則P（p，q）=0.

（1）最小化工作站數(shù).工作站的開啟意味著人力、物力等成本的投入，最小化工作站數(shù)能夠?qū)⑵髽I(yè)的投入成本降到最低，目標(biāo)為

（2）均衡各工作站的作業(yè)負(fù)荷.為保證拆卸線高效運(yùn)行，盡量降低產(chǎn)品在線阻塞，需要使各工作站的員工具有相對均衡的作業(yè)負(fù)荷，目標(biāo)表示為

（3）盡早拆除危害性零部件.回收產(chǎn)品中經(jīng)常包含有毒有害物質(zhì)，例如重金屬、含鉛玻璃、氯氟烴等.這些物質(zhì)不但會對作業(yè)員的人身安全以及自然環(huán)境安全造成嚴(yán)重威脅，而且由于其需要特殊的工具或手段進(jìn)行處理，還會對整個(gè)拆卸線的工作效率造成影響.對于這類危害性零部件，應(yīng)盡早拆除.目標(biāo)表示為

式中：Sk表示拆卸序列的第k個(gè)位置的零件編號.

（4）盡早拆卸高需求的零件.對于高需求的零部件，為了盡早滿足供給同時(shí)避免其在線上的損傷，應(yīng)盡早予以拆除.目標(biāo)表示為

式中：dSk表示編號為Sk的零件的需求量.

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

基于以上考慮，構(gòu)建的多目標(biāo)DLBP數(shù)學(xué)模型如下.

目標(biāo)函數(shù)：min｛f1，f2，f3，f4｝，

約束條件：

式（5）為節(jié)拍時(shí)間約束，即被分配到同一工作站的所有任務(wù)作業(yè)時(shí)間之和不能超過所設(shè)定的節(jié)拍時(shí)間.式（6）表示一項(xiàng)作業(yè)任務(wù)必須分配到某個(gè)工作站內(nèi)完成，但不能同時(shí)分配到兩個(gè)以上的工作站.式（7）表示任務(wù)之間的優(yōu)先關(guān)系約束，即每個(gè)作業(yè)任務(wù)都應(yīng)符合給定的優(yōu)先順序，如果作業(yè)k需在作業(yè)j前完成，則k就不能分配至j所在工作站的后續(xù)工作站中.

2 人工蜂群算法

人工蜂群智能優(yōu)化算法是仿效蜜蜂采蜜過程而提出的一種仿生搜索算法［12］，利用了雇傭蜂、觀察蜂和偵察蜂3個(gè)蜂種之間相互協(xié)作而體現(xiàn)出的群體智能行為.在運(yùn)用ABC算法求解問題的過程中，將問題的可行解看做蜜源，將解的收益度作為考量花蜜豐富程度的指標(biāo).

DLBP的標(biāo)準(zhǔn)人工蜂群算法步驟如下［11］：

步驟1 初始化階段.設(shè)定算法參數(shù)，如蜂群規(guī)模、雇傭蜂步長、循環(huán)次數(shù)及角色轉(zhuǎn)變閾值Zuplimit.同時(shí)偵察蜂在全局范圍內(nèi)隨機(jī)搜索初始解，開始時(shí)，令所有蜜蜂執(zhí)行搜索任務(wù)，選擇較好的初始解作為雇傭蜂采蜜的蜜源.

采用構(gòu)造可選任務(wù)集和可分配任務(wù)集的方法構(gòu)造可行解.首先，在當(dāng)前位置i處，所有緊前任務(wù)都已分配的任務(wù)稱為可選任務(wù)，組成可選任務(wù)集TEi；其次，從TEi中將作業(yè)時(shí)間超過工作站剩余時(shí)間的任務(wù)剔除，形成可分配任務(wù)集Trang，然后從Trang中隨機(jī)選擇任務(wù)分配.

步驟2 雇傭蜂階段.雇傭蜂在現(xiàn)有解附近搜索，如果找到更好的解，就放棄現(xiàn)有解保留新解，依次對比f1～f4來確定食物源的優(yōu)劣.常用的鄰域搜索方法有交換法和插入法等.

步驟3 觀察蜂階段.求出雇傭蜂帶回食物源的收益度，用解的收益度計(jì)算觀察蜂跟隨雇傭蜂的概率，

式中：Neb為雇傭蜂的數(shù)量；

Fi為第i只雇傭蜂所搜尋到的食物源的收益度.

觀察蜂采用輪盤賭的方式選擇跟隨目標(biāo)，食物源的收益度越好，被選擇的可能性就越大.一只觀察蜂在其跟隨的雇傭蜂附近搜索到新解后，如果新解優(yōu)于當(dāng)前解，雇傭蜂就放棄現(xiàn)有解，獲得新解.

步驟4 偵察蜂階段.如果某一雇傭蜂代表的解經(jīng)過Zuplimit次循環(huán)都沒有得到優(yōu)化，那么該雇傭蜂的角色轉(zhuǎn)變?yōu)閭刹旆洌⒃谌址秶鷥?nèi)隨機(jī)搜索新解.

步驟5 記錄當(dāng)前最優(yōu)解.

步驟6 終止條件判定（是否達(dá)到設(shè)定的最大迭代次數(shù)），滿足則退出，否則回到步驟2.

3 算法的分析與改進(jìn)

ABC算法中，雇傭蜂和跟隨的觀察蜂在現(xiàn)有解的附近搜索，不斷用附近更優(yōu)的解替代現(xiàn)有解作為下一步的搜索中心.偵察蜂依靠在全局的隨機(jī)搜索，為它們提供新的搜索中心.在貪婪選擇的驅(qū)使下，雇傭蜂代表的解會逐漸向局部最優(yōu)收斂，在參數(shù)Zuplimit的控制下偵察蜂獲得在全局搜索的機(jī)會.局部搜索的深度和全局搜索的廣度決定了算法的性能.標(biāo)準(zhǔn)的人工蜂群算法收斂速度快，但是搜索過于隨機(jī)，易早熟，不利于多目標(biāo)的搜索.因此本文對初始解生成策略、雇傭蜂步長和偵察蜂搜索策略進(jìn)行改進(jìn)，以克服標(biāo)準(zhǔn)算法的不足.

3.1 初始解生成策略的改進(jìn)

文獻(xiàn)［11］的初始解生成策略只考慮了節(jié)拍時(shí)間和優(yōu)先關(guān)系的約束，并未加入危害性和需求因素.而基于優(yōu)先順序的多目標(biāo)優(yōu)化策略對后續(xù)目標(biāo)的優(yōu)化能力不足，因此，本文在生成初始解時(shí)加入危害性和需求因素，提高初始解針對這兩個(gè)目標(biāo)的質(zhì)量.在從可分配任務(wù)集Trang中選擇分配任務(wù)時(shí)，增大選擇有危害和高需求任務(wù)的概率.基于此，設(shè)定Trang中每個(gè)任務(wù)被選擇的概率為

式中：NC為可分配任務(wù)集Trang中任務(wù)數(shù)；

PHi、PDi分別為零件i的危害指數(shù)和需求指數(shù)占Trang中所有任務(wù)該項(xiàng)指數(shù)之和的比重.

3.2 步長的分析與改進(jìn)

參數(shù)Zuplimit控制著雇傭蜂和偵察蜂的角色轉(zhuǎn)換.一個(gè)自適應(yīng)的步長能夠增強(qiáng)算法對問題的適應(yīng)性［16］.當(dāng)現(xiàn)有解的收益度很差時(shí)，應(yīng)盡早放棄.如果改善緩慢的話，會拖延收斂速度.基本ABC算法中Zlimit的增長步長為1，為了能夠根據(jù)解的質(zhì)量動(dòng)態(tài)調(diào)整其搜索次數(shù)，本文設(shè)定Zlimit的動(dòng)態(tài)步長為

式中：fi為當(dāng)前解的收益度；

fLbest為當(dāng)前局部最優(yōu)解的收益度，本文以平衡指標(biāo)f2的值表示收益度.

由式（10）可知，若λ＜1，則表示新搜索到的解優(yōu)于局部最優(yōu)解，搜索進(jìn)程放緩，搜索機(jī)會增加；若λ＞1，則表示新搜索到的解劣于局部最優(yōu)解，搜索進(jìn)程加速，對劣解的搜索次數(shù)減少.

3.3 觀察蜂搜索策略改進(jìn)

長距離的交換和插入操作很容易引起平衡指標(biāo)的改變，導(dǎo)致危害指標(biāo)和需求指標(biāo)被忽視.蠕動(dòng)搜索就是將有危害或高需求的任務(wù)向前做一個(gè)微小距離的移動(dòng)，在保證平衡指標(biāo)性能的前提下，提高后續(xù)目標(biāo)函數(shù)的質(zhì)量.

為了增強(qiáng)對危害目標(biāo)和需求目標(biāo)的搜索能力，使雇傭蜂執(zhí)行雇傭蜂搜索和蠕動(dòng)搜索兩種搜索方式，以增大改善當(dāng)前解的可能性.

3.4 偵察蜂搜索策略分析與改進(jìn)

分布估計(jì)算法是進(jìn)化算法的一種，其原理是基于概率模式的引導(dǎo)作用，即對歷次搜尋到的較優(yōu)個(gè)體集合建立概率模型，通過該模型對下一步的搜索范圍進(jìn)行引導(dǎo).具體到人工蜂群算法中，局部最優(yōu)解作為一組質(zhì)量較好的解，可以作為構(gòu)建指引偵察蜂搜索的經(jīng)驗(yàn)信息庫的基礎(chǔ).本文引入一個(gè)基于任務(wù)與位置對應(yīng)的分布估計(jì)矩陣Q，該矩陣記錄局部最優(yōu)解中任務(wù)與位置對應(yīng)關(guān)系在局部最優(yōu)解中出現(xiàn)的頻次，并以此作為引導(dǎo)偵察蜂進(jìn)行全局搜索的標(biāo)桿.

式中：qij為拆卸任務(wù)j在拆卸序列第i個(gè)位置上出現(xiàn)的次數(shù)，

i，j=1，2，…，n.

統(tǒng)計(jì)矩陣Q的初始數(shù)據(jù)取自于最優(yōu)的初始解，對反映該解序列中任務(wù)與位置對應(yīng)關(guān)系的元素qij進(jìn)行加權(quán)處理，權(quán)值為α，解的平衡指標(biāo)越小，說明任務(wù)所在位置越好.危害性指標(biāo)和需求指標(biāo)越小，說明有危害和高需求的零件被拆除的越早.為了反映對應(yīng)關(guān)系在平衡性、危害性和需求指標(biāo)上的質(zhì)量，令越優(yōu)的解其α值越大，設(shè)定

式中：F、H、D分別為解的平衡指標(biāo)、危害指標(biāo)和需求指標(biāo)；帶下標(biāo)Gbest的量為當(dāng)前全局最優(yōu)解.

每當(dāng)產(chǎn)生一個(gè)局部最優(yōu)解，且該解的平衡指標(biāo)不劣于當(dāng)前全局最優(yōu)解，就用該解更新矩陣Q.搜索初期獲得的全局最優(yōu)解質(zhì)量較差，對應(yīng)的矩陣Q質(zhì)量也較差.

為了能隨著搜索的深入逐漸削弱矩陣Q在前期受到的不良影響，根據(jù)測試經(jīng)驗(yàn)，對矩陣Q引入衰減常數(shù)，衰減常數(shù)的值為0.8.

在偵察蜂搜索階段，可行解的構(gòu)造策略為：從可分配任務(wù)集Trang中按照式（13）計(jì)算出的任務(wù)選擇概率進(jìn)行任務(wù)的選擇與分配.

由式（13）可知，在對位置i進(jìn)行任務(wù)分配時(shí)，集合Trang中每個(gè)任務(wù)被選擇的概率是由前i處位置上該任務(wù)出現(xiàn)的概率之和決定的.換言之，若集合Trang中所有任務(wù)均未在前i處位置上出現(xiàn)過，則它們被選擇的概率相同.

為了不失搜索的隨機(jī)性，偵察蜂采用分布估計(jì)搜索和隨機(jī)搜索兩種策略.改進(jìn)后的ABC算法流程圖如圖1所示.

圖1 改進(jìn)ABC算法流程Fig.1 Flow chart of the improved ABC algorithm

4 算例測試與分析

4.1 測試問題

根據(jù)第3節(jié)改進(jìn)ABC算法，用MATLAB R2008a編程實(shí)現(xiàn)，在Windows7系統(tǒng)下Intel Core 2.20 GHz CPU、2 GB RAM的計(jì)算機(jī)上，進(jìn)行了多次試驗(yàn)計(jì)算.考慮到拆卸線平衡問題與裝配線平衡問題（simple assembly line balancing problem，SALBP）結(jié)構(gòu)相似，具有相同的優(yōu)先關(guān)系、節(jié)拍約束等，兩者均為NP問題，故衡量裝配線平衡問題的性能在一定程度上也可體現(xiàn)求解拆卸線平衡問題的性能.首先，對SALBP測試問題集進(jìn)行求解以驗(yàn)證算法的有效性.該基準(zhǔn)測試問題集的相關(guān)數(shù)據(jù)可通過如下網(wǎng)址獲?。篽ttp：//alb.mansci.de/files/

uploads/SALBP%20data%20sets.zip.設(shè)置算法參數(shù)如下：

雇傭蜂數(shù)目Neb=10；

最大搜索步長Zuplimit=10；

最大迭代次數(shù)M=50.

測試結(jié)果如表1所示.

表1給出用改進(jìn)ABC算法求解不同規(guī)模、不同節(jié)拍的70個(gè)測試問題的解，對其中的65個(gè)問題求得了最優(yōu)解，5個(gè)問題求出了比最優(yōu)解多一個(gè)或兩個(gè)工作站的近優(yōu)解，算法的求解性能是可以接受的.

4.2 實(shí)例問題

實(shí)例1 對文獻(xiàn)［7］中10個(gè)任務(wù)的拆卸實(shí)例進(jìn)行求解，具體拆卸任務(wù)數(shù)據(jù)及優(yōu)先關(guān)系如圖2所示，圈中數(shù)字表示任務(wù)編號，*表示有危害性的任務(wù)；右上角數(shù)字表示拆卸任務(wù)的作業(yè)時(shí)間；左下角數(shù)字表示需求量.為使圖2簡潔，危害指標(biāo)和需求指標(biāo)為0的情況不予標(biāo)注.

各項(xiàng)拆卸任務(wù)的作業(yè)時(shí)間（單位：s）

危害指標(biāo)

需求指標(biāo)

設(shè)置算法參數(shù)如下：雇傭蜂數(shù)量Neb=10，

循環(huán)次數(shù)M=100.

表1 基準(zhǔn)算例測試結(jié)果Tab.1 Performance comparison on benchmark problems

圖2 拆卸任務(wù)數(shù)據(jù)及優(yōu)先關(guān)系Fig.2 Precedence diagram and data of disassembly tasks

運(yùn)行程序20次，每次均能很快找到最優(yōu)解，所用時(shí)間平均為0.73 s.對比文獻(xiàn)［7］用蟻群算法求解出的最優(yōu)解目標(biāo)函數(shù)值，結(jié)果如表2所示.

從表2可知，兩種算法的工作站數(shù)、平衡和危害指標(biāo)相同，在需求指標(biāo)上ABC算法優(yōu)于文獻(xiàn)［7］算法.

用ABC算法所得最優(yōu)解序列見表3，有危害和高需求的拆卸任務(wù)6、7、9被盡早完成，因?yàn)閮?yōu)先關(guān)系的緣故，有需求的任務(wù)2執(zhí)行較晚，但仍在無需求的任務(wù)3之前被執(zhí)行.說明了本文算法在觀察蜂搜索階段針對危害指標(biāo)和需求指標(biāo)采取的蠕動(dòng)搜索策略是有效的.

表2 算法求解結(jié)果對比Tab.2 Solution comparison of the two algorithms

表3 10個(gè)任務(wù)實(shí)例的最優(yōu)解Tab.3 Optimal solution for the 10-task case

圖3是20次運(yùn)行所得平衡指標(biāo)的平均值收斂圖.從圖3可見平衡指標(biāo)很快收斂于最優(yōu)值211，收斂的最大循環(huán)次數(shù)不超過20次.該測試結(jié)果說明ABC算法在求解拆卸線平衡問題時(shí)的有效性.

實(shí)例2 對文獻(xiàn)［5］中某企業(yè)52個(gè)任務(wù)的高速電子套結(jié)機(jī)拆卸實(shí)例進(jìn)行求解，節(jié)拍時(shí)間為600 s.由于該問題模型中考慮了拆卸成本，為便于比較，將文獻(xiàn)［5］中的平滑率指標(biāo)函數(shù)Fsmooth以及拆卸成本函數(shù)Fcost引入本文算法，描述為

式中：Cj為拆卸任務(wù)j的單位時(shí)間拆卸成本.

圖3 平衡指標(biāo)收斂圖Fig.3 Convergent graph of balance index

由于該案例含任務(wù)數(shù)較多，為加強(qiáng)對最優(yōu)解的搜索能力，適當(dāng)調(diào)高算法參數(shù)，設(shè)置雇傭蜂數(shù)量Neb=10，Zuplimit=8，循環(huán)次數(shù)M=200.將多次測試所得結(jié)果平均值與文獻(xiàn)［5］的求解結(jié)果平均值進(jìn)行了比較，見表4和圖4.

表4 套結(jié)機(jī)實(shí)例優(yōu)化結(jié)果Tab.4 Optimal solutions for the bar tacking machine case

由圖4可知，用本文改進(jìn)ABC算法求出的開啟工作站數(shù)目、平滑率、拆卸成本3項(xiàng)指標(biāo)均優(yōu)于文獻(xiàn)［5］算法.

本文改進(jìn)ABC算法得到最優(yōu)分配結(jié)果如表4所示.由表4可知，在所有開啟的工作站中，作業(yè)時(shí)間最大值為569.04 s，作業(yè)時(shí)間最小值為558.61 s，相差僅為10.43 s，相對于節(jié)拍時(shí)間600 s，時(shí)差比例僅為1.74%.因此，各工作站作業(yè)負(fù)荷基本處于均衡狀態(tài)，由此說明了本文算法的優(yōu)越性能.

圖4 目標(biāo)函數(shù)結(jié)果對比Fig.4 Result comparison of objective functions

5 結(jié)束語

針對傳統(tǒng)算法在求解多目標(biāo)DLBP問題時(shí)搜索過于隨機(jī)、易早熟和易陷入局部最優(yōu)等方面的不足，提出了一種改進(jìn)的人工蜂群算法.在生成初始解時(shí)，考慮了任務(wù)的危害性和需求對初始解質(zhì)量的影響，提高了初始解針對危害指標(biāo)和需求指標(biāo)的質(zhì)量；在雇傭蜂階段，用可變步長增加較優(yōu)解的搜索機(jī)會，加速淘汰劣解；在觀察蜂階段，以微小的蠕動(dòng)搜索提高解在危害性和需求方面的質(zhì)量；在偵察蜂階段，以分布估計(jì)矩陣引導(dǎo)搜索過程.通過大規(guī)模算例測試驗(yàn)證了算法的有效性.應(yīng)用改進(jìn)ABC算法求解電子套結(jié)機(jī)拆卸實(shí)例，取得了優(yōu)良的求解效果.

下一步的研究方向可將改進(jìn)ABC算法拓展應(yīng)用到不確定時(shí)間拆卸及混合產(chǎn)品拆卸等DLBP問題中去.

［1］ GUPTA S M，GUNGOR A.Product recovery using a disassembly line： challenges and solution［C］∥Proceedings of the 2001 IEEE International Symposium on Electronics and the Environment. Colorado：［s.n.］，2001：36-40.

［2］ 張則強(qiáng)，胡俊逸，程文明.第Ⅰ類雙邊裝配線平衡問題的改進(jìn)蟻群算法［J］.西南交通大學(xué)學(xué)報(bào)，2013，48（4）：724-730.

ZHANG Zeqiang，HU Junyi，CHENG Wenming. Improved ant colony algorithm for two-sided assembly line balancing problem oftypeⅠ［J］. Journalof Southwest Jiaotong University，2013，48（4）：724-730.［3］ DUTA L，F(xiàn)ILIP F G，CACIULA I.Real time balancing of complex disassembly lines［C］∥ 17th World Congress， International Federation of Automatic Control，IFAC.Seoul：［s.n.］，2008：913-918.

［4］ 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.

［5］ 丁力平，譚建榮，馮毅雄，等.基于Pareto蟻群算法的拆卸線平衡多目標(biāo)優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15（7）：1406-1429.

DING Liping，TAN Jianrong，F(xiàn)ENG Yixiong，et al. Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm［J］. ComputerIntegrated ManufacturingSystems，2009，15（7）：1406-1429.

［6］ LAMBERT A，GUPTA S M.Methods for optimum and near optimum disassembly sequencing［J］.International Journal of Production Research，2008，46（11）：2845-2865.

［7］ MCGOVERN S，GUPTA S.Ant colony optimization for disassembly sequencing with multiple objectives［J］. The International Journal of Advanced Manufacturing Technology，2006，30（5/6）：481-496.

［8］ 朱興濤，張則強(qiáng)，朱勛夢，等.求解多目標(biāo)拆卸線平衡問題的一種蟻群算法［J］.中國機(jī)械工程，2014，25（8）：1075-1079.

ZHU Xingtao，ZHANG Zeqiang，ZHU Xunmeng，et al. Ant colony optimization for multi-objective disassembly line balancing problem［J］. China Mechanical Engineering，2014，25（8）：1075-1079.

［9］ HEZER S，KARA Y.A network-based shortest route model for parallel disassembly line balancing problem［J］. International Journal of Production Research，2015，53（6）：1849-1865.

［10］ KALAYCI C B，POLAT O，GUPTA S M.A variable neighbourhood search algorithm for disassembly lines［J］. Journal of Manufacturing Technology Management，2015，26（2）：182-194.

［11］ KALAYCI C B，GUPTA S M.Artificial bee colony algorithm for solving sequence：dependent disassembly linebalancing problem［J］. ExpertSystems with Applications，2013，40（18）：7231-7241.

［12］ KARABOGA D.An idea based on honey bee swarm for numerical optimization In Technical report TR06［R］.Kayseri：Erciyes University，2005.

［13］ 傅繼陽，鐘亮，黃友欽，等.基于量子粒子群算法的門式剛架結(jié)構(gòu)抗風(fēng)優(yōu)化［J］.西南交通大學(xué)學(xué)報(bào)，2013，48（5）：845-850.

FU Jiyang，ZHONG Liang，HUANG Youqin，et al. Wind-resistant optimization of portal frames based on quantum-behaved particle swarm algorithm［J］. JournalofSouthwestJiaotong University，2013，48（5）：845-850.

［14］ 宋榮榮，陳滋利.基于PSO算法的磁浮系統(tǒng)PID控制器優(yōu)化與評價(jià)［J］.西南交通大學(xué)學(xué)報(bào)，2015，50（1）：36-43.

SONG Rongrong，CHEN Zili.Optimization and design of maglev system PID controller based on particle swarm optimization algorithm［J］.Journal of Southwest Jiaotong University，2015，50（1）：36-43.

［15］ KARABOGA D，GORKEMLI B，OZTURK C，et al. A comprehensive survey：artificial bee colony（ABC）algorithm and applications［J］.Artificial Intelligence Review，2014，42（1）：21-57.

［16］ ALAM M S，UL KABIR M，ISLAM M M.Selfadaptation of mutation step size in artificial bee colony algorithm for continuous function optimization［C］∥2010 13th International Conference on Computer and Information Technology（ICCIT）.［S.l.］：IEEE，2010：69-74.

求解拆卸線平衡問題的改進(jìn)人工蜂群算法

張則強(qiáng)， 胡 揚(yáng)， 陳 沖

Improved Artificial Bee Colony Algorithm for Disassembly Line Balancing Problem

ZHANG Zeqiang， HU Yang， CHEN Chong
（School of Mechanical Engineering，Southwest Jiaotong University，Chengdu 610031，China）

The disassembly line balancing problem（DLBP）has been mathematically proved to be NP-complete.The search processes of traditional algorithms for DLBP are so random that they tend to get local optimum due to DLBP's exponential time complexity for large scale cases.To overcome the shortcomings of traditional algorithms，an improved artificial bee colony（ABC）algorithm was proposed based on a multi-objective optimization model for the DLBP，where the main objectives to achieve are to minimize the number of workstations，equilibrate workload，and remove hazardous and high-demand components as early as possible.This algorithm includes four phases.In the initial solution generation phase，the hazardous index and demand measure are used to improve the convergence property of the algorithm.In the employed bee phase，a variable step length search strategy is introduced to take a further search for better solutions and speed up the elimination of inferior solutions.In the onlooker bee phase，a hybrid search strategy that combines the traditional search with the disturbance search is adopted.In the scout bee phase，a search strategy based on estimation of distribution is constructed.The proposed algorithm was applied to solve 70 test cases to verify its validity.As a result，optimal solutions were obtained for 65 cases and the optimization rate is 92.86%.In addition，the algorithm was applied to solve a 10-task case and a 52-task case.The results show that the demand measures to obtain the optimal solution for the 10-task case are 9 730，which is 360 less that by ant colony optimization；meanwhile，better solutions for the balance rate，number of workstations and cost are obtained for the 52-task case.Compared to the traditional ABC algorithm，the improved algorithm has a significantly superior performance in solving large-scale DLBPs.

disassembly line balancing；artificial bee colony algorithm；optimization；disassembly

0258-2724（2016）05-910-08

10.3969/j.issn.0258-2724.2016.05.013

TH165

A

2015-05-04

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

張則強(qiáng)（1978—），男，教授，博士，博士生導(dǎo)師，研究方向?yàn)橹圃煜到y(tǒng)與智能優(yōu)化，E-mail：zzq_22@163.com

張則強(qiáng)，胡揚(yáng)，陳沖.求解拆卸線平衡問題的改進(jìn)人工蜂群算法［J］.西南交通大學(xué)學(xué)報(bào)，2016，51（5）：910-917.

（中文編輯：秦萍玲 英文編輯：蘭俊思）