王書偉， 郭秀萍， 劉 佳

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，四川 成都 610031； 2.青島理工大學(xué) 商學(xué)院，山東 青島 266520)

0 引言

信息技術(shù)的革新與激烈的市場(chǎng)競(jìng)爭(zhēng)，促使電子產(chǎn)品更新?lián)Q代速度加快，而消費(fèi)者不斷變化的個(gè)性化需求，更是加劇了電子產(chǎn)品的淘汰速度。作為目前增速最快的一類固體垃圾，電子廢棄物對(duì)人體和環(huán)境都具有較大危害，但同時(shí)也蘊(yùn)藏著大量可回收利用資源，若能有效提取和利用將給社會(huì)帶來巨大的經(jīng)濟(jì)和環(huán)境效益。因此，電子廢棄物的回收再制造問題備受關(guān)注。

面對(duì)大規(guī)模廢舊產(chǎn)品，為了提高拆卸效率，采用流水線作業(yè)方式已成為企業(yè)的最佳選擇[1]，但通過流水線對(duì)廢舊產(chǎn)品進(jìn)行作業(yè)時(shí)，會(huì)發(fā)生零部件的作業(yè)任務(wù)分配不平衡問題。針對(duì)該問題，Gupta和Gungor[2,3]于2001年首次提出拆卸線平衡問題(DLBP)，并建立了DLBP數(shù)學(xué)優(yōu)化模型。隨后，一些啟發(fā)式算法最先被應(yīng)用到DLBP中以獲取近似最優(yōu)解，如：貪婪算法[4,5]、2-opt啟發(fā)式算法[6]。啟發(fā)式算法構(gòu)造簡(jiǎn)單、求解速度快，但不具通用性且求解質(zhì)量不高。因此，分段線性規(guī)劃[7]、分支定界[8]、最短路徑[9]和整數(shù)規(guī)劃[10]等數(shù)學(xué)方法被用于求解DLBP以獲得問題的精確解，但DLBP是NP-complete問題[11]，其無法應(yīng)對(duì)大規(guī)模DLBP。因此，一些研究者將智能算法，如蟻群算法[12]、變鄰域搜索算法[13]、人工魚群算法[14]、人工蜂群算法[15]等應(yīng)用于DLBP以獲得問題的滿意解。

以上研究的DLBP都是針對(duì)產(chǎn)品在直線型布局拆卸線進(jìn)行作業(yè)，且零部件間僅考慮優(yōu)先關(guān)系約束。然而，當(dāng)面對(duì)回收數(shù)量不定，品種多樣的產(chǎn)品拆卸時(shí)，拆卸線采用U型布局效率更高。針對(duì)拆卸時(shí)間不確定的多產(chǎn)品混流拆卸，Agrawal等[16]對(duì)隨機(jī)混流U型DLBP進(jìn)行了研究。以精益生產(chǎn)為準(zhǔn)則，李明等[17]提出了多目標(biāo)U型DLBP。對(duì)于一些結(jié)構(gòu)復(fù)雜的產(chǎn)品，在拆卸時(shí)，部分零件之間雖然不存在拆卸優(yōu)先關(guān)系，但也會(huì)相互干擾，妨礙對(duì)方的作業(yè)操作，從而導(dǎo)致零件作業(yè)時(shí)間增加，影響拆卸線平衡，此類問題被定義為順序相依問題。Kalayci和Gupta[18]于2013年首次將順序相依問題引入直線型DLBP中，提出了順序相依拆卸線平衡問題(SDDLBP)。隨后，Kalayci與其合作者[18～20]分別采用混合遺傳算法、禁忌算法和人工蜂群算法求解直線型SDDLBP。

受信息技術(shù)快速革新的影響，電子廢棄物的回收數(shù)量波動(dòng)較大，且種類繁多、構(gòu)造復(fù)雜。因此，分配更靈活、效率更高的U型線更適合用于廢舊電子產(chǎn)品拆卸[21]。鑒于上述分析，本文針對(duì)拆卸線以U型模式布局，考慮拆卸過程中任務(wù)間的優(yōu)先關(guān)系和順序相依關(guān)系約束，構(gòu)建了多目標(biāo)U型順序相依拆卸線平衡問題(USDDLBP)模型，并提出一種自適應(yīng)人工蜂群算法(SAABC)。在局部搜索過程中采用了動(dòng)態(tài)鄰域搜索方法，以提高算法局部開發(fā)“Exploration”效率；在全局搜索過程中采用基于當(dāng)前最優(yōu)解的變異操作，以加速跳出局部最優(yōu)，從而增強(qiáng)算法的探索“Exploitation”能力。

圖1 產(chǎn)品任務(wù)關(guān)系圖

1 問題描述與數(shù)學(xué)模型

圖1為一個(gè)含有8個(gè)零部件產(chǎn)品任務(wù)關(guān)系圖，圓內(nèi)數(shù)字表示零件(任務(wù))編號(hào)，圈外數(shù)字對(duì)應(yīng)該零件的作業(yè)時(shí)間，實(shí)箭頭為拆卸過程中零件之間的優(yōu)先關(guān)系，灰色背景表示有危害零件。虛箭頭為零件間的相互干擾，虛線上數(shù)字為干擾時(shí)間增量。通過圖1可以看出，零件2/3、6/7之間無拆卸優(yōu)先關(guān)系但存在順序相依關(guān)系。以零件6/7拆卸為例，若零件6先于零件7拆卸，零件7將干擾零件6的作業(yè)操作，導(dǎo)致零件6實(shí)際拆卸作業(yè)時(shí)間增至8+1=9s(秒)，增量為1s；反之，若零件7在零件6之前拆卸，零件7作業(yè)時(shí)間將增加5s。

U型拆卸線是將工作站按“U”型排列，其布局更緊湊、更柔性，如圖2所示。U型線入口與出口在同一端，拆卸時(shí)任務(wù)在滿足優(yōu)先關(guān)系約束前提下，可從前向、后向或雙向分配至工作站。與直線型相比，U型線上任務(wù)分配更加靈活，因此，問題解規(guī)模更大。本文所提出的USDDLBP是在拆卸產(chǎn)品時(shí)，考慮零部件間的優(yōu)先關(guān)系和順序相依關(guān)系，在滿足節(jié)拍時(shí)間條件下，將所有零部件的作業(yè)任務(wù)平衡分配到U型線所開啟的工作站上，以滿足相關(guān)目標(biāo)需求。按照目標(biāo)重要程度不同，由高到低依次考慮以下4個(gè)目標(biāo)：

(1)最小化工作站開啟數(shù)量。拆卸過程中所需工作站數(shù)量越少，產(chǎn)品拆卸固定成本也將越低。

(1)

式中zk為0-1變量，表示工作站k是否開啟。

(2)最小化平滑指數(shù)。為保證拆卸線高效運(yùn)行，應(yīng)平衡各工作站空閑時(shí)間即作業(yè)負(fù)荷。

(2)

(3)盡早移除有危害零部件，以降低危害，如主板和鍵盤底片上的鈹，電腦顯示器陰極射線管熒屏上的鋇，電路板中的溴化阻燃物等，該類有危害零部件應(yīng)優(yōu)先拆卸，以將危害降至最低。

(3)

式中PSl表示拆卸序列中第l個(gè)位置對(duì)應(yīng)的零件編號(hào)，例如序列{1,5,2,3,6,7,4}，第2個(gè)位置PS2=5，hi為零件i的危害性，有危害則hi=1，否則hi=0。

(4)盡早拆卸需求高的零部件。價(jià)值高、需求大的零部件應(yīng)優(yōu)先拆卸，以滿足市場(chǎng)需求。

(4)

式中di為零件i的需求量。

圖2 U型布局拆卸線

2 自適應(yīng)人工蜂群算法

Karaboga[22]在2005年首次提出人工蜂群算法，其包含雇傭蜂、觀察蜂和偵察蜂三種角色蜜蜂，三者分工協(xié)作搜索蜜源，最終獲得問題的(近似)最優(yōu)解。ABC算法參數(shù)設(shè)置少、魯棒性強(qiáng)、易于實(shí)現(xiàn)，已經(jīng)廣泛應(yīng)用于多種優(yōu)化問題，但也存在局部搜索效率較低、易早熟等缺陷。針對(duì)USDDLBP，本文提出一種自適應(yīng)人工蜂群算法，從初始解生成、雇傭蜂局部開發(fā)、觀察蜂跟隨以及偵察蜂全局搜索等環(huán)節(jié)進(jìn)行改進(jìn)，以提高算法的搜索性能，具體實(shí)現(xiàn)如下。

2.1 編碼與解碼

為了更有效描述U型線可雙向分配任務(wù)的特點(diǎn)，引入影子約束[23]至圖1產(chǎn)品拆卸示例，如圖3所示。從虛節(jié)點(diǎn)0開始，可向后在滿足優(yōu)先關(guān)系前提下分配任務(wù)至U型線入口工作站上，或向前滿足影子關(guān)系前提下分配任務(wù)至U型線出口工作站上。USDDLBP是將零件的作業(yè)任務(wù)平衡分配至拆卸線所開啟的工作站上，屬于離散組合優(yōu)化問題，針對(duì)其特點(diǎn)，采用一種整數(shù)排列編碼方式。數(shù)字表示任務(wù)(零件)編號(hào)，正、負(fù)號(hào)分別表示作業(yè)任務(wù)從入口、出口分配至U型線，整數(shù)排列順序表示任務(wù)拆卸前后順序。以排列{1,-8,2,3,-6,-7,5,4}(正號(hào)省略)為例，其表示先將任務(wù)1從U型線入口分配，然后再?gòu)某隹诜较蚍峙淙蝿?wù)8，以此類推，直至所有任務(wù)拆卸完畢，其滿足圖1拆卸優(yōu)先關(guān)系，是一個(gè)可行的拆卸方案。

表1 解碼結(jié)果(CT=17s)

2.2 初始化種群

在ABC算法中，一個(gè)蜜源對(duì)應(yīng)問題的一個(gè)可行解，且每個(gè)蜜源僅能被一個(gè)雇傭蜂或觀察蜂開采，因此，蜜源數(shù)量(SN)與雇傭蜂、觀察蜂數(shù)量一致。為了保證初始種群的生成質(zhì)量與多樣性，采用最大處理時(shí)間(LPT)啟發(fā)式方法與單點(diǎn)左操作隨機(jī)生成法相結(jié)合的初始化策略。LPT在任務(wù)選擇分配時(shí)賦予作業(yè)時(shí)間最長(zhǎng)的任務(wù)最高權(quán)重，即作業(yè)時(shí)間最長(zhǎng)的任務(wù)將優(yōu)先分配。單點(diǎn)左操作是在可行解序列上隨機(jī)產(chǎn)生一點(diǎn)，該點(diǎn)左側(cè)在滿足優(yōu)先關(guān)系前提下重新生成，右側(cè)則不變(圖4d)。在初始化種群時(shí)，首先通過LPT生成一個(gè)較高質(zhì)量的初始解x，然后在x基礎(chǔ)上通過單點(diǎn)左操作生成種群中其余的SN-1個(gè)解，具體生成過程如圖4所示。

圖4中的可選任務(wù)集C*根據(jù)引入影子約束的任務(wù)優(yōu)先關(guān)系圖進(jìn)行構(gòu)建。若任務(wù)i未分配，且其無前驅(qū)或前驅(qū)任務(wù)已經(jīng)分配，則將+i添加到C*以表示入口任務(wù)；若任務(wù)j未分配，且其無后繼或后繼任務(wù)已經(jīng)分配，則將-j添加到C*表示出口任務(wù)?？煞峙淙蝿?wù)集A*是從C*中選擇實(shí)際拆卸時(shí)間不超過當(dāng)前工作站所剩余空閑時(shí)間的任務(wù)組成。

圖3 引入影子約束的產(chǎn)品任務(wù)優(yōu)先關(guān)系

圖4 初始解生成過程

2.3 局部開發(fā)

步驟1初始化。確定鄰域集Nk(k=1,…,K)，設(shè)置Sk(k=1,…,K)，選定初始解x。

步驟2鄰域選擇。根據(jù)自適應(yīng)選擇機(jī)制動(dòng)態(tài)選擇鄰域結(jié)構(gòu)k。

步驟3擾動(dòng)。隨機(jī)選擇一點(diǎn)x′∈Nk(x)。

步驟4局部搜索。在x′鄰域Nk(x′)的子集內(nèi)進(jìn)行局部搜索獲得解x″。

步驟5更新最優(yōu)解。若x″優(yōu)于x，則x=x″，Sk=Sk+1。

步驟6重復(fù)步驟2～5，直至結(jié)束。

根據(jù)USDDLBP的問題特征和編碼特點(diǎn)，選擇由突變、逆序和插入三種鄰域操作組成SADNS的鄰域結(jié)構(gòu)集(圖5a～圖5c)。

(1)突變操作。在可行解上選擇一點(diǎn)，將該點(diǎn)上的任務(wù)符號(hào)變?yōu)槠湎喾捶?hào)，然后重新分配。

(2)逆序操作。在可行解上隨機(jī)選擇兩個(gè)位置，將兩個(gè)位置間的任務(wù)逆序排列。

(3)插入操作。在可行解上選擇兩個(gè)位置i、j，將位置i的任務(wù)插入到位置j，然后將j至i-1間的任務(wù)向后依次移動(dòng)。

圖5 鄰域結(jié)構(gòu)

2.4 蜜源選擇評(píng)價(jià)

在采蜜過程中，隨著搜索的不斷深入，雇傭蜂所尋得蜜源質(zhì)量差異將逐漸縮小，因此無論選取哪一個(gè)目標(biāo)函數(shù)作為適應(yīng)值評(píng)價(jià)函數(shù)，觀察蜂都不能在整個(gè)迭代過程中對(duì)蜜源進(jìn)行有效評(píng)價(jià)。為了解決該問題，采用分段選擇法，在迭代前期，選用平滑指數(shù)作為適應(yīng)值評(píng)價(jià)函數(shù)，并以輪盤賭法選擇雇傭蜂跟隨[18,20]；隨著迭代的深入，當(dāng)所有雇傭蜂攜帶蜜源的平滑指數(shù)相同時(shí)，則以錦標(biāo)賽法選擇雇傭蜂跟隨。觀察蜂確定雇傭蜂跟隨后，將采用與其相同的方法對(duì)蜜源進(jìn)行深度開發(fā)。

2.5 全局探索

在搜索過程中，若蜜源經(jīng)過upLimit次迭代后質(zhì)量仍未提高則視為開發(fā)已盡將被丟棄(該蜜源所對(duì)應(yīng)的解陷入局部最優(yōu))，此時(shí)，偵察蜂將在全局范圍內(nèi)探索新蜜源。USDDLBP是NP-complete問題，解空間通常是無界的，因此，在整個(gè)解空間隨機(jī)探索新蜜源，效率低且不易跳出局部最優(yōu)。而在搜索時(shí)，當(dāng)前最優(yōu)解的鄰域周邊往往蘊(yùn)藏著更為豐富的蜜源，因此，對(duì)其周邊鄰域進(jìn)行探索效率會(huì)更高。鑒于此，在該階段，基于當(dāng)前最優(yōu)解采用單點(diǎn)右操作實(shí)現(xiàn)新蜜源的搜索(圖4e)以加速跳出局部最優(yōu)。

2.6 SAABC算法流程

所提算法采用啟發(fā)式方法與隨機(jī)生成法構(gòu)造初始化種群。種群初始化后，雇傭蜂采用SADNS方法對(duì)蜜源周邊進(jìn)行開發(fā)；然后，觀察蜂采用分段方式選擇雇傭蜂跟隨，并采用與其相同的方法繼續(xù)開發(fā)蜜源；當(dāng)蜜源開發(fā)完畢，偵察蜂采用基于當(dāng)前最優(yōu)解的變異操作探索新蜜源。三種角色蜜蜂分工協(xié)作，完成最優(yōu)蜜源的搜索，算法流程如圖6所示。

圖6 SAABC算法流程

3 算例驗(yàn)證

為了有效測(cè)試所提算法的求解性能，采用一組基準(zhǔn)算例和2個(gè)實(shí)例進(jìn)行驗(yàn)證，同時(shí)與ABC[20]和PVNS[24]兩種算法求解結(jié)果進(jìn)行對(duì)比。所有測(cè)試均用C++編碼，在Core I7-7500U 2.7Hz，8G內(nèi)存電腦上運(yùn)行。

3.1 基準(zhǔn)測(cè)試

目前已發(fā)表文獻(xiàn)中，尚無U型順序相依問題基準(zhǔn)測(cè)試算例，為了驗(yàn)證所提SAABC算法的有效性，在此設(shè)計(jì)了USDDLBP的一組基準(zhǔn)算例。具體如下：算例規(guī)模(零件數(shù)量)分布在12到87之間，從由12個(gè)零件組成開始每次增加15，節(jié)拍時(shí)間設(shè)為26s(CT=26)。每個(gè)零件的拆卸時(shí)間由式(5)所得，其中拆卸第一個(gè)耗時(shí)7s的零件有危害，第一個(gè)耗時(shí)5s的零件有市場(chǎng)需求。零件之間的拆卸優(yōu)先關(guān)系和順序相依關(guān)系分別由式(6)和(7)確定。

為了有效比較，SAABC、ABC和PVNS三種算法均在相同的時(shí)間內(nèi)求解每個(gè)算例。算例P12和P27求解時(shí)間為5s，P42和P57為25s，P72和P87為125s。每個(gè)算例求解25次，得到的最優(yōu)解、均值和標(biāo)準(zhǔn)差如表2、表3所示。

(5)

(6)

(7)

對(duì)于算例P12和P27，二者解空間規(guī)模相對(duì)較小，ABC、PVNS和SAABC三種算法在指定時(shí)間內(nèi)每次都可搜索到問題的最優(yōu)解。然而隨著問題規(guī)模增大，解空間呈指數(shù)增加，搜尋問題最優(yōu)解變的愈加困難。對(duì)于P42算例，三種算法在25次求解中僅可尋得問題的近似最優(yōu)解。通過表3可以看出，SAABC算法在工作站數(shù)量f1和平滑指數(shù)f2兩個(gè)目標(biāo)的平均值方面明顯好于ABC和PVNS。雖然在標(biāo)準(zhǔn)差方面要比二者稍差，原因在于SAABC能夠搜索到更多比ABC和PVNS兩種算法更優(yōu)的解(見表2)，從而導(dǎo)致其標(biāo)準(zhǔn)差波動(dòng)略大，這也恰好說明SAABC具有更好的搜索性能。

隨著問題規(guī)模的繼續(xù)增加，對(duì)于P57、P72和P87三個(gè)算例，三種算法除了在P57和P87上的目標(biāo)函數(shù)f1一致外，SAABC在目標(biāo)函數(shù)f1、f2和f3的平均值與標(biāo)準(zhǔn)差上均優(yōu)于ABC和PVNS，且優(yōu)勢(shì)顯著。表明SAABC在25次求解中，解的波動(dòng)性更小，穩(wěn)定性更好，整體效果更佳。

此外，在所能搜索到的最優(yōu)解方面，如表2所示，除了在算例P12和P27上三種算法均可搜索到問題最優(yōu)解，以及在P57算例SAABC與PVNS最優(yōu)解相同外，在其它算例上SAABC算法所能搜索到的最優(yōu)解質(zhì)量更高，體現(xiàn)出更強(qiáng)的尋優(yōu)能力。

通過以上對(duì)比表明SAABC算法具備良好的尋優(yōu)能力和更高的搜索穩(wěn)定性，在求解USDDLBP過程中，可尋得USDDLBP更優(yōu)解，在中大規(guī)模問題上其優(yōu)越的搜索性能體現(xiàn)的更加充分。

表2 ABC、PVNS和SAABC求得最優(yōu)解對(duì)比

3.2 實(shí)例分析

以含有10個(gè)零件的P10產(chǎn)品和25個(gè)零件的P25手機(jī)拆卸實(shí)例[24]為例，分別在U型和直線型拆卸線進(jìn)行拆卸，采用所提SAABC算法進(jìn)行求解，以獲得最優(yōu)拆卸方案。

對(duì)于P10實(shí)例，理論解空間為10！，規(guī)模較小，可搜索到問題最優(yōu)解：f1=5，f2=61，f3=6，f4=8880，該最優(yōu)解對(duì)應(yīng)的拆卸方案如表4所示。圖7(b)為此拆卸方案在U型線上各工作站的作業(yè)任務(wù)分配情況，在整個(gè)拆卸過程中，任務(wù)6對(duì)任務(wù)9、任務(wù)4對(duì)任務(wù)1和5、任務(wù)5對(duì)任務(wù)6、任務(wù)3對(duì)任務(wù)2造成了干擾，導(dǎo)致任務(wù)9、1、5、6、2的作業(yè)時(shí)間分別增加了3s、4s、4s、2s、3s。對(duì)于P25拆卸實(shí)例，相比于P10其解規(guī)模顯著增大，算法在指定的100s內(nèi)所能尋得問題的當(dāng)前最優(yōu)解為：f1=10，f2=9，f3=76，f4=909，所對(duì)應(yīng)的拆卸任務(wù)方案如表4所示。

表4為直線型和U型兩種布局下，拆卸P10和P25最優(yōu)方案對(duì)比。在兩種模式下所開啟的工作站數(shù)量未發(fā)生變化。除了P10算例，采用U型布局的危害指數(shù)增加1以外，在平滑指數(shù)、危害指數(shù)和需求指數(shù)方面，U型布局均優(yōu)于直線型布局。圖7為P10實(shí)例在兩種拆卸線布局模式下的最優(yōu)序列作業(yè)任務(wù)分配情況對(duì)比，可以看出，U型線的布局設(shè)計(jì)更加柔性，可使拆卸任務(wù)更加靈活的在工作站上進(jìn)行分配，因此U型布局通常比直線型布局具有更高的拆卸效率或更低的危害和需求指數(shù)。

表3 ABC、PVNS和SAABC求解基準(zhǔn)算例均值、標(biāo)準(zhǔn)差對(duì)比

4 結(jié)論

在實(shí)際拆卸過程中，部分零部件之間會(huì)存在相互干擾，導(dǎo)致作業(yè)時(shí)間增加，從而影響拆卸線平衡，基于該現(xiàn)象，本文建立了U型SDDLBP多目標(biāo)優(yōu)化模型。通過求解不同規(guī)模算例和拆卸實(shí)例，驗(yàn)證了所提算法在求解USDDLBP的優(yōu)越性。與直線型拆卸線相比，U型線布局更加靈活柔性，可使拆卸任務(wù)更合理的進(jìn)行分配。

后續(xù)研究可針對(duì)拆卸過程中零部件作業(yè)時(shí)間的不確定，考慮大型產(chǎn)品雙邊拆卸，以及多產(chǎn)品類型混合拆卸，此外還有以利潤(rùn)等為目標(biāo)的產(chǎn)品不完全或部分拆卸。

表4 U型和直線型布局結(jié)果對(duì)比