第Ⅱ類(lèi)拆卸線(xiàn)平衡問(wèn)題建模及優(yōu)化

王書(shū)偉，郭秀萍，劉佳

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

1 引言

科技進(jìn)步以及人們消費(fèi)水平的提高加快了產(chǎn)品更新?lián)Q代的速度，大量廢棄產(chǎn)品導(dǎo)致了嚴(yán)重的資源浪費(fèi)，以及巨大的環(huán)境污染。拆卸是將廢舊產(chǎn)品分解成若干零部件的發(fā)散過(guò)程，其一方面是將有價(jià)值的零部件或原材料從廢舊產(chǎn)品中分離出來(lái)用于再制造，以提高廢舊產(chǎn)品的再利用價(jià)值；另一方面是將有危害的零部件有效拆除，以減少?gòu)U舊產(chǎn)品對(duì)人體和生態(tài)環(huán)境的危害。面對(duì)大規(guī)模產(chǎn)品拆卸，采用流水線(xiàn)的方式可實(shí)現(xiàn)零部件的精細(xì)化拆卸。然而拆卸過(guò)程復(fù)雜，需對(duì)作業(yè)任務(wù)合理排序并均衡分配，以最大化拆卸線(xiàn)效益。

自Gungor和Gupta[1]于2001年提出拆卸線(xiàn)平衡問(wèn)題DLBP，研究者便采用啟發(fā)式算法[2-3]和傳統(tǒng)數(shù)學(xué)方法[4-5]等對(duì)其進(jìn)行求解。啟發(fā)式方法簡(jiǎn)單易實(shí)現(xiàn)，但解精度不高，而傳統(tǒng)數(shù)學(xué)方法雖求解精度高，但耗時(shí)較長(zhǎng)。DLBP已被證明是NP-complete[6]，解空間隨問(wèn)題規(guī)模增大呈爆炸式增長(zhǎng)，因此，求解精度較高、速度更快的智能算法更適用于DLBP的優(yōu)化。考慮不完全拆卸，Ren Yaping等[7]以最大化利潤(rùn)為目標(biāo)，構(gòu)建了部分拆卸DLBP優(yōu)化模型，并提出一種重力搜索算法。針對(duì)拆卸過(guò)程中任務(wù)間的相互干擾，Kalayci等[8-10]分別采用遺傳算法、粒子群搜索算法和變鄰域搜索算法優(yōu)化順序相依DLBP。考慮不同類(lèi)型產(chǎn)品混流拆卸，Agrawal和Tiwari[11]提出了隨機(jī)混流U型DLBP模型，并設(shè)計(jì)了協(xié)作蟻群算法。基于Pareto理論，胡楊等[12]通過(guò)細(xì)菌覓食算法求解多目標(biāo)DLBP。考慮拆卸時(shí)間不確定，Kalayci和Hancilar[13]采用人工蜂群算法求解模糊DLBP。

以上對(duì)DLBP的研究均是在給定拆卸線(xiàn)節(jié)拍時(shí)間(Cycle time, CT)的前提下，最小化工作站開(kāi)啟數(shù)量。參照裝配線(xiàn)平衡問(wèn)題劃分方式[14]，該類(lèi)問(wèn)題可定義為第I類(lèi)DLBP(DLBP-I)，而第II類(lèi)DLBP(DLBP-II)則是在工作站開(kāi)啟數(shù)量一定的情況下最小化節(jié)拍時(shí)間，以最大化拆卸效率。目前對(duì)DLBP-II的研究較少，僅有Bentaha等[15]和Kalayclar等[16]分別以工作站作業(yè)負(fù)荷均衡和利潤(rùn)最大化為目標(biāo)對(duì)其展開(kāi)研究。然而，當(dāng)企業(yè)拆卸線(xiàn)構(gòu)建完畢，工作站的數(shù)量則已確定，為了提高拆卸效率，需最小化節(jié)拍時(shí)間以便在最短周期內(nèi)完成產(chǎn)品拆卸，因此，對(duì)DLBP-II的研究符合企業(yè)實(shí)際拆卸情形。鑒于此，本文針對(duì)拆卸線(xiàn)工作站開(kāi)啟數(shù)量固定，以最短節(jié)拍時(shí)間和均衡工作站上的作業(yè)負(fù)荷為目標(biāo)構(gòu)建第Ⅱ類(lèi)拆卸線(xiàn)平衡問(wèn)題優(yōu)化模型，并提出一種并行動(dòng)態(tài)鄰域深度搜索(Parallel Dynamic Neighborhood Depth Search,PDNDS)算法進(jìn)行求解。

2 問(wèn)題描述與建模

2.1 問(wèn)題描述

圖1 任務(wù)關(guān)系圖

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

相關(guān)符號(hào)如下：

i，j：零部件(任務(wù))編號(hào)，i,j=1, 2, …,N；

k：工作站編號(hào)，k=1, 2, …,M；

ti：任務(wù)i的拆卸作業(yè)時(shí)間；

Pij：零部件i、j的拆卸先后關(guān)系，若零部件i是j的前驅(qū)零部件則Pij=1，否則Pij=0；

xik：0-1變量，若任務(wù)i分配到工作站k則xik=1，否則xik=0。

CT：整數(shù)變量，表示節(jié)拍時(shí)間。

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

考慮最短節(jié)拍時(shí)間和均衡任務(wù)在工作站上的分配，構(gòu)建第II類(lèi)DLBP數(shù)學(xué)模型如下：

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

minf1=CT=max{STk|1≤k≤M}

(1)

(2)

約束條件：

(3)

(4)

(5)

(6)

目標(biāo)函數(shù)：式(1)表示最小化節(jié)拍時(shí)間，即在最短周期內(nèi)完成產(chǎn)品拆卸，以提高拆卸效率；式(2)為平滑指數(shù)，用于平衡各工作站上的任務(wù)量。約束條件：式(3)保證每個(gè)任務(wù)都被分配；式(4)為拆卸優(yōu)先關(guān)系約束，即前驅(qū)任務(wù)要先于后繼任務(wù)拆卸；式(5)為節(jié)拍時(shí)間約束，以限定分配到工作站上的任務(wù)數(shù)量，使其總作業(yè)時(shí)間不超過(guò)節(jié)拍時(shí)間；式(6)表示每個(gè)工作站至少有1個(gè)任務(wù)分配，即無(wú)工作站閑置。

3 PDNDS算法設(shè)計(jì)與實(shí)現(xiàn)

變鄰域搜索算法是由K個(gè)鄰域結(jié)構(gòu)構(gòu)成鄰域結(jié)構(gòu)集，并通過(guò)不斷變化鄰域結(jié)構(gòu)來(lái)擴(kuò)大搜索空間，以尋得問(wèn)題(近似)最優(yōu)解[17]，已在訂單接受[18]、車(chē)輛路徑[19]等諸多組合優(yōu)化中得到應(yīng)用，且取得良好的效果。鑒于此，本文提出一種平行動(dòng)態(tài)鄰域深度搜索算法，所提算法構(gòu)建了兩種鄰域結(jié)構(gòu)集，從而實(shí)現(xiàn)對(duì)兩個(gè)初始解在不同鄰域結(jié)構(gòu)集內(nèi)的并行深度搜索；在鄰域結(jié)構(gòu)變換過(guò)程中設(shè)計(jì)了動(dòng)態(tài)選擇策略，以提高對(duì)解改進(jìn)效果好的鄰域結(jié)構(gòu)被選中的概率；在一定迭代周期后，將兩個(gè)鄰域集內(nèi)的解互換，以實(shí)現(xiàn)在不同鄰域集內(nèi)的搜索；若解在多次迭代后仍未改進(jìn)則對(duì)其實(shí)施干擾，流程如圖2所示。

圖2 PDNDS算法流程

3.1 編碼與解碼

DLBP-II是尋求廢舊產(chǎn)品的一個(gè)可行拆卸序列，該序列在滿(mǎn)足拆卸先后關(guān)系約束前提下，實(shí)現(xiàn)產(chǎn)品零部件的有序拆卸，以達(dá)到最大化拆卸效率等相關(guān)目標(biāo)，屬于離散的組合優(yōu)化問(wèn)題。在第2.2節(jié)符號(hào)說(shuō)明中，每個(gè)零件及其對(duì)應(yīng)的拆卸任務(wù)被賦予了相應(yīng)的整數(shù)編號(hào)，因此，在可行解的編碼過(guò)程中采用整數(shù)排列的編碼方式，排列的順序代表任務(wù)的分配順序。例如整數(shù)排列{1, 3, 2, 5, 4, 6,7}表示在產(chǎn)品拆卸過(guò)程中首先拆卸任務(wù)1，再拆卸任務(wù)3，接著按照排列順序依次對(duì)任務(wù)進(jìn)行作業(yè)，其滿(mǎn)足圖1所示任務(wù)拆卸優(yōu)先關(guān)系，能將產(chǎn)品所有零件分離下來(lái)。

以整數(shù)排列{1,3,2,5,4,6,7}為例進(jìn)行解碼，已知工作站數(shù)量M=4，假設(shè)節(jié)拍時(shí)間CT=11s，首先將任務(wù)1分配至WS1(工作站1)，此時(shí)WS1作業(yè)時(shí)間ST1=10s，空閑時(shí)間IT1=11-10=1s；隨后分配任務(wù)3，由于t3=6s>IT1則需將任務(wù)3分配至WS2，此時(shí)IT2=5s；繼續(xù)分配任務(wù)2，t2為5s等于IT2，因此可將任務(wù)2分配至WS2；然后將任務(wù)5分配至WS3；最后將剩余任務(wù)4、6、7分配到WS4，解碼結(jié)束，如圖3所示。可求得各工作站總作業(yè)時(shí)間分別為：10s、11s、9s和14s，實(shí)際節(jié)拍時(shí)間取最長(zhǎng)工作站作業(yè)時(shí)間，即f1=CT=14s，同時(shí)可得f2=(14-10)2+(14-11)2+(14-9)2+(14-14)2=50。

圖3 解碼結(jié)果

3.2 初始解生成

分別采用最大直接后繼數(shù)(GNIS)和最大任務(wù)處理時(shí)間(LPT)兩種啟發(fā)式方法[21]各生成一個(gè)初始解，具體過(guò)程如下：

第1步：確定理論節(jié)拍時(shí)間CT，并從第一個(gè)工作站k=1開(kāi)始分配任務(wù)。

第2步：由無(wú)前驅(qū)及前驅(qū)任務(wù)已分配的任務(wù)構(gòu)成可選任務(wù)集C*。

第3步：若k=M則轉(zhuǎn)至第5步，否則從C*中選則不超過(guò)當(dāng)前工作站空閑時(shí)間的任務(wù)構(gòu)成可分配任務(wù)集A*。若無(wú)可選任務(wù)，則啟動(dòng)下一工作站，并重復(fù)第3步。

第4步：從A*中根據(jù)LPT/GNIS啟發(fā)式方法，選取作業(yè)時(shí)間最長(zhǎng)的任務(wù)/后繼任務(wù)數(shù)最多的任務(wù)分配至當(dāng)前工作站k，然后轉(zhuǎn)至第2步。

第5步：若C*不為空，則從C*中選取一個(gè)任務(wù)分配至最后一個(gè)工作站M，然后轉(zhuǎn)至第2步，否則初始解生成結(jié)束。

3.3 局部搜索

PDNDS算法構(gòu)建兩種鄰域結(jié)構(gòu)集，實(shí)現(xiàn)對(duì)兩個(gè)初始解的并行深度搜索。考慮鄰域結(jié)構(gòu)的規(guī)模，為每個(gè)鄰域結(jié)構(gòu)集設(shè)計(jì)了3種鄰域結(jié)構(gòu)，第一個(gè)鄰域結(jié)構(gòu)集Nk(k=1,2,3)由交換(圖4a)、插入(圖4b)和交叉(圖4c)組成，鄰域結(jié)構(gòu)規(guī)模相對(duì)較小，側(cè)重對(duì)解的局部搜索，第二個(gè)鄰域結(jié)構(gòu)集Nl(l=1,2,3)由逆序(圖4d)、多次插入(圖4e)和多次交換(圖4f)組成，鄰域結(jié)構(gòu)規(guī)模相對(duì)較大，側(cè)重對(duì)解的廣度搜索。在鄰域結(jié)構(gòu)變換過(guò)程中采用動(dòng)態(tài)選擇策略，即在搜索過(guò)程中記錄鄰域結(jié)構(gòu)Nk對(duì)解改進(jìn)次數(shù)INTk，以輪盤(pán)賭方法選擇鄰域結(jié)構(gòu)。當(dāng)鄰域結(jié)構(gòu)被選擇后，從該鄰域中選擇含有n個(gè)元素的子集進(jìn)行局部搜索，步驟如下：

步驟1：確定參數(shù)，構(gòu)造鄰域結(jié)構(gòu)集Nk(k=1,2,3)，并設(shè)INTk=1(k=1, 2, 3)，初始解為x。

步驟2：擾動(dòng)，隨機(jī)選一鄰域結(jié)構(gòu)并在該鄰域內(nèi)任意選一解x'。

步驟3：選擇鄰域結(jié)構(gòu)，根據(jù)改進(jìn)次數(shù)以輪盤(pán)賭的方法動(dòng)態(tài)選擇鄰域結(jié)構(gòu)Nk。

步驟4：局部搜索，在解x'鄰域Nk(x')中選擇n個(gè)元素進(jìn)行局部搜索獲得解x"。

步驟5：更新解，若解x"優(yōu)于x，則x=x"，INTk=INTk+1，然后轉(zhuǎn)至步驟2。

步驟6：重復(fù)步驟2-5，直至停止。

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

3.4 局部干擾

為加快個(gè)體跳出局部最優(yōu)，本文設(shè)置擾動(dòng)閾值。在尋優(yōu)過(guò)程中，若解x經(jīng)過(guò)ut次搜索后仍未改進(jìn)，則視其已陷入局部最優(yōu)，將采用變異操作方法進(jìn)行干擾，如圖5所示，新生成的解既包含了當(dāng)前解的部分優(yōu)秀序列片段，又有新構(gòu)建序列片段的注入，以引導(dǎo)個(gè)體x快速跳出局部最優(yōu)。

圖5 變異操作

3.5 節(jié)拍時(shí)間變化策略

DLBP-II的理論最小節(jié)拍時(shí)間CTlow為工作站平均拆卸時(shí)間與任務(wù)最長(zhǎng)拆卸時(shí)間中的大者，CTlow=max{∑ti/M, max{ti|1≤i≤N}}。最優(yōu)節(jié)拍時(shí)間的搜索通常是從理論最小節(jié)拍時(shí)間CTlow開(kāi)始，令CT=CTlow，如果搜索到的可行解節(jié)拍時(shí)間CTnow大于當(dāng)前設(shè)置的節(jié)拍時(shí)間CT，那么在下一次迭代時(shí)增加節(jié)拍時(shí)間CT=CT+1；反之則縮小節(jié)拍時(shí)間CT=CT-1，這種增加縮小方式節(jié)拍時(shí)間變化幅度為1，搜索時(shí)間復(fù)雜度為O(N)，效率較低。鑒于此，所提算法在節(jié)拍時(shí)間變化過(guò)程中采用基于二分法的定界策略，如圖6所示，若尋得可行解節(jié)拍時(shí)間CTnow>CT，則在下一次搜索時(shí)令CTlow=CT，CT=(CTnow+CT)/2；若CTnow≤CT，則CTlow不變，CT=(CTlow+CTnow)/2。二分法搜索的時(shí)間復(fù)雜度為O(logN)，搜索效率較高，能夠?qū)崿F(xiàn)節(jié)拍時(shí)間向最優(yōu)節(jié)拍時(shí)間的快速靠攏。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提PDNDS算法的有效性，采用10個(gè)零件的產(chǎn)品拆卸算例(P10)、25個(gè)零件的手機(jī)拆卸算例(P25)[11]和47個(gè)零件的筆記本拆卸算例(P47)進(jìn)行測(cè)試[13]，并與DABC[21]、PSO[9]算法求解以上三個(gè)算例的結(jié)果進(jìn)行比較。所有算法均用C++編碼，在Corei3-7100 3.9GHz，4G內(nèi)存電腦上運(yùn)行，為保證結(jié)果的可靠性，P10、P25、P47分別在0.01s、0.5s、2.5s內(nèi)求解，每個(gè)運(yùn)行30次，求得結(jié)果如表1所示。

圖6 二分法定界策略

對(duì)于小規(guī)模算例P10，在不同工作站數(shù)量情況下，PDNDS、DABC和PSO三種算法均能搜索到問(wèn)題的最優(yōu)解且隨著工作站數(shù)量的增多，節(jié)拍時(shí)間呈縮短趨勢(shì)。當(dāng)節(jié)拍時(shí)間一定，工作站數(shù)量越多平滑指數(shù)越大(如圖7所示)，說(shuō)明工作站的空閑時(shí)間增加，拆卸線(xiàn)的平衡效果變差。表2為5個(gè)工作站情況下，所得最優(yōu)拆卸序列任務(wù)在拆卸線(xiàn)上的分配。此時(shí)，實(shí)際節(jié)拍時(shí)間等于理論最小節(jié)拍時(shí)間，即最長(zhǎng)任務(wù)拆卸時(shí)間36，且在節(jié)拍時(shí)間內(nèi)實(shí)現(xiàn)了任務(wù)在各工作站上的均衡分配。

圖7 P10算例節(jié)拍時(shí)間和平滑指數(shù)隨工作站數(shù)量變化趨勢(shì)

對(duì)于中規(guī)模算例P25，PDNDS求得平均值和標(biāo)準(zhǔn)差均不比DABC和PSO算法差，尤其是當(dāng)工作站數(shù)量為8和9時(shí)，PDNDS能夠獲得更好的求解效果且算法穩(wěn)定性更好，PDNDS良好的尋優(yōu)性能在P25算例上開(kāi)始顯現(xiàn)。

對(duì)于大規(guī)模算例P47，除了工作站數(shù)量為9時(shí)，PDNDS獲得的節(jié)拍時(shí)間平均值與其他兩種算法相等之外，在節(jié)拍時(shí)間和平滑指數(shù)方面，PDNDS所求得的平均值和標(biāo)準(zhǔn)差均好于DABC和PSO，且優(yōu)勢(shì)顯著。圖8為三種算法在不同工作站數(shù)量情況下求得節(jié)拍時(shí)間的對(duì)比，可以看出，除了P47(6)、P47(9)，PDNDS搜索到CT的上界與DABC一致外，在其他情況下，PDNDS搜索到CT的上界均小于DABC和PSO，且在算例P47(7)和P47(8)中，PDNDS求得CT的下界也小于DABC和PSO，體現(xiàn)出更強(qiáng)的尋優(yōu)性能。

圖8 三種算法求解P47算例的節(jié)拍時(shí)間對(duì)比

表1 PDNDS、DABC和PSO求解結(jié)果對(duì)比(AVG為平均值，SD為標(biāo)準(zhǔn)差)

算例工作站數(shù)PDNDSDABCPSOf1f2f1f2f1f2AVGSDAVGSDAVGSDAVGSDAVGSDAVGSDP1028101081010810103580130580130580130446011704601170460117053604303604303604306360503036050303605030

續(xù)表1 PDNDS、DABC和PSO求解結(jié)果對(duì)比(AVG為平均值，SD為標(biāo)準(zhǔn)差)

此外，通過(guò)表1可以看出，在不同情況下，拆卸線(xiàn)所能達(dá)到的平衡效果也不相同，其中P47(4)情況下，PDNDS所得到的最優(yōu)拆卸序列平滑指數(shù)為0，說(shuō)明在拆卸過(guò)程中，每個(gè)工作站所分配的任務(wù)總作業(yè)時(shí)間恰好等于節(jié)拍時(shí)間，各工作站均滿(mǎn)負(fù)荷運(yùn)轉(zhuǎn)，此時(shí)拆卸線(xiàn)運(yùn)行效率最高、平衡效果最好。因此，產(chǎn)

表2 P10算例5個(gè)工作站數(shù)量下的任務(wù)分配

品拆卸過(guò)程中考慮平滑指數(shù)，可實(shí)現(xiàn)拆卸任務(wù)在工作站上的均衡分配，保證拆卸線(xiàn)高效運(yùn)行。通過(guò)以上對(duì)比表明PDNDS算法能夠?qū)ふ业絾?wèn)題更優(yōu)解，求解穩(wěn)定性更高，尋優(yōu)能力更強(qiáng)，特別是對(duì)于中大規(guī)模算例，PDNDS算法在求解質(zhì)量、求解穩(wěn)定性方面的優(yōu)越性體現(xiàn)的更加充分。

5 結(jié)語(yǔ)

本文針對(duì)工作站數(shù)量確定情況下的拆卸線(xiàn)平衡問(wèn)題進(jìn)行研究，建立以最短節(jié)拍時(shí)間和均衡工作站空閑時(shí)間為目標(biāo)的第II類(lèi)拆卸線(xiàn)平衡問(wèn)題數(shù)學(xué)模型，并提出一種并行動(dòng)態(tài)鄰域深度搜索算法進(jìn)行求解。所提算法通過(guò)構(gòu)建兩種鄰域結(jié)構(gòu)集，實(shí)現(xiàn)對(duì)兩個(gè)初始解在不同鄰域結(jié)構(gòu)集內(nèi)的并行深度搜索。在節(jié)拍時(shí)間調(diào)整過(guò)程中，采用基于二分法的定界策略，實(shí)現(xiàn)節(jié)拍時(shí)間向最優(yōu)節(jié)拍時(shí)間的快速靠攏。

對(duì)P10、P25、P47三個(gè)算例進(jìn)行求解，驗(yàn)證了本文所提PDNDS算法尋優(yōu)效果更好。通過(guò)優(yōu)化拆卸方案發(fā)現(xiàn)，合理對(duì)作業(yè)任務(wù)進(jìn)行排序，并平衡任務(wù)在各個(gè)工作站的分配，能夠?qū)崿F(xiàn)拆卸線(xiàn)節(jié)拍時(shí)間更短，單位時(shí)間內(nèi)拆卸的廢舊產(chǎn)品數(shù)量更多，可以充分發(fā)揮拆卸線(xiàn)的產(chǎn)能，節(jié)約資源。此外，在拆卸過(guò)程中，考慮任務(wù)的平衡分配可以實(shí)現(xiàn)工作站上作業(yè)負(fù)荷大致相同，從而保證工人作業(yè)效率，維持整個(gè)拆卸線(xiàn)的穩(wěn)定運(yùn)行。