李 勇，王 雅 君，王 耐 東，李 焜

(大連工業(yè)大學(xué) 機(jī)械工程與自動(dòng)化學(xué)院,遼寧 大連 116034)

0 引 言

拆卸是產(chǎn)品回收的基本動(dòng)作，提取有用部件，回收有害部件，做到循環(huán)經(jīng)濟(jì)和綠色制造。拆卸線平衡問(wèn)題(disassembly line balancing problem，DLBP)成為近年的研究熱點(diǎn)。Gungor等[1]分析了DLBP問(wèn)題，指出與裝配線平衡問(wèn)題的區(qū)別；Avikal等[2]采用一種啟發(fā)式算法求解DLBP問(wèn)題，但僅適用于解決小規(guī)模問(wèn)題；Altekin等[3]采用線性規(guī)劃方法優(yōu)化DLBP，但無(wú)法解決大規(guī)模問(wèn)題；Kalayci等[4]采用遺傳算法處理DLBP問(wèn)題，但算法較早收斂于局部最優(yōu)解。文獻(xiàn)[5-6]以AND/OR圖規(guī)劃和整數(shù)規(guī)劃，以最大化利潤(rùn)來(lái)優(yōu)化拆卸線問(wèn)題；Kalayci等[7]采用模擬退火算法，局部搜索能力強(qiáng)，但耗時(shí)長(zhǎng)，獲得全局最優(yōu)解能力弱。實(shí)際的拆卸線問(wèn)題需要兼顧多個(gè)目標(biāo)，單一的優(yōu)化往往不能更好地協(xié)調(diào)拆卸線。文獻(xiàn)[8-9]在實(shí)際生產(chǎn)中解決多目標(biāo)條件下的DLBP問(wèn)題；丁力平等[10]提出了基于Pareto的蟻群算法，通過(guò)支配關(guān)系尋找最優(yōu)前沿，以拆卸線空閑時(shí)間、平滑系數(shù)、成本等為優(yōu)化目標(biāo)，但未考慮零件其他影響平衡的指標(biāo)。

針對(duì)上述研究的不足，本研究提出一種改進(jìn)的遺傳算法，在均衡空閑時(shí)間、平滑系數(shù)基礎(chǔ)上，結(jié)合零件拆卸時(shí)環(huán)境、資源，提出新優(yōu)化目標(biāo)，通過(guò)具體實(shí)例，分析并驗(yàn)證該算法對(duì)求解此類問(wèn)題的優(yōu)越性。

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

1.1 基本參數(shù)

假設(shè)每個(gè)待拆零件作為一個(gè)拆卸任務(wù)，零件數(shù)為n(也叫拆卸任務(wù)數(shù))；T={1，2，3，…，n}為所有任務(wù)的集合；N為工作站數(shù)；CT為生產(chǎn)節(jié)拍，tk為第k個(gè)工作站上分配的所有拆卸任務(wù)作業(yè)時(shí)間之和。

1.2 決策變量

拆卸線平衡優(yōu)化不僅要考慮作業(yè)任務(wù)的均衡分配，還包括環(huán)境、資源等，待拆產(chǎn)品可能包含有害物質(zhì)，如重金屬、化學(xué)毒物，在拆卸作業(yè)中應(yīng)優(yōu)先考慮。拆卸主要是回收和利用有剩余價(jià)值的零件，拆解中應(yīng)盡快拆除價(jià)值大的零件。為使待拆產(chǎn)品的分解作業(yè)時(shí)間最小化，拆卸動(dòng)作方位的變換次數(shù)也納入優(yōu)化空間，縮短拆卸作業(yè)時(shí)間。

考慮拆卸線平衡的5個(gè)目標(biāo)，并對(duì)其優(yōu)化。5個(gè)目標(biāo)包括最少工作站數(shù)F1，平衡各個(gè)工作站空閑時(shí)間F2，見(jiàn)式(1)和(2)。

minF1=k

(1)

(2)

將兩個(gè)目標(biāo)歸納合并，以式(3)和(4)同時(shí)優(yōu)化均衡閑置時(shí)間與最小化工作站數(shù)兩項(xiàng)任務(wù)。

(3)

(4)

優(yōu)先拆卸高需求部件指標(biāo)F3，優(yōu)先拆卸危害大的部件指標(biāo)F4；最少改變方向進(jìn)行拆除F5。

(5)

(6)

(7)

引入方向指標(biāo)用來(lái)評(píng)價(jià)解序列，該數(shù)值越小，即拆卸過(guò)程中方向改變量越少，則該解越優(yōu)。式(8)表示拆卸過(guò)程相對(duì)零件與工作站的各個(gè)方向。

(8)

將方向指標(biāo)用決策變量的形式進(jìn)行表述為

(9)

綜上，多目標(biāo)拆卸線平衡表示為

minF=(F3，F(xiàn)4，F(xiàn)5，F(xiàn)6)

(10)

s.t.

(11)

(12)

(13)

約束條件式(11)為設(shè)置工作站數(shù)應(yīng)不低于理論工作站數(shù)、不多于拆卸任務(wù)數(shù)，式(12)為各工作站內(nèi)拆卸時(shí)間不超過(guò)生產(chǎn)節(jié)拍，式(13)表示拆卸順序必須滿足拆卸優(yōu)先關(guān)系。

2 算法模型求解

2.1 編 碼

常用的編碼方式有二進(jìn)制0-1編碼、實(shí)數(shù)編碼、浮點(diǎn)數(shù)編碼等[11-12]。針對(duì)拆卸線作業(yè)任務(wù)的現(xiàn)實(shí)情況，使用一種基于作業(yè)順序先后的染色體編碼規(guī)則，將n個(gè)拆卸元素排列于一排，相應(yīng)對(duì)應(yīng)一個(gè)基因位，并按作業(yè)順序優(yōu)先圖將這些元素分配到各工作站中，站中工序的加權(quán)時(shí)間值不得高于預(yù)定的生產(chǎn)節(jié)拍，按工作站中工序的排序進(jìn)行編碼。利用插零[13]方法來(lái)表示當(dāng)前工作站的作業(yè)元素開始(或結(jié)束)位置，染色體中n個(gè)作業(yè)、k+1個(gè)0、n+k+1長(zhǎng)，相鄰兩個(gè)0間的作業(yè)元素為同一個(gè)工作站。

2.2 初始種群生成

初始種群的好壞對(duì)進(jìn)化過(guò)程優(yōu)劣性影響明顯，影響算法運(yùn)行效率。采用拓?fù)渑判螂S機(jī)搜索生成初始種群，確保初始種群中個(gè)體的多樣性與解的多樣性。根據(jù)作業(yè)優(yōu)先順序流程，在作業(yè)任務(wù)全集內(nèi)(種群)尋找無(wú)任務(wù)前驅(qū)的任務(wù)i，并放入新集T1中，在作業(yè)順序圖中隨即刪除任務(wù)i及與其相關(guān)的緊后順序；重復(fù)上述操作，直至任務(wù)集合為空集結(jié)束分配任務(wù)，每步選好的任務(wù)放到對(duì)應(yīng)的基因位，所得序列即為初始可行拆卸序列。

2.3 解 碼

編碼采用的是基于任務(wù)的一維數(shù)組解序列，無(wú)法由其確定個(gè)體優(yōu)劣性，需要將解序列分配到各工作站[14]，操作過(guò)程為開啟第一個(gè)工作站j=1；初始化當(dāng)前站內(nèi)時(shí)間和剩余時(shí)間；尋找解序列上的任務(wù)i，當(dāng)所分配的任務(wù)時(shí)間超過(guò)當(dāng)前剩余時(shí)間，則分配失敗，隨機(jī)開啟新工作站，初始化當(dāng)前站內(nèi)時(shí)間和剩余時(shí)間；反之，將任務(wù)i分配到當(dāng)前站中，并更新站內(nèi)時(shí)間和剩余時(shí)間，并循環(huán)直至遍歷解序列。對(duì)每個(gè)個(gè)體的編碼及工作站間插零，能確保種群中各工作站與任務(wù)分配，提高算法的可視化[15]。

2.4 適應(yīng)度

適應(yīng)度函數(shù)在GA搜索進(jìn)化中起評(píng)價(jià)個(gè)體優(yōu)劣的作用。僅利用目標(biāo)函數(shù)即可在解空間內(nèi)完成系統(tǒng)優(yōu)化，在遺傳算法空間中，按一定規(guī)則將目標(biāo)函數(shù)轉(zhuǎn)換成個(gè)體適應(yīng)度，并評(píng)價(jià)適應(yīng)度值以實(shí)現(xiàn)解空間中可行解優(yōu)劣的判斷。

2.5 遺傳算子

2.5.1 選 擇

最常用的選擇方法是輪盤賭法，采樣思路為經(jīng)選擇的個(gè)體后代遺傳的概率與適應(yīng)度值成正比，適應(yīng)度函數(shù)評(píng)價(jià)越高，進(jìn)入下一代的概率也就越大，個(gè)體進(jìn)入下一代的概率為它的適應(yīng)度值與整個(gè)種群中個(gè)體適應(yīng)度和的比例，假設(shè)種群中個(gè)體數(shù)為M，個(gè)體被選擇的概率為

2.5.2 交 叉

交叉操作是形成新個(gè)體的重要方式，從選擇完成的種群中任取的兩個(gè)染色體，采用特定規(guī)則互換部分基因，重組后形成新個(gè)體[16]。

由于傳統(tǒng)常規(guī)方法中的隨機(jī)交叉方式往往會(huì)得到大量重復(fù)且沖突的現(xiàn)象，產(chǎn)生不可行解，影響算法的運(yùn)行效率，故采用兩點(diǎn)映射交叉法，于父代染色體隨機(jī)確定兩個(gè)交叉點(diǎn)，對(duì)父代兩染色體于交叉點(diǎn)間部分基因排序并采用部分映射，保存交叉點(diǎn)兩側(cè)的基因并放到新個(gè)體中，從而產(chǎn)生兩個(gè)新的后代個(gè)體。假設(shè)隨機(jī)選取第3、5基因位為交叉點(diǎn)，父代中兩個(gè)交叉點(diǎn)前的序列{6，3，7}、{2，4，9}得以保留，兩交叉點(diǎn)間的序列{8，5，1}在父代2中的順序?yàn)閧1，5，8}，具體過(guò)程如圖1所示。

圖1 交叉示意圖Fig.1 The diagram of crossover

2.5.3 變異操作

類似于交叉操作，作業(yè)受優(yōu)先關(guān)系的約束，變異也會(huì)產(chǎn)生不可行解。采用單點(diǎn)基本位變異，在父代染色體隨機(jī)產(chǎn)生一變異點(diǎn)(圖2中的4位置)，并根據(jù)作業(yè)優(yōu)先順序，找出變異點(diǎn)的前后工序，保留前驅(qū)任務(wù)與以前的基因位置、緊后任務(wù)與以后的基因位置，隨機(jī)將變異元素4插入染色體中前驅(qū)、緊后工序間的最近基因位，再整合以上基因的3部分生成新的子代染色體。若選取的變異位置沒(méi)有可選的插入位置，則重新選取變異點(diǎn)。

圖2 變異操作示意圖Fig.2 The diagram of mutation

2.6 結(jié)束準(zhǔn)則

GA作為一種反復(fù)迭代的搜索工具，通過(guò)多次進(jìn)化循環(huán)而無(wú)限逼近最優(yōu)值，而非恰好計(jì)算出最優(yōu)解，因此須確定終止條件，確定遺傳迭代的代數(shù)。在算法的初始時(shí)，迭代次數(shù)設(shè)置要盡量小，視情況增加迭代，當(dāng)?shù)螖?shù)超過(guò)要求的最大代數(shù)時(shí)，算法停止。

2.7 算法實(shí)現(xiàn)流程

初始種群的個(gè)體雖然是可行的，但較難保證個(gè)體最優(yōu)在運(yùn)算初期產(chǎn)生，為提高這種尋優(yōu)解性能，于算法初期增大交叉、變異的概率。而在迭代后期，要想保障適應(yīng)度高的優(yōu)良基因，可降低交叉、變異概率。采用一種自適應(yīng)交叉概率Pc如式(1)，變異概率Pm如式(2)。

(1)

式中：m為迭代次數(shù)，Pcmax為最大交叉概率，Pcmin為最小交叉概率。

(2)

式中：M為最大迭代次數(shù)，Pmmax為最大變異概率，Pmmin為最小變異概率。

算法實(shí)現(xiàn)的步驟：

步驟1參數(shù)的確定：選定種群規(guī)模NP及Pc、Pm的值；

步驟2初始化種群：令t=0，滿足節(jié)拍約束和作業(yè)優(yōu)先順序的前提下產(chǎn)生初始種群P(0)，個(gè)體數(shù)為NP；

步驟3適應(yīng)度評(píng)估：計(jì)算第t代種群中每個(gè)個(gè)體的適應(yīng)度值；

步驟4選擇操作：從第t代種群中選擇NP個(gè)個(gè)體并把它們復(fù)制到t+1代中；

步驟5交叉操作；

步驟6變異操作；

步驟7最優(yōu)保存策略；

步驟8循環(huán)：令t←t+1，滿足停止條件即結(jié)束；反之，轉(zhuǎn)向步驟3。

3 實(shí)例驗(yàn)證

3.1 DLBP實(shí)例計(jì)算

一個(gè)零件數(shù)為8的計(jì)算機(jī)部件的拆卸信息如表1所示，同時(shí)，零件拆卸任務(wù)優(yōu)先關(guān)系如圖3所示，利用改進(jìn)的遺傳算法求解。參考文獻(xiàn)[17]用MATLAB R2012b在Windows7系統(tǒng)平臺(tái)實(shí)現(xiàn)上述算法程序，對(duì)上述實(shí)例求解，工作站均為最小站數(shù)4，危害指標(biāo)H均為7，需求D=211，方向指標(biāo)R=7。表2為求得的最優(yōu)解。表3為最優(yōu)拆卸系列解及平衡后的工作站。其中，拆卸任務(wù)1、5被分配到工作站1，工作站2主要負(fù)責(zé)拆卸任務(wù)3、6、2，以此類推。且最優(yōu)解較早地將高需求零件3、6、2和危害零件7進(jìn)行了拆除，允許有7個(gè)方向的改變，算法運(yùn)算時(shí)間不到1s，所得解的平衡和危害目標(biāo)與文獻(xiàn)[9]相同，需求指標(biāo)則優(yōu)于文獻(xiàn)[11]，方向指標(biāo)比文獻(xiàn)[11]多一個(gè)。因而所得解的總體性能優(yōu)于文獻(xiàn)[11]。

表1 8個(gè)零件的拆卸信息Tab.1 Disassembly information for eight components

圖3 零件拆卸任務(wù)優(yōu)先關(guān)系Fig.3 Work priority relationship of components

表2 改進(jìn)GA與標(biāo)準(zhǔn)GA優(yōu)化結(jié)果對(duì)比Tab.2 The comparison of optimization results between improved GA and standard GA

4種單目標(biāo)求得的最優(yōu)解如表2所示，并參考文獻(xiàn)[9]中的參數(shù)設(shè)計(jì)結(jié)合DLBP問(wèn)題，針對(duì)解的質(zhì)量和算法效率經(jīng)反復(fù)測(cè)試，將參數(shù)設(shè)置為NP=100，M=100，Pcmin=0.5，Pcmax=0.95，Pmmin=0.005，Pmmax=0.01，經(jīng)計(jì)算后取最優(yōu)值，并分析運(yùn)算時(shí)間，最優(yōu)序列結(jié)果見(jiàn)表3。將改進(jìn)GA與文獻(xiàn)中的標(biāo)準(zhǔn)GA進(jìn)行對(duì)比，從中得出測(cè)試結(jié)果在處理該問(wèn)題上與標(biāo)準(zhǔn)算法相比較突出，能起到平衡的作用，且運(yùn)行時(shí)間更短。

表3 DLBP最優(yōu)拆卸系列解Tab.3 Optimal disassembly series solution of DLBP

3.2 發(fā)動(dòng)機(jī)拆卸實(shí)例應(yīng)用

以文獻(xiàn)[18]中的汽車發(fā)動(dòng)機(jī)拆卸實(shí)例為研究對(duì)象，對(duì)發(fā)動(dòng)機(jī)進(jìn)行完全拆卸。原企業(yè)中未考慮拆卸危害與需求，可變性差，不能及時(shí)地適應(yīng)拆卸任務(wù)的變化，現(xiàn)利用改進(jìn)的遺傳算法對(duì)發(fā)動(dòng)機(jī)缸體拆卸線進(jìn)行改進(jìn)，相關(guān)數(shù)據(jù)如表4所示。

表4 汽車發(fā)動(dòng)機(jī)作業(yè)零件及要素Tab.4 Working parts and elements of automobile engine

將拆卸線的汽車發(fā)動(dòng)機(jī)作業(yè)順序矩陣錄入，在MATLAB2012b上進(jìn)行編程，節(jié)拍CT=120 s，算法參數(shù)為NP=50，MaxGen=150，GAP=0.9。對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，并取得了預(yù)測(cè)的結(jié)果，跳出局部最優(yōu)解取得更優(yōu)解，搜索能力明顯提高，優(yōu)化結(jié)果如圖4所示。線平衡結(jié)果如圖5所示，直線型布局優(yōu)化結(jié)果中工作站數(shù)為15，而U型線布局站數(shù)為9，所以U型布局能做到最小化工作站數(shù)，具有一定經(jīng)濟(jì)性。

圖4 優(yōu)化結(jié)果Fig.4 The result of optimization

4 結(jié) 語(yǔ)

采用一種改進(jìn)的遺傳算法求解多目標(biāo)拆卸線平衡問(wèn)題，在保證平衡的前提下，兼顧其他目標(biāo)對(duì)平衡的影響，如危害、需求、拆卸方向等指標(biāo)。采用實(shí)數(shù)編碼策略與拓?fù)渑判蚝蛣?dòng)態(tài)確定交叉、變異操作改進(jìn)求得最優(yōu)解。算例表明DLBP-GA具有解決實(shí)際問(wèn)題的可行性，能完成作業(yè)時(shí)間均衡，在此基礎(chǔ)上對(duì)多目標(biāo)優(yōu)化問(wèn)題具有很好的適應(yīng)性，可及時(shí)適應(yīng)拆卸任務(wù)的變化，為企業(yè)帶來(lái)更多的決策方案。

(a) 直線型