孫嫻靜，唐秋華，鄧明星

(武漢科技大學(xué) 1.冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室；2.機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室；3.汽車與交通工程學(xué)院，湖北 武漢 430081)

拆卸是將產(chǎn)品或裝配體進(jìn)行拆解，獲取目標(biāo)零部件的過程。與焚燒、掩埋等其他報(bào)廢產(chǎn)品處理方法相比，通過拆卸來獲取可直接重用或可修復(fù)的零部件，實(shí)現(xiàn)資源的再利用，故而拆卸具有顯著的經(jīng)濟(jì)和環(huán)境優(yōu)勢(shì)，在報(bào)廢產(chǎn)品的再利用和再制造過程中具有重要的地位。

拆卸序列規(guī)劃是指根據(jù)產(chǎn)品中零部件之間的幾何結(jié)構(gòu)、功能等一些預(yù)定的性能指標(biāo)探索確定合理可行的拆卸序列，并從中選擇最優(yōu)的序列以指導(dǎo)產(chǎn)品的拆卸，達(dá)到預(yù)期的拆卸目標(biāo)。根據(jù)拆除零部件的邏輯順序，拆卸可以分為兩大類：順序拆卸和并行拆卸。因此，拆卸序列規(guī)劃也可以分為順序拆卸規(guī)劃和并行拆卸規(guī)劃。并行拆卸分為同步并行拆卸和異步并行拆卸。

到目前為止，已經(jīng)有很多學(xué)者對(duì)順序拆卸規(guī)劃問題進(jìn)行了研究，開發(fā)出許多模型和方法。但隨著技術(shù)的發(fā)展，對(duì)拆卸時(shí)效的要求逐漸提高，并行拆卸序列規(guī)劃問題越來越受到學(xué)者的關(guān)注與研究。Zhang等[1]針對(duì)性地建立拆卸混合圖模型來解釋4種不同的零部件之間的結(jié)構(gòu)連接，然后提出協(xié)同拆卸層次樹的生成方法，通過一種基于兩用戶定義變量的分支定界算法計(jì)算出并行拆卸序列規(guī)劃的最小工作時(shí)間。隨后，Zhang等[2]基于模糊粗糙集，定義和推導(dǎo)了裝配約束因子、拆卸優(yōu)先因子、拆卸時(shí)間因子、拆卸工具因子和組合類型因子等5個(gè)拆卸因子，建立了并行拆卸的模糊?粗糙集映射模型，利用模糊?粗糙集映射模型生成最優(yōu)的并行拆卸序列。Smith等[3]利用模塊化設(shè)計(jì)理論將待拆卸的零件轉(zhuǎn)化為模塊，并根據(jù)遞歸規(guī)則生成可行的拆卸序列，然后利用遺傳算法尋找最優(yōu)的并行拆卸序列。Ren等[4]創(chuàng)建拆卸層次樹形圖來描述并行拆卸過程，并提出一種多目標(biāo)離散人工蜂群算法，使求得的并行拆卸序列規(guī)劃的拆卸時(shí)間最小化，利潤(rùn)最大化。

然而，以上文獻(xiàn)主要針對(duì)同步并行拆卸序列規(guī)劃，要求操作者同時(shí)開始拆卸操作，從而導(dǎo)致空閑時(shí)間多，作業(yè)效率低。因此，本文針對(duì)異步并行拆卸序列規(guī)劃問題，提出改進(jìn)遺傳算法進(jìn)行求解。

1 異步并行拆卸序列規(guī)劃

異步并行拆卸是并行拆卸方式中的一種。異步并行拆卸是指允許操作者完成當(dāng)前拆卸任務(wù)后，在不違背相關(guān)約束的情況下即時(shí)開始下一個(gè)拆卸任務(wù)，不必等待所有操作者都完成任務(wù)[5]。在并行拆卸序列規(guī)劃中，操作者開始執(zhí)行拆卸操作的時(shí)間也尤為重要，會(huì)對(duì)產(chǎn)品拆卸的完成時(shí)間以及拆卸成本產(chǎn)生不小的影響。異步并行拆卸節(jié)省了部分操作者等待其他拆卸任務(wù)完成的空閑時(shí)間，減少了完成拆卸所需要的時(shí)間以及相關(guān)成本，更具有研究?jī)r(jià)值。

1.1 優(yōu)先關(guān)系約束

優(yōu)先關(guān)系表示產(chǎn)品零部件之間的拆卸先后順序，根據(jù)邏輯關(guān)系對(duì)其進(jìn)行劃分，可以分為“與優(yōu)先”關(guān)系和“或優(yōu)先”關(guān)系?！芭c優(yōu)先”關(guān)系指只有拆除所有緊前優(yōu)先零部件，零件i才能被拆除。若同時(shí)有多個(gè)零部件對(duì)零件i具有優(yōu)先關(guān)系，拆除其中某一個(gè)零部件，零件i即可拆卸，則零件i與其緊前優(yōu)先零部件構(gòu)成“或優(yōu)先”關(guān)系[6-7]。

圖1為某產(chǎn)品的優(yōu)先關(guān)系示意圖。其中，i={1,2,···,10}表示待拆卸任務(wù)，每個(gè)拆卸任務(wù)表示要拆卸的零部件，其優(yōu)先關(guān)系由優(yōu)先級(jí)高的零件指向優(yōu)先級(jí)低的零件。在圖中，用有向點(diǎn)虛線邊連接的任務(wù)2、3與任務(wù)1、8、9、10之間構(gòu)成 “或優(yōu)先”關(guān)系。若零部件2被拆卸，零部件1、3、8、9、10均可被拆卸。其余有向?qū)嵾吔舆B的拆卸任務(wù)接觸約束關(guān)系為“與優(yōu)先”關(guān)系。

圖1 某待拆卸產(chǎn)品的優(yōu)先關(guān)系示意圖Figure 1 Schematic diagram of the priority relationship of a product to be disassembled

通常，在某一拆卸方向上的各零部件之間的優(yōu)先約束關(guān)系總是嚴(yán)格對(duì)接的，當(dāng)出現(xiàn)“或優(yōu)先”關(guān)系則說明要想拆卸某一產(chǎn)品，至少有2種不同的拆卸方式，即至少有2種不同的拆卸方向。因此，在含有“或優(yōu)先”關(guān)系的情況下，可以不用考慮產(chǎn)品的拆卸方向，在一定程度上簡(jiǎn)化了問題。

1.2 工作區(qū)域沖突約束

在異步并行拆卸序列規(guī)劃中，通常是多個(gè)操作者共同拆卸一個(gè)產(chǎn)品，由于各零部件間存在復(fù)雜的裝配關(guān)系，會(huì)存在當(dāng)某個(gè)操作者拆卸某一零件時(shí)會(huì)占用另一個(gè)操作者的拆卸工作區(qū)域，使得另一個(gè)操作者的拆卸工作無法進(jìn)行的問題。這時(shí)，2個(gè)操作者無法同時(shí)完成各自的拆卸任務(wù)，這種情況稱為2個(gè)零部件之間存在工作區(qū)域沖突關(guān)系。

為了方便表達(dá)，可以像優(yōu)先關(guān)系矩陣一樣構(gòu)造一個(gè)沖突矩陣C來描述。

2 加入路徑重連的改進(jìn)遺傳算法

2.1 編碼

由于異步并行拆卸序列規(guī)劃問題不僅涉及到每個(gè)任務(wù)之間的約束關(guān)系，與操作者也相關(guān)，因此采用雙向量列表結(jié)構(gòu)編碼更加合適，個(gè)體v由拆卸任務(wù)向量v1和 操作者向量v2組成。拆卸任務(wù)向量v1={i1,i2,···,ik}，向量中每個(gè)元素代表一個(gè)待拆卸任務(wù)，由1到K的整數(shù)表示，K為待拆卸產(chǎn)品的零部件總數(shù)。操作者向量v2={r1,r2,···,rN}，向量中每個(gè)元素代表執(zhí)行向量v1中對(duì)應(yīng)的拆卸任務(wù)的操作者，由1到N的整數(shù)表示，N為操作者數(shù)量。

在確定遺傳算法的編碼方式之后，需要根據(jù)問題特點(diǎn)生成初始化種群，以本文1.1節(jié)中提出的問題為例進(jìn)行說明。拆卸任務(wù)向量v1只與待拆卸產(chǎn)品的各零部件有關(guān)。為方便解碼，需要在種群初始化時(shí)保證向量v1的可行性，即嚴(yán)格遵循各零件之間的優(yōu)先關(guān)系約束。由優(yōu)先關(guān)系矩陣可知，當(dāng)優(yōu)先關(guān)系矩陣P中 第j列中的元素均為0時(shí)，待拆卸任務(wù)j當(dāng)前可拆卸，不受其余零件的優(yōu)先約束。將得到的可拆卸任務(wù)依次存入向量v1，不斷循環(huán)直至找出所有拆卸任務(wù)，此時(shí)可得到拆卸任務(wù)向量v1，操作者向量v2可以由操作者數(shù)量通過隨機(jī)程序獲得。初始化種群具體步驟如下。

步驟 1輸入優(yōu)先關(guān)系矩陣P，創(chuàng)建空向量v1和空集合t1。

步驟 2若矩陣P為空矩陣，則轉(zhuǎn)到Step7，否則執(zhí)行Step 3。

步驟 3找出矩陣P中 元素全為0的列，將列對(duì)應(yīng)的拆卸任務(wù)存入集合t1中。

步驟 4從集合t1中隨機(jī)選擇一個(gè)待拆卸任務(wù)放入到向量v1最左端中。

步驟 5更新矩陣P，將已拆卸任務(wù)的行與列刪除，若刪除的元素中包含“或優(yōu)先”關(guān)系，則同時(shí)對(duì)與之關(guān)聯(lián)的其他“或優(yōu)先”關(guān)系元素進(jìn)行修改。

步驟 6將集合t1中已拆卸任務(wù)刪除，返回Step 2。

步驟 7根據(jù)操作者數(shù)量隨機(jī)生成向量v2。

步驟 8輸出向量v1和 向量v2。

2.2 解碼

在本文研究的異步并行拆卸序列規(guī)劃問題中，拆卸的目標(biāo)為拆卸完成時(shí)間最小，即最小化最大拆卸完成時(shí)間，類似于JSP問題的最大完工時(shí)間。與JSP問題不同，在異步并行拆卸序列規(guī)劃問題中還要考慮“與/或優(yōu)先”關(guān)系和操作者的拆卸工作區(qū)域沖突問題。 “或優(yōu)先”關(guān)系存在不定向性，在未開始拆卸之前，多個(gè)具有“或優(yōu)先”關(guān)系的待拆卸任務(wù)具有同樣的拆卸優(yōu)先級(jí)，無法選擇哪個(gè)任務(wù)先進(jìn)行拆卸。

因此，在解碼開始之前，要將拆卸任務(wù)之間的“或優(yōu)先”關(guān)系解除。仍以1.1節(jié)中的問題為例，通過編碼，該產(chǎn)品所有拆卸任務(wù)的拆卸順序已經(jīng)出來，可以修改優(yōu)先關(guān)系矩陣P，解除拆卸任務(wù)之間的“或優(yōu)先”關(guān)系。 假設(shè)個(gè)體編碼v1={3,9,2,10,8,4,7,1,5,6}，則可以看作拆卸任務(wù)3對(duì)任務(wù)1、8、9、10具有“與優(yōu)先”關(guān)系約束，任務(wù)2不再對(duì)后續(xù)任務(wù)具有“或優(yōu)先”關(guān)系約束。對(duì)應(yīng)的，優(yōu)先關(guān)系矩陣可以修改為P21，P28，P29，P2,10為 0；P31，P38，P39，P3,10為1，其余保持不變。

解碼是根據(jù)種群個(gè)體編碼計(jì)算出每個(gè)個(gè)體對(duì)應(yīng)拆卸序列的最大完成時(shí)間。首先，創(chuàng)建存放所有待拆卸任務(wù)開始拆卸時(shí)間的矩陣 st和所有待拆卸零件結(jié)束時(shí)間的矩陣 ft 。 按照編碼v1的順序?qū)γ總€(gè)待拆卸零件進(jìn)行拆卸，將拆卸開始時(shí)間存入矩陣 st中對(duì)應(yīng)的位置，拆卸結(jié)束時(shí)間存入矩陣 ft中對(duì)應(yīng)的位置。當(dāng)遇到某一具有前序拆卸任務(wù)的拆卸任務(wù)時(shí)，比較其前序任務(wù)的結(jié)束時(shí)間，與所在并行序列的上一個(gè)任務(wù)結(jié)束時(shí)間，取較大值為該任務(wù)的開始時(shí)間。當(dāng)計(jì)算完時(shí)間后，還需要判斷當(dāng)前任務(wù)是否存在工作區(qū)域沖突，若存在，則對(duì)該個(gè)體進(jìn)行懲罰，若不存在則繼續(xù)計(jì)算下一個(gè)任務(wù)。

判斷零部件之間是否存在工作區(qū)域沖突主要有3個(gè)判斷標(biāo)準(zhǔn)：1) 兩任務(wù)之間是否還存在優(yōu)先關(guān)系；2) 兩任務(wù)中某一任務(wù)是否還有前序任務(wù)未執(zhí)行；3) 兩個(gè)任務(wù)的執(zhí)行時(shí)間是否重疊。若2個(gè)具有工作區(qū)域沖突關(guān)系的拆卸任務(wù)同時(shí)不滿足以上3個(gè)條件，則它們之間會(huì)產(chǎn)生工作區(qū)域沖突，該解為不可行解。

2.3 遺傳算子設(shè)計(jì)

遺傳算法中的選擇操作是對(duì)種群進(jìn)行選擇，從而使優(yōu)秀基因遺傳到下一代。本文采用輪盤賭選擇方法。

遺傳算法中的交叉操作是對(duì)種群中被選擇的兩個(gè)個(gè)體的編碼片段進(jìn)行部分交叉，從而產(chǎn)生兩個(gè)新個(gè)體的過程。本文對(duì)向量v1采用優(yōu)先保存交叉(precedence preservation crossover, PPX)方法[8-9](圖2)。PPX可以將父代的優(yōu)先關(guān)系傳遞給新的子代，從而保證子代的可行性；對(duì)向量v2采用單點(diǎn)交叉方法，在向量的長(zhǎng)度范圍內(nèi)隨機(jī)選擇一個(gè)交叉點(diǎn)，將兩個(gè)個(gè)體的向量v2從交叉點(diǎn)初斷開，并互換前半部分，即可獲得兩個(gè)新的子代v2。

圖2 PPX操作示意圖Figure 2 Schematic diagram of PPX operation

遺傳算法中的變異操作是以一定概率使個(gè)體中的基因發(fā)生變異以產(chǎn)生新個(gè)體的過程。若在向量v1上進(jìn)行變異操作，可能會(huì)產(chǎn)生不符合優(yōu)先關(guān)系約束的不可行解。本文選擇基于向量v2進(jìn)行一個(gè)簡(jiǎn)單突變：從向量v2中隨機(jī)選擇一個(gè)變異點(diǎn)，將其值更換為其他并行序列。

2.4 路徑重連算子設(shè)計(jì)

路徑重連通過使用在搜索過程中得到的一組不同的高質(zhì)量解對(duì)啟發(fā)式算法實(shí)現(xiàn)進(jìn)一步收斂和優(yōu)化。在每個(gè)迭代中，路徑重連應(yīng)用于全局搜索階段結(jié)束時(shí)找到的解決方案和從精英集中隨機(jī)選擇的解決方案，返回與這兩個(gè)解決方案相似但可能更好的新解決方案[10]。

2.4.1 路徑距離計(jì)算

在算法開始前，定義以下參數(shù)[11]。MoS為個(gè)體S中分配給拆卸任務(wù)o的操作者；LSM為個(gè)體S中分配給操作者的拆卸任務(wù)數(shù)；為o在操作者M(jìn)oS上的位置。若兩個(gè)個(gè)體中的拆卸任務(wù)o被分配給同一個(gè)操作者進(jìn)行拆卸，則定義兩個(gè)個(gè)體之間o的距離為

若兩個(gè)個(gè)體中的拆卸任務(wù)o被分配給不同的操作者進(jìn)行拆卸，定義兩個(gè)個(gè)體之間o的距離為

個(gè)體S1和S2之間的距離定義為

2.4.2 重連策略

在遺傳算法每次迭代完成后，選取出最優(yōu)的部分個(gè)體組成精英集，并隨機(jī)選擇出兩個(gè)個(gè)體，一個(gè)作為初始解Si，一個(gè)作為引導(dǎo)解Sg進(jìn)行路徑重連。設(shè)Sc為 當(dāng)前解決方案(Sc初 始化為Si)。

首先，構(gòu)造路徑重連過程中得到的解集N：對(duì)于Sc中 的每個(gè)拆卸任務(wù)oi依 次進(jìn)行判斷，若oi在解Sc和 解Sg中分別位于不同操作者上，將Sc中的oi移動(dòng)到Sg中的操作者上(位置不變)。比較移動(dòng)前后解Sc和Sg中oi的距離，選擇其中較短的存放入解集N中；若oi在 解Sc和 解Sg中同一操作者的不同位置上，改變解Sc中oi的位置，并將改變后的解存入解集N中。然后，刪除解集N中的不可行解，以及到Sg的路徑距離大于初始路徑距離(解Sc到Sg的距離)的解，計(jì)算剩余解的拆卸完成時(shí)間。然后，對(duì)于N中剩下的解S，按拆卸完成時(shí)間大小進(jìn)行升序排列，從中選擇拆卸完成時(shí)間最小的解作為路徑上的下一個(gè)Sc。若該解的最小完成時(shí)間優(yōu)于初始解的拆卸完成時(shí)間,則同時(shí)將其存儲(chǔ)在優(yōu)解集合Path中。重復(fù)以上步驟直到無法再得到更優(yōu)的解。最后，返回優(yōu)解集合Path中完工時(shí)間最短的解Sr。

3 實(shí)驗(yàn)分析

3.1 案例說明

在1.1節(jié)的案例中，令操作者(并行序列)的數(shù)量為2，運(yùn)行程序，結(jié)果如圖3所示。

圖3 程序運(yùn)行結(jié)果Figure 3 Results on program running

圖3中的柱形表示每個(gè)操作者進(jìn)行操作的拆卸任務(wù)，各個(gè)任務(wù)從甘特圖最左邊開始依次被操作者進(jìn)行拆卸，柱形上的數(shù)字對(duì)應(yīng)的是正在拆卸的任務(wù)的序號(hào)。

從圖3中可以發(fā)現(xiàn)，各操作者在零件拆卸過程中無空閑時(shí)間，最大化利用了資源，證明本文所述程序有效。

3.2 路徑重連性能分析

3.2.1 參數(shù)校驗(yàn)

使用田口實(shí)驗(yàn)對(duì)精英解個(gè)數(shù)、種群大小、交叉概率、變異概率等參數(shù)進(jìn)行校驗(yàn)，結(jié)果如圖4所示(信噪：望小)。信噪比是質(zhì)量影響因子的主效應(yīng)與誤差效應(yīng)的比值。一般地，信噪比值越大，其穩(wěn)健性越好。由圖4可知，最佳參數(shù)組合：精英解個(gè)數(shù)為10，種群規(guī)模為100，交叉概率為0.7，變異概率為0.2。

圖4 平均完成時(shí)間的信噪比?主效應(yīng)圖Figure 4 S/N ratio of average completion time-main effect diagram

3.2.2 路徑重連有效性

為驗(yàn)證所提路徑重連策略的性能，令多個(gè)實(shí)際拆卸案例[12-14]采用最佳參數(shù)組合進(jìn)行運(yùn)算。為了對(duì)多種路徑重連方法進(jìn)行區(qū)分，將采用精英解與精英解之間進(jìn)行路徑重連的方法稱為 G A?PR1，劣解向精英解進(jìn)行路徑重連的方法稱為 G A?PR2。 固定上述算法的CPU運(yùn)行時(shí)間t為N×N×0.01 s，每個(gè)案例的3種算法均運(yùn)行10次。表1展示了相同運(yùn)行時(shí)間下各算法的相對(duì)分析誤差(RPD)。

由表1可知，GA-PR1在最小RPD和平均RPD方面的表現(xiàn)均優(yōu)于GA和GA-PR2。此外，繪出3種算法在95%置信區(qū)間下的區(qū)間圖，如圖5所示。結(jié)合圖表可得，在相同的CPU運(yùn)行時(shí)間內(nèi)，GA-PR1運(yùn)行得到的結(jié)果更好且更加穩(wěn)定。

圖5 3種算法(GA、GA-PR2和GA-PR1)在95%置信區(qū)間下的區(qū)間圖Figure 5 Interval graphs of the three algorithms (GA, GA-PR2 and GA-PR1) under the 95% confidence interval

表1 GA、GA-PR2和GA-PR1的相對(duì)分析誤差Table 1 RPD of GA、GA-PR2 and GA-PR1

3.3 算法性能分析

為分析所提算法的綜合性能，將算法GA-PR1與參考文獻(xiàn)[6]中提出的改進(jìn)遺傳算法IGA及改進(jìn)離散蜜蜂算法MDBA[15]進(jìn)行對(duì)比實(shí)驗(yàn)。

通過田口實(shí)驗(yàn)確定各算法的最佳參數(shù)組合(表2)，對(duì)21個(gè)案例在相同的CPU運(yùn)行時(shí)間分別運(yùn)行10次，結(jié)果如表3所示。根據(jù)表3繪制出3種算法在95%置信區(qū)間下的區(qū)間圖，如圖6所示。

表2 各算法參數(shù)校驗(yàn)結(jié)果Table 2 Verification results of various algorithm parameters

表3 IGA、MDBA和GA-PR1的相對(duì)分析誤差Table 3 RPD of the IGA、MDBA and GA-PR1

圖6 3種算法(IGA、MDBA和GA-PR1)在95%置信區(qū)間下的區(qū)間圖Figure 6 Interval graphs of the three algorithms (IGA, MDBA and GAPR1) under the 95% confidence interval

從表3中可知，在平均值方面，相較于IGA，GAPR1獲得了20個(gè)較優(yōu)解；相較于 MDBA，GA-PR1獲得了18個(gè)較優(yōu)解。在最小值方面，相較于IGA，GAPR1獲得了17個(gè)較優(yōu)解；相較于 MDBA，GA-PR1獲得了15個(gè)較優(yōu)解。結(jié)合表3和圖6可得，對(duì)比IGA和MDBA，所提出的GA-PR1具有更好的綜合性能。

4 結(jié)論

本文采用加入路徑重連的遺傳算法來解決異步并行拆卸序列規(guī)劃問題，并通過Matlab編程進(jìn)行實(shí)現(xiàn)。所提出的方法具有以下特點(diǎn)。1) 在模型中采用“或優(yōu)先”關(guān)系來判斷拆卸方向，對(duì)問題進(jìn)行簡(jiǎn)化。2) 采用路徑重連策略，并通過實(shí)驗(yàn)證明其有效性。

雖然本文提出的方法已經(jīng)通過案例進(jìn)行驗(yàn)證，但在實(shí)際應(yīng)用中依然存在些許不足。在實(shí)際拆卸中，往往不僅關(guān)注拆卸完成時(shí)間，更要對(duì)拆卸成本，資源消耗，拆卸利潤(rùn)等其他因素進(jìn)行多方面權(quán)衡，尋找最佳方案，但本文所述方法僅考慮拆卸完成時(shí)間，略有不足。在以后的研究中，考慮更貼合實(shí)際的具體需求，提出更好的方法解決異步并行拆卸序列規(guī)劃問題。