張 雷,闞歡迎,田曉飛,張文勝
(1.合肥工業(yè)大學(xué)機(jī)械工程學(xué)院,安徽 合肥 230009;2.中國質(zhì)量認(rèn)證中心,北京 100000)
機(jī)械產(chǎn)品在再制造和維修回收過程需要對(duì)構(gòu)件和零件進(jìn)行拆卸,產(chǎn)品拆卸[1]是在一定規(guī)則約束下進(jìn)行的零部件分離行為。在拆卸過程中記錄零部件分離順序的序列稱為拆卸序列,而拆卸序列規(guī)劃就是在提高產(chǎn)品拆卸效率,降低拆卸成本等各項(xiàng)要求的前提下挑選出的最優(yōu)序列。在產(chǎn)品拆卸方面,主要包括串行拆卸和并行拆卸[2]。目前,串行拆卸序列規(guī)劃方法主要包括以圖論為基礎(chǔ)的緊固件圖[3]、AND/OR 圖[4]、混合圖模型[5]等方法,但隨著產(chǎn)品結(jié)構(gòu)的復(fù)雜化,激增的零件數(shù)量致使傳統(tǒng)的拆卸方法無法解決復(fù)雜產(chǎn)品拆卸序列規(guī)劃的問題,因此眾多學(xué)者選擇改進(jìn)的人工智能算法解決產(chǎn)品復(fù)雜化出現(xiàn)的組合爆炸問題,文獻(xiàn)[6]構(gòu)建了拆卸Petri網(wǎng)模型,通過混沌粒子群優(yōu)化算法解決了拆卸序列規(guī)劃;文獻(xiàn)[7]提出了可行度及自適應(yīng)算法優(yōu)化人工蜂群算法,極大提高了拆卸序列收斂的速度及求解質(zhì)量。
隨著產(chǎn)品的復(fù)雜程度的增加和企業(yè)對(duì)拆卸效率的提高,并行拆卸與串行拆卸相比,能提高拆卸效率。文獻(xiàn)[8]利用模塊設(shè)計(jì)理論對(duì)復(fù)雜產(chǎn)品進(jìn)行并行化分析,并提出五項(xiàng)原則指導(dǎo)選擇性并行拆卸規(guī)劃的求解,但該方法適用面有限,易受產(chǎn)品結(jié)構(gòu)約束。文獻(xiàn)[9]提出并行序列染色體編碼方法,并加入不可行懲罰因子實(shí)現(xiàn)并行拆卸序列的優(yōu)化,但因其拆卸模型求解效率較低,零件選取順序隨機(jī)性太強(qiáng),導(dǎo)致求解質(zhì)量一般。文獻(xiàn)[10]通過基于模糊等價(jià)關(guān)系的動(dòng)態(tài)聚類方法實(shí)現(xiàn)了拆卸作業(yè)的并行化,但聚類模塊間的連接零件集合難以求解,增加了并行規(guī)劃求解的復(fù)雜性。
綜上所述,為了解決復(fù)雜產(chǎn)品在并行拆卸序列規(guī)劃問題求解時(shí)存在求解模型過于冗雜、求解質(zhì)量較差等問題。應(yīng)用序列矩陣方法解決并行拆卸序列長度及步長難以描述的問題;根據(jù)并行拆卸特點(diǎn)提出了拆卸單元選取原則,建立了并行拆卸最少耗時(shí)優(yōu)化模型,并結(jié)合人工蜂群算法,提出了誘導(dǎo)因子算法,實(shí)現(xiàn)了并行拆卸序列規(guī)劃問題的快速、高質(zhì)量的求解。
拆卸混合圖描述了各個(gè)零件之間的約束關(guān)系,可被定義為:G={V,E,DE}。其中,V={v1,v2,…,vn}為頂點(diǎn),表示基本拆卸單元,n 為基本拆卸單元的總數(shù)。E={E1,E2,…,Eo}為無向邊,代表兩個(gè)基本拆卸單元之間存在接觸連接關(guān)系,用實(shí)線表示,o 為無向邊的條數(shù);DE={DE1,DE2,…,DEl}為有向邊,代表兩個(gè)基本拆卸單元之間存在優(yōu)先約束關(guān)系,用帶箭頭的實(shí)線表示,箭頭方向由約束零件指向被約束零件,l 為有向邊的條數(shù)。某結(jié)構(gòu)示意圖,如圖1 所示。拆卸混合,如圖 2 所示。此時(shí) n=10,o=9,l=10。
圖1 結(jié)構(gòu)示意圖Fig.1 Schematic Diagram of a Structure
圖2 拆卸混合圖Fig.2 Disassembly Hybrid Graph
根據(jù)拆解單元之間的連接關(guān)系與優(yōu)先關(guān)系,連接矩陣Gc和優(yōu)先約束矩陣Gp可由拆卸混合圖G 可以推導(dǎo)出,即:
當(dāng) i=j 時(shí),Pij=0
部件4 在拆卸之前必須優(yōu)先拆卸部件3,兩者之前存在優(yōu)先約束關(guān)系,用帶箭頭的實(shí)線表示,由3 指向4,如圖1 所示。且兩者之間又存在連接關(guān)系,用無箭頭實(shí)線表示。由此可以得出此結(jié)構(gòu)的拆卸混合圖,如圖2 所示。
并行拆卸是對(duì)拆卸任務(wù)的進(jìn)行并行化處理從而縮短拆卸序列串行長度,進(jìn)而減少拆卸時(shí)間。在保證所有拆卸單元可拆性的基礎(chǔ)上,在并行拆卸序列過程中為了縮短拆卸序列長度采用多單元同步拆卸方法。為了消除在并行拆卸序列規(guī)劃中存在的問題,研究了可變序列矩陣的建立方法和并行拆卸單元選取方法。
一般情況下,產(chǎn)品的基本拆卸單元數(shù)量是可知的,根據(jù)零件之間的約束關(guān)系,可以輕松的計(jì)算出串行拆卸序列的步長和長度,并且可以采用單一集合模型對(duì)其進(jìn)行表示。然而,在并行拆卸中不能采用單一集合模型對(duì)拆卸步長和序列長度進(jìn)行表示,主要原因有以下幾點(diǎn):(1)在產(chǎn)品拆卸的過程中受到拆卸環(huán)境和拆卸單元約束的影響;(2)拆卸步長不完全一致;(3)拆卸并行度與每個(gè)拆卸步驟的拆卸步長可能不一致。
為了解決上述問題,采用可變序列矩陣方法,來描述并行拆卸序列問題。序列X:{X1,X2…Xg}表示含有有g(shù) 個(gè)拆卸基本單元串行拆卸序列,我們可以把該串行序列看作并行度為1,步驟數(shù)為g 的并行拆卸序列。以此類推,序列P 為ir 行ic 列的矩陣,表示其包含ir*ic 個(gè)拆卸基本單元,步驟數(shù)為ir,并行度為ic 的并行拆卸序列,即P 為:
式中:P—并行拆卸過程中可變序列矩陣,并行拆卸的步驟數(shù)與矩陣最大行數(shù)數(shù)值上相同,即mmax,同樣地,拆卸并行度和矩陣最大列數(shù)相同,即Emax,因此產(chǎn)品的拆卸單元可以表示為P(ir,ic)。
在可變序列矩陣中每個(gè)元素代表一個(gè)拆卸單元,在每行中各元素為并列關(guān)系且屬于同一拆卸步驟。當(dāng)該步驟中拆卸并行度數(shù)大于拆卸單元數(shù),將同行中缺少的元素設(shè)置為0;矩陣中的一行代表一個(gè)拆卸步驟,故行數(shù)即為拆卸步驟數(shù)。
例如圖1 所示結(jié)構(gòu),若并行拆卸度為2,拆卸步驟總數(shù)為7并行拆卸順序如下:(3,5→1,4→2→7,8→9→10→6)。則可用 7*2的并行拆卸序列矩陣P 表示:
由此可見,并行拆卸序列可以通過并行拆卸序列矩陣進(jìn)行描述,同時(shí)在可變序列矩陣的逐行構(gòu)建過程中,能解決并行拆卸序列長度與拆卸步長相互影響變化的求解問題。相應(yīng)的流程如下:
首先為了便于操作,m 表示總單元數(shù),n 表示拆卸序列中第n 個(gè)元素,Vn表示第n 個(gè)元素所代表的拆卸單元,Emax表示拆卸并行度。Q 為判斷變量,Te 表示中間變量。
(1)初始化。
在拆卸開始時(shí),取步驟數(shù)k=1,單元數(shù)Ek=0,序列矩陣P(k,:)=0,n=1;
(2)可拆卸性檢驗(yàn)。
若是,則令 Ek=Ek+1,Te=Dk,序列矩陣 P(k,Te)=Vn,n=n+1;
若否,且Ek=0,則跳轉(zhuǎn)到(5);
若否,且 Ek>0,則 Te=Emax;
(3)若n=m+1,則循環(huán)結(jié)束,轉(zhuǎn)到(5);否則返回(2);
(4)若Te=Emax則刪除P(k,:)中各單元的約束和連接關(guān)系,且 k-k+1,Ek=0;
(5)輸出結(jié)果。
如果n<m+1,表明該拆卸序列無法進(jìn)行并行拆卸,此時(shí)Q 為0。n 表示不可拆性單元的序號(hào)。如果n=m+1,表明滿足并行拆卸,此時(shí)Q 為1,k 為拆卸步驟數(shù),拆卸單元記錄在P 中,為基本單元數(shù)量。Ek如圖 1 所示模型,串行拆卸序列可以表示為{3,5,1,4,2,8,7,9,10,6},通過上述算法可得圖 1 也可以進(jìn)行并行拆卸,拆卸并行度為3,且可變序列矩陣P 為:
其中拆卸步驟數(shù) kmax=7,對(duì)應(yīng)步長分別為(3,1,1,2,1,1),并行拆卸順序?yàn)椋?,3,5→4→2→7,8→9→10→6 因此,通過可變序列矩陣算法可將串行序列轉(zhuǎn)化為并行拆卸序列。
獨(dú)立存在性是并行拆卸中各拆卸單元拆卸時(shí)間顯著的特點(diǎn),在并行拆卸確定拆卸順序的同時(shí),應(yīng)滿足整體拆卸序列并行程度最大化原則,由于需要考慮多種因素致使拆卸序列的確定變得尤為復(fù)雜,大大增加了并行拆卸序列建立的困難程度。
如果在拆卸過程中拆卸并行度大于可拆卸單元數(shù)量,要滿足步驟數(shù)最小化原則進(jìn)而實(shí)現(xiàn)整個(gè)并行拆卸序列的并行程度最高。在選取拆卸單元時(shí),采用基本拆卸時(shí)間和拆卸約束能力來解可拆卸單元數(shù)量大于拆卸并行度的問題,單元拆卸約束能力即:
式中:j—優(yōu)先約束的單元個(gè)數(shù);Z(j)—單元拆卸約束能力。
在進(jìn)行并行拆卸序列規(guī)劃時(shí),拆卸單元的被約束關(guān)系應(yīng)最大程度的釋放,增加可拆卸單元數(shù)量;同時(shí)在拆卸過程中應(yīng)優(yōu)先對(duì)Z(j)值最大的單元進(jìn)行拆卸。在圖1 所示的結(jié)構(gòu)中,若拆卸并行度為 2,單元 1,3,5 都可被拆卸,對(duì)應(yīng)的拆卸約束能力 Z(j)可分別表示為 6,7,2,其中單元 3 的 Z(j)值為 7 應(yīng)優(yōu)先被拆除,這樣單元4 就可以被釋放出來,從而在第二個(gè)步驟中就可對(duì)單元4進(jìn)行拆卸,對(duì)應(yīng)的拆卸順序可表示為:(1,3→4,5),其拆卸步驟數(shù)為2;否則拆卸順序可表示為:(1,5→3→4),其拆卸步驟數(shù)為3。
時(shí)間相關(guān)性是并行拆卸的顯著特點(diǎn),拆卸單元中耗時(shí)最長的拆卸單元決定了該步驟的拆卸時(shí)間,因此在整個(gè)拆卸過程中拆卸工位閑置現(xiàn)象就會(huì)出現(xiàn)在那些遠(yuǎn)小于最大拆卸時(shí)長的單元上,違背了提高并行拆卸效率的原則。因此為了避免工位閑置現(xiàn)象,除了遵循可拆性和整體步驟數(shù)最小的原則外,還應(yīng)考慮一種特殊的情況,即當(dāng)拆卸并行度小于可拆卸單元數(shù)時(shí),應(yīng)優(yōu)先考慮Z(j)值較大的單元,并選擇與其拆卸時(shí)長相近的單元優(yōu)先進(jìn)行拆卸。
拆卸單元的可拆性是求解并行拆卸序列規(guī)劃問題的前提條件,即當(dāng)前拆卸單元沒有受到其他單元的優(yōu)先約束且只含有單一的連接關(guān)系。故記:
式中:S(i)—基本拆卸單元i 在被拆卸前需要優(yōu)先拆卸的單元個(gè)數(shù);W(i)—與基本拆卸單元i 存在連接關(guān)系的單元個(gè)數(shù)。所以基本拆卸單元的可拆卸性要同時(shí)滿足式(2)~式(3)。
與串行拆卸不同,在并行拆卸過程中如果若干個(gè)單元的同步拆卸為一個(gè)步驟,此時(shí)該步驟的拆卸時(shí)長由此步驟中耗時(shí)最長的單元決定。若在并行拆卸中第k 個(gè)步驟的拆卸時(shí)長記為tk,根據(jù)并行拆卸序列的總時(shí)長的定義,則有:
式中:T(x)—并行拆卸序列x 的拆卸總時(shí)間。因此并行拆卸序列的總時(shí)長優(yōu)化模型為:
為解決多約束組合優(yōu)化問題的求解,在2005 年土耳其學(xué)者文獻(xiàn)[11]提出人工蜂群算法(artificial bee colony,ABC),該算法操作簡單、精度高和穩(wěn)定性強(qiáng)的特點(diǎn)被充分體現(xiàn),目前也在拆卸規(guī)劃的求解中得到應(yīng)用[7,10]。為了便于對(duì)拆卸序列規(guī)劃問題進(jìn)行求解,首先通過前文算法對(duì)串行拆解序列并行化處理,然后再對(duì)人工蜂群算法進(jìn)行初始化。為了解決并行拆卸序列的快速收斂的問題,結(jié)合并行拆卸序列規(guī)劃的特點(diǎn),以前文拆卸序列單元選取的原則為基礎(chǔ),提出了一種帶誘導(dǎo)因子的蜂群算法。通常我們把第m 個(gè)拆卸步驟中此時(shí)拆卸約束能力最強(qiáng)的單元imax(j≠imax)和拆卸單元i 的拆卸時(shí)長之差的絕對(duì)值,即,稱為誘導(dǎo)因子。當(dāng)t(mimax,j)越小,則表明單元j 比其他的單元拆卸優(yōu)先級(jí)低。并行拆卸序列規(guī)劃步驟如下:
(1)初始化。隨機(jī)生成初始拆卸序列Xt(t=1,2,3,…,MP),其中MP 為初始種群數(shù)量。每個(gè)拆卸序列Xt包含m 個(gè)零件。
(2)新序列生成。Xm和Xr分別為引領(lǐng)蜂m 和r 對(duì)應(yīng)的序列(其中r≠m),在兩個(gè)序列中隨機(jī)選擇兩個(gè)元素進(jìn)行交換(其中r≠m),新的拆卸序列由此產(chǎn)生。當(dāng)Xm的適應(yīng)度高于新的拆卸序列的適應(yīng)度時(shí),則保留原值,否則Xm將被替代。同時(shí)更新相關(guān)數(shù)據(jù)。適應(yīng)度根據(jù)式(6)計(jì)算。
當(dāng)序列x 可進(jìn)行并行拆卸時(shí),P=1,此時(shí):
當(dāng)序列x 無法并行化時(shí),P=0,此時(shí)的fitx為0,其值比前者小,因此新生成的序列替代將代替舊拆卸序列。
(3)計(jì)算轉(zhuǎn)移概率。根據(jù)式(8)計(jì)算。
(4)結(jié)合誘導(dǎo)因子新序列的生成。當(dāng)序列確定以后,根據(jù)誘導(dǎo)因子算法決定拆卸序列中需要交換的元素,并更新相關(guān)數(shù)據(jù)。
(5)新序列優(yōu)良性的判斷,如果不滿足條件,則放棄原序列,轉(zhuǎn)至(1)繼續(xù)搜尋。
(6)終止條件的判定。若不滿足條件,則轉(zhuǎn)至(2)繼續(xù)進(jìn)行搜尋;若滿足條件,則結(jié)束循環(huán)。
采用MATLAB 軟件編寫并行拆卸算法,選取某型號(hào)發(fā)動(dòng)機(jī)驗(yàn)證上述算法,發(fā)動(dòng)機(jī)模型,如圖3 所示。將模型分為32 個(gè)拆卸單元,并對(duì)拆卸單元進(jìn)行編號(hào)生成拆卸單元信息表,如表1 所示。根據(jù)零件和拆卸單元之間的約束關(guān)系生成拆卸混合圖,如圖4 所示。
圖3 發(fā)動(dòng)機(jī)模型Fig.3 The Model of Engine
表1 拆卸單元信息表Tab.1 Information Table of Disassembly Unit
圖4 拆卸混合圖Fig.4 Disassembly Hybrid Graph
改進(jìn)的人工蜂群算法的參數(shù)設(shè)置如下:初始種群數(shù)量為100,迭代次數(shù)為500,單個(gè)尋優(yōu)目標(biāo)最大迭代次數(shù)為200,當(dāng)Emax為 2 時(shí),最優(yōu)并行拆卸序列為:16,20→11,18→12,15→19,6→21,22 →1,17 →24,25 →13,2 →10,5 →9,4 →23,14 →3,8 →26,32→27,31→28,29→30。最大拆卸步驟數(shù) Kmax為 17 步,最短的拆卸時(shí)間為1054s。當(dāng)拆卸并行度Dmax為3 時(shí),其最優(yōu)并行序列 為 :16,20,6 →11,18,12 →5,10,19 →13,21,22 →1,9,17 →4,24,25→2,15→14,23→3,8,26→27,32→28,29,31→30→7,最大拆卸步驟數(shù)Kmax為13 步,最短的拆卸時(shí)間為882s。通過上述分析發(fā)現(xiàn)適當(dāng)提高拆卸并行度,可獲得較為優(yōu)異的拆卸序列,提高拆卸效率。
當(dāng)選用文獻(xiàn)[11]中的算法對(duì)發(fā)動(dòng)機(jī)模型拆卸序列進(jìn)行規(guī)劃師,可以得出最優(yōu)并行拆卸序列為:1,23→16,20→11,18→12,15→14,17 →19,6 →21,22 →24,25 →13,2 →9,4 →3,8 →26,32 →27,31→28,29→30→7,最大拆卸步驟數(shù) Kmax為 17 步,最短拆卸時(shí)間為1067s。兩者對(duì)比圖,如圖5 所示。
圖5 對(duì)比圖Fig.5 Comparison Diagram
從對(duì)比圖來看,這里算法收斂迭代次數(shù)比文獻(xiàn)算法少,而且曲線的階梯轉(zhuǎn)變次數(shù)明顯大于文獻(xiàn)算法,因此所用的方法能夠更好地處理復(fù)雜模型的并行拆卸序列規(guī)劃問題。根據(jù)兩種算法的拆卸序列可以看出在1,14,17 等拆卸單元的拆卸序列規(guī)劃時(shí)存在明顯的差異,在并行拆卸序列構(gòu)建的開始階段,將單元16 和20 作為起始拆卸步驟,而文獻(xiàn)算法將單元1 和23 作為并行拆卸系列的第一步。由于提出的算法能釋放約束能力較強(qiáng)的拆卸單元,為拆卸單元的選取提供理論支持,縮短了拆卸時(shí)間,提高了拆卸效率。
(1)建立了拆卸混合圖及可拆卸單元判別公式,并明確了并行拆卸的相關(guān)定義。為了用以描述并行拆卸序列規(guī)劃問題建立了可變序列矩陣,,搭建了串行拆卸與并行拆卸之間的橋梁。
(2)闡述了并行拆卸單元選取的原則,構(gòu)建了優(yōu)化目標(biāo)函數(shù),提出一種帶誘導(dǎo)因子的人工蜂群算法,尋求最優(yōu)的拆卸序列。
(3)實(shí)例驗(yàn)證表明,通過與其他算法的對(duì)比,所提的方法能夠準(zhǔn)確、快速的得到優(yōu)異的并行拆卸序列,對(duì)企業(yè)的拆卸生產(chǎn)作業(yè)具有一定的指導(dǎo)意義。