鄧明星，陳方穎，唐秋華，陳 剛

(1.武漢科技大學(xué) 汽車與交通工程學(xué)院，湖北 武漢 430081；2.武漢科技大學(xué) 機(jī)械自動化學(xué)院，湖北 武漢 430081；3.武漢東風(fēng)鴻泰汽車資源循環(huán)利用有限公司，湖北 武漢 430081)

0 引言

拆卸指將零部件從產(chǎn)品上分離的過程。根據(jù)零部件拆卸的邏輯次序，拆卸可以分為并行拆卸和串行拆卸，串行拆卸是指將零部件依次順序拆卸，且一次僅拆卸一個零部件；并行拆卸則是指多個零部件可同時被拆卸。進(jìn)一步而言，根據(jù)任務(wù)的執(zhí)行方式，并行拆卸可分為同步并行和異步并行，兩者區(qū)別在于任務(wù)開始時間，同步并行是同時開始執(zhí)行并行的拆卸操作，而異步并行是各自即時開始執(zhí)行并行的拆卸操作，節(jié)省了等待其他任務(wù)完成的時間。在對復(fù)雜產(chǎn)品進(jìn)行拆卸時，異步并行能減少整體拆卸時間，更具有實際指導(dǎo)意義。產(chǎn)品拆卸按拆卸程度可分為完全拆卸和選擇性拆卸。選擇性拆卸多用于產(chǎn)品維護(hù)，或是在報廢后具有較大再利用價值的產(chǎn)品回收。本文針對多目標(biāo)件異步并行選擇性拆卸問題，通過對其序列規(guī)劃確定需拆卸的零部件及其拆卸步驟，達(dá)到降低成本、提高效率與環(huán)境效益的目的。

目前，國內(nèi)外學(xué)者對于選擇性拆卸序列規(guī)劃問題已有豐碩的研究成果。Kara等[1]采用圖論方法枚舉所有可行序列，并選取所需選擇性拆卸序列；丁勇等[2]采用基于規(guī)則消除不可行的序列，并通過遞歸方法求解拆卸序列；Wang等[3]和Luo等[4]均構(gòu)建了多層約束矩陣，以減少選擇性拆卸規(guī)劃的搜索范圍，后者進(jìn)一步用蟻群算法求解了復(fù)雜產(chǎn)品拆卸問題；蔡凱駿等[5]在分析零部件可拆卸性的基礎(chǔ)上，通過分層圖方法定位目標(biāo)零件，去除多余拆卸步驟并將選擇性拆卸轉(zhuǎn)化為完全拆卸序列規(guī)劃。針對多目標(biāo)件問題，Smith等[6]通過規(guī)則生成多個獨立的單目標(biāo)件拆卸序列結(jié)構(gòu)圖，依據(jù)其特征點融合形成一個最小規(guī)模的多目標(biāo)件結(jié)構(gòu)模型；文獻(xiàn)[7-8]考慮了多個目標(biāo)件的情況，并通過遞歸推理得到最小零部件集合或是直接在遞歸過程中生成序列。選擇性拆卸逐漸受到重視并得到深入的研究，通過遞歸方法處理選擇性拆卸序列規(guī)劃這類問題較為常見且有效，但目前針對多目標(biāo)件問題的研究仍較少。

并行拆卸的序列規(guī)劃問題在近年來也受到了普遍關(guān)注與深入研究，很多學(xué)者就并行拆卸序列規(guī)劃問題展開了研究。Zhang等[9]構(gòu)造了并行拆卸的模糊粗糙集映射模型并尋優(yōu);田永廷等[10]和張秀芬等[11]采用遺傳算法，以拆卸單元序列和拆卸步長作為編碼的前段和后段，確定了每一步所需拆卸的零部件，以表示并行序列的初始種群個體；蔡凱駿等[12]運用蟻群算法，以多只螞蟻表示相同數(shù)目維修人員共同參與拆卸，以此研究一條并行拆卸序列。上述文獻(xiàn)在考慮并行拆卸時，通常要求在完成當(dāng)前任務(wù)時，等待同步執(zhí)行的其他所有任務(wù)完成后，才能同時執(zhí)行下一步并行任務(wù)。但在實際拆卸過程中，不違背各種約束關(guān)系的情況下可以直接進(jìn)入下一步操作。Ren等[13-14]提出協(xié)同拆卸的概念，進(jìn)一步提出了同步和異步并行拆卸的概念及區(qū)別，并用雙向量列表結(jié)構(gòu)進(jìn)行編碼與解碼求取可行序列，但需對列表依次更新，以生成可行序列，且在保證約束的前提下進(jìn)行交叉操作的過程較為復(fù)雜。

本文基于異步并行拆卸概念，提出了考慮多目標(biāo)件的異步并行選擇性拆卸序列規(guī)劃方法。針對多目標(biāo)件選擇性拆卸，確定了拆卸零部件集合；構(gòu)建了異步并行拆卸序列規(guī)劃數(shù)學(xué)模型，并基于改進(jìn)遺傳算法，以拆卸完工時間為目標(biāo)，獲取了滿足需要的近優(yōu)甚至最優(yōu)拆卸序列規(guī)劃方案。

1 拆卸信息模型構(gòu)建

1.1 拆卸基本信息表達(dá)

有向圖由有向邊和節(jié)點組成，常被用于簡潔有效地表達(dá)產(chǎn)品拆卸優(yōu)先關(guān)系。優(yōu)先關(guān)系示意圖如圖1所示，可表示為EG={V,E}，其中：V為最小拆卸單元集合，E為有向邊集合。節(jié)點i表示產(chǎn)品中的最小拆卸單元，有向邊連接各個節(jié)點，ei,i′∈E，表示零件i優(yōu)先于零件i′拆卸。拆卸優(yōu)先級較節(jié)點i高，且與之相鄰的所有節(jié)點構(gòu)成i的直接前序集合Γ。圖1中有向邊e4,9和e5,9即表示零件4和5需優(yōu)先于9拆卸；節(jié)點9的直接前序集合則為{4,5}。

其鄰接矩陣可表示為P={pi,i′}，當(dāng)ei,i′∈E時，pi,i′=1，否則pi,i′=0。以圖1為例，e4,9∈E，故p4,9=1。干涉矩陣表示為CD(D=x,y,z)={ci,i′}，則D方向上的干涉矩陣中，若零件i在沿+D方向拆卸時與i′發(fā)生干涉，即零件i′在沿-D方向拆卸時與i發(fā)生干涉，則ci,i′(ci′,i)=1，否則取0。

拆卸時間包括基本拆卸時間和輔助拆卸時間，其中前者為拆卸零部件所耗費的時間，后者本文只考慮拆卸方向改變所需的時間。拆卸方向在±x,±y,±z這6個方向上移動，則輔助時間可表達(dá)為Dir={di,i′}，其中：di,i′=0(單位：s)，表示拆卸方向不改變；di,i′=1時，表示拆卸方向轉(zhuǎn)變90°;di,i′=2時,表示拆卸方向轉(zhuǎn)變180°。

1.2 待拆零部件集合及其相關(guān)拆卸信息獲取

零部件間的優(yōu)先關(guān)系具有傳遞特性，而選擇性拆卸是針對目標(biāo)件的一種定向操作，需拆卸所有對目標(biāo)件有阻礙關(guān)系的零部件，直至目標(biāo)件被拆卸。基于優(yōu)先關(guān)系的傳遞特性，以目標(biāo)零件為起始點，回溯前序零件，以獲取阻礙目標(biāo)件拆卸的所有零部件。設(shè)O為多目標(biāo)件集合，S為待拆零部件集合，A用于緩存，具體步驟如下：

步驟1初始化，S=?,A=?，將目標(biāo)件置于集合O中。

步驟2判斷O是否為空集，如果O不為空，從集合O中選取目標(biāo)件o，置于集合S中，并從O中刪除；如果為空集，則轉(zhuǎn)步驟7。

步驟3判斷o是否可拆，如果是，則轉(zhuǎn)步驟2；否則，將其直接前序Γ置入集合A。

步驟4判斷A是否為空集，如果是，轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟5。

步驟5判斷A中元素a是否已存在集合S中，如果存在，則轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟6。

步驟6判斷A中元素a是否可拆，將其從A中刪除并置入S中,如果可拆，轉(zhuǎn)步驟4；否則，將其直接前序Γ置入A中，轉(zhuǎn)步驟5。

步驟7輸出集合S。

2 考慮多目標(biāo)件的異步并行拆卸序列規(guī)劃問題建模

2.1 問題描述

考慮多目標(biāo)件的異步并行選擇性拆卸序列規(guī)劃問題可描述如下：設(shè)待拆裝配體含有K個待拆卸單元。為高效拆卸某個或某些目標(biāo)件，以總體拆卸時間最小為目標(biāo)，并行序列總數(shù)為R，要求確定目標(biāo)函數(shù)最小的拆卸序列，且滿足約束條件：①優(yōu)先關(guān)系約束；②所有的目標(biāo)組件均被拆卸；③所有最小拆卸單元只被拆卸一次。

根據(jù)所描述問題，可給出如下假設(shè)與說明：①每個拆卸任務(wù)不可中斷；②在同一時刻只能拆卸一個零件；③拆卸過程無破壞。

2.2 考慮多目標(biāo)件的異步并行拆卸序列規(guī)劃數(shù)學(xué)模型構(gòu)建

根據(jù)上述問題描述可建立數(shù)學(xué)模型如下：

minmakespan。

(1)

(2)

(3)

(4)

(5)

(6)

?pi,i′=1,pi,i′∈P,ci,i′=1,

ci,i′∈C,?r,r′,n,n′,i,i′；

(7)

?i,i′,r,n

(8)

式(1)表示目標(biāo)函數(shù)，為最小化拆卸完工時間；式(2)保證每個拆卸任務(wù)都必須被執(zhí)行；式(3)表示對于每個并行序列的每個拆卸任務(wù)最多僅能進(jìn)行一次拆卸；式(4)保證每個并行序列必須執(zhí)行至少一次拆卸操作；式(5)保證在前一個任務(wù)執(zhí)行了以后才能執(zhí)行下一個拆卸任務(wù)；式(6)表示每個任務(wù)的拆卸開始時間和拆卸結(jié)束時間之間的關(guān)系；式(7)表示僅在兩個任務(wù)i和i′存在優(yōu)先關(guān)系并考慮干涉時，任務(wù)i的結(jié)束時間必須在i′的開始時間之前；式(8)保證并行序列下只有在前一個任務(wù)及輔助操作執(zhí)行完畢之后，才能繼續(xù)執(zhí)行下一個任務(wù)。

3 考慮多目標(biāo)件的異步并行選擇性拆卸序列規(guī)劃算法研究

啟發(fā)式算法因能高效求解大規(guī)模問題的近優(yōu)解，近年來被廣泛應(yīng)用于拆卸序列規(guī)劃研究中。本文融入路徑重連策略，采用改進(jìn)遺傳算法進(jìn)行多目標(biāo)件的異步并行選擇性拆卸序列規(guī)劃。

3.1 編碼和解碼方法

染色體采用兩段式編碼，包括并行序列的序列分配段和任務(wù)排序段，分別簡稱為v1和v2，且長度均為K，其編碼如圖2所示。v1中每個基因均由隨機(jī)生成的操作人員序號組成；v2由K個任務(wù)執(zhí)行序號隨機(jī)排列生成，生成新的v2則對任務(wù)的執(zhí)行順序進(jìn)行了重新分配，且任務(wù)的人員分配與v1中同一位置的元素是一一對應(yīng)的。

解碼需首先取v2中序號為1的任務(wù)，判斷其對應(yīng)零件是否可拆。若可拆，將任務(wù)分配給對應(yīng)v1段的并行序號，獲取被分配任務(wù)的開始與結(jié)束時間，并將該任務(wù)賦零值；否則順次對下一序號為2的任務(wù)進(jìn)行判斷。當(dāng)對v2分配到最末任務(wù)時，返回至序號最小且不為零的任務(wù)，并重復(fù)上述操作，直至所有任務(wù)均被分配。最后讀取相應(yīng)數(shù)據(jù)，將v2任務(wù)對應(yīng)于被拆卸零件，可得到所求序列。

3.2 交叉與變異

目前常見交叉算子主要包括單點交叉、兩點交叉、多點交叉和均勻交叉，依據(jù)兩段編碼的各自特點，需分別對兩段編碼執(zhí)行不同的交叉操作。在v1段主要采用單點交叉的方法，隨機(jī)選取一個交叉點，將兩個父代的基因段從交叉點斷開并交換前段，即可獲得兩個子代。在v2段依據(jù)編碼特點選擇均勻交叉方法，使每一位基因都能夠以相同的概率進(jìn)行交換。因序列長度不定，均勻交叉相對于選擇單點交叉表現(xiàn)效果更優(yōu)。具體交叉方法為：將第一個父代交叉點的基因同第二個父代交換，得到子代的一部分；尋找父代未被交換的基因，并依次放入子代空白部分，將子代剩余部分填充完整。編碼與解碼方法使得無論以怎樣的順序組成染色體，都可解碼獲取可行序列，因此上述變異過程生成的仍為由1-K組成的可行解。

如圖3所示為v1和v2兩段編碼對應(yīng)的兩種交叉操作示意圖。圖中，以A和a指代序列分配段，B及b指代任務(wù)排序段。首先在父代A1和A2上選取交叉點，以交叉點為分界線將A1與A2進(jìn)行分割，并將前段灰色基因{2,2,1}與{1,2,2}進(jìn)行交換，虛線后段白色部分不變，則可得到子代a1，a2。隨后在父代B1上隨機(jī)產(chǎn)生4個交叉點，將B2灰色交叉點的基因{9,10,8,3}置于b1相同位置，再在B1中找到除{9,10,8,3}以外的基因，將其順次放入b1白色位置上，則生成完整子代b1，生成b2方法類似。此處須知，對于所生成的b1和b2，僅需保證其為1～10的數(shù)字隨機(jī)打亂組成的序列，即可依據(jù)3.1節(jié)所提的解碼規(guī)則獲取可行的拆卸序列。

在v1段選取一個變異點，并將變異點處元素變換為其他并行序列；隨機(jī)交換v2段兩個變異點處的元素，完成變異操作。

如前所述，所提編碼與解碼方法生成初始解過程簡單且可行，生成的解具有多樣性，且對其進(jìn)行交叉變異后可直接生成可行解，具有易操作性。

3.3 適應(yīng)度函數(shù)

基于所獲取的待拆零部件集合及上述編碼規(guī)則，即可初步生成初始種群。初始種群需要通過優(yōu)勝劣汰法則選取其中精英解，在種群更新與淘汰過程中優(yōu)化整個種群，直至達(dá)到所設(shè)定的迭代次數(shù)。適應(yīng)度函數(shù)用于評判種群中個體的優(yōu)劣，從而保護(hù)較好的染色體不被淘汰。此處，以chro表示染色體編號，拆卸序列規(guī)劃中的第i項任務(wù)結(jié)束時間為fti，考慮拆卸方向更換的時間，則可將相應(yīng)適應(yīng)度函數(shù)定義為f(chro)=max{fti}。解碼后可得各個拆卸任務(wù)結(jié)束時間，并求取適應(yīng)度函數(shù)值，該數(shù)值越小，其對應(yīng)染色體的質(zhì)量越優(yōu)。

設(shè)種群規(guī)模為G，從父代種群中選擇個體進(jìn)行交叉與變異操作，產(chǎn)生與父代種群規(guī)模相同的子代。通過適應(yīng)度函數(shù)值衡量種群內(nèi)染色體優(yōu)劣，并選擇前G個高質(zhì)量染色體作為父代進(jìn)入下一輪循環(huán)。

3.4 路徑重連策略

路徑重連策略是一種通過在初始解和引導(dǎo)解之間建立路徑，獲取路徑生成過程中可能產(chǎn)生的更優(yōu)解，以加速收斂的種群強(qiáng)化策略。文獻(xiàn)[15-17]對于路徑重連均有較好的實現(xiàn)。

進(jìn)行交叉變異的操作產(chǎn)生新種群后，依據(jù)目標(biāo)函數(shù)值對解進(jìn)行排序，從排序高的解中獲取規(guī)模為F的精英池，并從精英池中任取兩個染色體作為初始解Si與引導(dǎo)解Sg。針對兩段式編碼，需對v1段和v2段分別引入元素。首先在v1段，以引導(dǎo)解中的一個元素替換v1段相同位置的元素，計算目標(biāo)值后再對v2元素進(jìn)行替換。直接替換v2元素后必然會產(chǎn)生重復(fù)元素，故以缺失元素替代重復(fù)元素。隨著對v1與v2段的元素引入，初始解與引導(dǎo)解將達(dá)到一致，則重連結(jié)束。最后，比較新生成一系列解的目標(biāo)函數(shù)值，用生成的最優(yōu)解替代初始解。

每次從精英池中選取一對解，路徑重連結(jié)束后將其從精英池中剔除，當(dāng)精英池為空時結(jié)束重連。路徑重連會有目的地將較優(yōu)解中的元素重新組合，以期在該過程中獲取更好的解來優(yōu)化種群，具有一定的導(dǎo)向性。引入路徑重連策略后，使所提方法能在較短的迭代次數(shù)內(nèi)尋獲較好的解，提高了求解效率。

本中所述方法的基本流程如圖4所示。

4 案例分析

本文以文獻(xiàn)[18]中的發(fā)動機(jī)為研究案例進(jìn)行分析對比，并結(jié)合所提出的改進(jìn)遺傳算法，于MATLAB中實現(xiàn)了考慮多目標(biāo)件的異步并行拆卸序列規(guī)劃。最大迭代次數(shù)C=50，種群規(guī)模Pop=100，交叉概率Pc=0.7，變異概率Pm=0.2。針對本文所考慮的異步并行選擇性拆卸問題，假設(shè)目標(biāo)件O={2,16,17}，R=2，用GAMS軟件求解所建數(shù)學(xué)模型，運行模型后獲得序列(19,4,16,17)和(3,1,18,2)，完工時間為273，結(jié)果表明所求得解與GAMS計算所得結(jié)果一致，從而驗證了所提方法的可行性。當(dāng)目標(biāo)件和并行度取不同值時，計算結(jié)果如表1所示。

表1 目標(biāo)件及并行度不同時所得最優(yōu)解

以目標(biāo)件為{2,26,33}，并行序列R=3為例進(jìn)行計算，運行15次，分別記錄其每次迭代所得解的平均值和最優(yōu)解的個數(shù)。如圖5所示，算法在迭代25次左右可獲取近優(yōu)或最優(yōu)解，且能較快收斂，表明了所提方法的高效性。

與文獻(xiàn)[18]結(jié)果進(jìn)行對比，在考慮異步并行拆卸后可獲取的最短完工時間為2 048 s，最終完工時間縮短到了原文獻(xiàn)的55.56%，極大地提高了拆卸的效率。由表1還可看出，R增大時完工時間有明顯下降，但當(dāng)R達(dá)到某臨界值時，拆卸完工時間收斂。因此R值并非越大越好，可依據(jù)實際需要選擇R數(shù)目。

當(dāng)目標(biāo)件為O={2,16,17}且R=2時，針對所求解繪制甘特圖進(jìn)行分析，如圖6所示。圖6中橫坐標(biāo)表示時間(單位：s)，縱坐標(biāo)為并行序列，矩形框上方數(shù)字表示待拆卸零件的序號，其中零部件之間所存在的間隙為輔助拆卸時間。圖6a中同步并行拆卸總耗費時間為405 s，而圖6b中異步并行在完成當(dāng)前拆卸后立即執(zhí)行下一可執(zhí)行任務(wù)，總耗費時間為273 s?？梢钥闯?，異步并行時間得到了有效利用，操作也更為緊湊，提高了拆卸效率。

5 結(jié)束語

目前研究主要側(cè)重于同步并行拆卸序列規(guī)劃方面，但是實際拆卸過程往往是異步并行拆卸，因此，對于異步并行拆卸的研究更具有實際參考意義與工程價值。為提高并行拆卸序列規(guī)劃效率，本文提出一種基于遺傳算法的異步并行選擇性拆卸序列規(guī)劃方法，該方法具有以下特點:

(1)采用有向圖來描述產(chǎn)品零部件之間的拆卸優(yōu)先關(guān)系，結(jié)合鄰接矩陣、干涉矩陣與前序集合等，便于在計算機(jī)中通過遞歸方法求取包含多個目標(biāo)件的待拆卸零部件集合。

(2)以所獲取的待拆零部件集合為基礎(chǔ)，總體拆卸時間最小為目標(biāo)，確定目標(biāo)函數(shù)最小的拆卸序列，并考慮異步并行拆卸序列規(guī)劃問題的特點，構(gòu)建了相應(yīng)的數(shù)學(xué)模型。

(3)針對異步并行拆卸所具有的特點，采用包含序列分配段及任務(wù)排序段兩部分的編碼方法，并融入路徑重連思想以改進(jìn)遺傳算法，最后通過案例驗證了所提方法的可行性與有效性。

后續(xù)在對拆卸序列規(guī)劃領(lǐng)域的研究中，需尋求更優(yōu)的信息模型，通過具體實驗驗證，使其具有更強(qiáng)的實踐性；針對多目標(biāo)優(yōu)化問題，文中考慮因素較少，且求解方式簡單，需完善并優(yōu)化求解方法；可考慮拆卸工具并行性及高效專用拆卸工具的使用對拆卸序列規(guī)劃問題的影響。