面向再制造的拆卸線平衡問題建模理論及求解方法綜述

張則強(qiáng) 蔡 寧 曾艷清 李六柯 鄒賓森

西南交通大學(xué)機(jī)械工程學(xué)院，成都，610031

0 引言

廢舊機(jī)電產(chǎn)品具有環(huán)境危害性和資源再生性雙重屬性，其回收再利用是實(shí)現(xiàn)可持續(xù)發(fā)展的重要出路之一，拆卸作為實(shí)現(xiàn)產(chǎn)品資源回收再制造的關(guān)鍵步驟，是組成產(chǎn)品閉環(huán)生命周期的重要環(huán)節(jié)[1]。傳統(tǒng)方式對(duì)廢舊機(jī)電產(chǎn)品的拆卸主要是依靠單人單臺(tái)人工拆解，難以實(shí)現(xiàn)規(guī)?；鹦逗吞岣咴僦圃煨?，而拆卸生產(chǎn)線作為一種大規(guī)模生產(chǎn)的組織形式，具有生產(chǎn)效率高、成本低、易實(shí)現(xiàn)規(guī)?；?、自動(dòng)化生產(chǎn)等優(yōu)點(diǎn)。為推動(dòng)再制造的產(chǎn)業(yè)化，建造高柔性、敏捷性的拆卸線是實(shí)現(xiàn)批量拆卸的重要保障。然而，由于拆卸作業(yè)的復(fù)雜性、不確定性等因素，實(shí)際拆卸線的各工位間普遍存在著作業(yè)不均衡現(xiàn)象，影響生產(chǎn)效率的提升，再加之拆卸產(chǎn)品存在質(zhì)量和數(shù)量的不確定性、失效模式的差異性，極大增加了拆卸線規(guī)劃設(shè)計(jì)的難度,因此，合理規(guī)劃拆卸方案、標(biāo)準(zhǔn)化作業(yè)流程，是提升再制造拆卸線平衡及作業(yè)效率的關(guān)鍵。

拆卸線平衡問題(disassembly line balancing problem, DLBP)一直受到學(xué)術(shù)界和工業(yè)界的廣泛重視，學(xué)者采用了不同的方法對(duì)其進(jìn)行求解，并擴(kuò)展了多種與DLBP相關(guān)的模型。本文概述了DLBP及其基本數(shù)學(xué)模型,梳理了DLBP的求解方法并細(xì)分為三大類,總結(jié)了DLBP的擴(kuò)展模型問題,最后對(duì)DLBP未來的研究內(nèi)容和方向提出合理建議。

1 DLBP描述及模型

1.1 問題描述

DLBP是指：有一拆卸任務(wù)集合，每個(gè)作業(yè)任務(wù)之間存在優(yōu)先約束關(guān)系，在滿足節(jié)拍和優(yōu)先關(guān)系等約束的前提下，確定拆卸工序順序并將任務(wù)分配給各工位，使得工位數(shù)、各工位空閑作業(yè)時(shí)間盡可能少，拆卸效率盡可能高，最后將有用零件或部件回收。在DLBP中，表或圖可用于優(yōu)先關(guān)系約束和可行拆卸路線的直觀表示，目前文獻(xiàn)中主要存在兩種關(guān)于DLBP的描述：零件優(yōu)先關(guān)系圖和任務(wù)優(yōu)先關(guān)系圖[2-3]。

零件優(yōu)先關(guān)系圖(part-based precedence diagram, PPD)表示依據(jù)優(yōu)先關(guān)系的零件排序，每個(gè)任務(wù)導(dǎo)致一個(gè)零件被移除，該任務(wù)編號(hào)對(duì)應(yīng)于移除零件的編號(hào)。產(chǎn)品拆卸可通過有向圖G={V,E,U}來描述，其中節(jié)點(diǎn)集V表示拆卸任務(wù)集，弧集E表示優(yōu)先關(guān)系集，有向圖G的邊數(shù)e=|E|；采用鄰接矩陣IP=[ali]n×n表示拆卸任務(wù)的優(yōu)先關(guān)系，其中ali為0-1變量，若任務(wù)l是任務(wù)i的緊前任務(wù)，則ali=1，否則ali=0；關(guān)聯(lián)矩陣U表示拆卸任務(wù)關(guān)聯(lián)信息集，存儲(chǔ)任務(wù)時(shí)間、成本等。

任務(wù)優(yōu)先關(guān)系圖(task-based precedence diagram，TPD)依據(jù)其緊前任務(wù)提供優(yōu)先關(guān)系約束，一個(gè)任務(wù)可能會(huì)導(dǎo)致一個(gè)或多個(gè)零件、組件的拆除，拆卸任務(wù)的編號(hào)不依賴于零件的編號(hào)，與PPD的對(duì)比見表1。AND/OR關(guān)系圖(AND/OR graph, AOG)是一種基于任務(wù)的表達(dá)方式，可描述產(chǎn)品完全拆卸的所有路徑，但由于AOG不能直接給出拆卸任務(wù)之間的優(yōu)先關(guān)系，因此，KOC等[3]在AOG的基礎(chǔ)上提出AND/OR關(guān)系轉(zhuǎn)換圖(TAOG)的描述方式，TAOG圖中節(jié)點(diǎn)代表組件或者零件，超弧線代表一個(gè)拆卸任務(wù)，并連接經(jīng)過拆卸后形成的兩個(gè)組件或零件。

表1 PPD和TPD的對(duì)比

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

在優(yōu)化目標(biāo)方面，工作站的數(shù)量最小化是最優(yōu)選的目標(biāo)，最常見的優(yōu)化目標(biāo)歸納如下[4]：①最小化工作站數(shù)目；②最小化均衡空閑時(shí)間；③最小化危害指數(shù)；④最小化需求指數(shù)；⑤最小化拆卸方向改變次數(shù)。上述5個(gè)目標(biāo)分別表示為(部分研究文獻(xiàn)中式(2)沒有平方項(xiàng))

f1=W

(1)

(2)

(3)

(4)

(5)

式中，W為開啟工作站數(shù)目；n為拆卸產(chǎn)品拆卸任務(wù)數(shù)目；CT為工作節(jié)拍，是固定值；STk為第k個(gè)工位的所有拆卸任務(wù)時(shí)間之和；pi為任務(wù)i在拆卸序列上的位置；hi為0-1變量，若第i個(gè)拆卸任務(wù)有危害屬性，則hi=1，否則hi=0；di為已知量，表示第i個(gè)拆卸任務(wù)的需求量；ri為第i個(gè)拆卸任務(wù)的操作方向，共分為±x、±y、±z6種；Ri為0-1變量，指拆卸序列上第i個(gè)位置上操作方向的變動(dòng)性。

1.3 經(jīng)典DLBP數(shù)學(xué)模型

為方便模型建立，經(jīng)典DLBP常作如下假設(shè)：①拆卸產(chǎn)品的供貨量是無限的；②拆卸產(chǎn)品為完全拆卸；③廢舊產(chǎn)品零件無缺失、改造等情況；④廢舊產(chǎn)品為單一品種拆卸且為直線形布局；⑤忽略零件或者組件在工作站之間的移動(dòng)時(shí)間；⑥拆卸處于理想狀態(tài)，忽略突發(fā)事件。

DLBP的數(shù)學(xué)模型描述如下[5-6]：

minF={f1,f2,f3,f4,f5}

(6)

(7)

(8)

(9)

(10)

其中，xik為決策變量，若任務(wù)i被分配到工作站k，則xik=1，否則xik=0；ti為已知量，表示第i個(gè)拆卸任務(wù)的操作時(shí)間；式(7)為工作站約束，確立工作站數(shù)目的上下界限；式(8)為任務(wù)分配約束，保證每個(gè)拆卸任務(wù)必須被分配，且只能被分配到一個(gè)工作站；式(9)為節(jié)拍約束，保證工作站所有任務(wù)時(shí)間之和不超過規(guī)定節(jié)拍；式(10)為優(yōu)先關(guān)系約束。除式(10)外，下式也可確立優(yōu)先關(guān)系約束：

(11)

1.4 測(cè)試算例

由于DLBP的NP屬性，求解難度較大，故研究者提出大量的求解方法。為了對(duì)這些方法的求解性能進(jìn)行有效評(píng)價(jià)，現(xiàn)將文獻(xiàn)中常見的拆卸求解實(shí)例進(jìn)行匯總，以此作為DLBP的基準(zhǔn)算例。

基于PPD的拆卸實(shí)例匯總見表2。

表2 基于PPD的拆卸實(shí)例

MCGOVERN等[16]首次提出19個(gè)不同規(guī)模的DLBP基準(zhǔn)算例，驗(yàn)證蟻群算法求解DLBP的性能。具體構(gòu)造規(guī)則滿足7個(gè)要求：①拆卸任務(wù)數(shù)滿足8≤n≤80，并且構(gòu)成等差數(shù)列，任務(wù)數(shù)首項(xiàng)為8，公差為4，末項(xiàng)為80，總共19組拆卸實(shí)例；②不考慮拆卸任務(wù)之間的優(yōu)先關(guān)系；③定義零件危害屬性，若k=n，則對(duì)應(yīng)零件hk=1，否則hk=0；④定義需求量，若k=3n/4，則對(duì)應(yīng)零件dk=1，否則dk=0；⑤所有拆卸實(shí)例的節(jié)拍均為26 s；⑥定義拆卸方向

(12)

⑦拆卸任務(wù)時(shí)間分配滿足

(13)

KOC等[3]提出基于TAOG的基準(zhǔn)算例，其產(chǎn)生方式主要由3個(gè)參數(shù)來定義：a表示每個(gè)水平的虛擬節(jié)點(diǎn)B的數(shù)量，t表示每個(gè)虛擬節(jié)點(diǎn)B的任務(wù)(正常節(jié)點(diǎn)A)的數(shù)量，N表示零件的數(shù)量。每個(gè)水平參數(shù)a、t可以不同，參數(shù)t甚至可以在同個(gè)水平中不同。P(a,t,N)可表示任何一個(gè)隨機(jī)算例，正常節(jié)點(diǎn)A的個(gè)數(shù)R(A)和虛擬節(jié)點(diǎn)B的個(gè)數(shù)R(B)的計(jì)算公式為

R(A)=a(N-2)+1

(14)

R(B)=a[t(N-3)+2]

(15)

基于TAOG的拆卸實(shí)例匯總見表3。

表3 基于TAOG的算例

2 DLBP的研究方法

設(shè)計(jì)高效的求解算法是DLBP的研究重點(diǎn)和熱點(diǎn)之一，以所求結(jié)果是否精確，可以將求解方法分為精確方法和非精確方法兩大類。精確方法主要包括整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃等；非精確方法主要包括啟發(fā)式方法[21]和元啟發(fā)式方法。

精確方法在理論上是可以求解出DLBP問題的精確解的，但因受限于DLBP的NP屬性，只能求解小規(guī)模問題，難以求解大規(guī)模問題。啟發(fā)式方法和元啟發(fā)式方法不能確定所求結(jié)果是否為精確解，但可以在合理時(shí)間內(nèi)給出近似最優(yōu)解，尤其在面對(duì)大規(guī)模多目標(biāo)問題時(shí)，元啟發(fā)式方法求解成為明智的選擇。

2.1 精確方法

在精確求解方法中整數(shù)規(guī)劃應(yīng)用較多，研究重點(diǎn)是如何建立不同的整數(shù)規(guī)劃模型，通過增加約束以減少搜索空間，運(yùn)用成熟的數(shù)學(xué)規(guī)劃軟件(GAMS/CPLEX/LINGO/GOURBI)求解。為了處理任務(wù)時(shí)間不確定性，BENTAHA等[22]建立隨機(jī)混合整數(shù)規(guī)劃，采用L-shape和Monte Carlo相結(jié)合的方法求解最小線成本。表4對(duì)精確求解方法、優(yōu)化目標(biāo)及描述方式做了匯總和歸納。

表4 常見求解DLBP的精確方法

2.2 啟發(fā)式算法

在拆卸線平衡方法中，啟發(fā)式方法有貪婪算法、H-K算法或者幾種啟發(fā)式互相結(jié)合的方法等，主要思想是構(gòu)造方法策略中的價(jià)值重要層次度。結(jié)合拆卸線本身的特點(diǎn)，通常使用位置權(quán)重法，在滿足約束的基礎(chǔ)上進(jìn)行任務(wù)分配。

單一啟發(fā)式方法求解DLBP受啟發(fā)式規(guī)則影響大，且所求結(jié)果唯一，為了進(jìn)一步提高求解質(zhì)量，常采用多種啟發(fā)式相結(jié)合的方法，分階段優(yōu)化。MCGOVERN等[31]提出貪婪算法和爬山搜索結(jié)合的兩階段優(yōu)化策略的啟發(fā)式方法，第一階段在可行解的基礎(chǔ)上，采用貪婪算法獲得一個(gè)較優(yōu)解，在考慮危害零件和需求零件的同時(shí)使工作站數(shù)目盡可能小，第二階段采用爬山搜索進(jìn)一步優(yōu)化工作站數(shù)目或均衡空閑時(shí)間。AVIKAL等[21]采用Kano模型和改進(jìn)理想點(diǎn)法(M-TOPSIS)，先通過多準(zhǔn)則決策確定任務(wù)優(yōu)先級(jí)，然后基于優(yōu)先級(jí)大小和零件優(yōu)先關(guān)系，將任務(wù)分配給每個(gè)工作站。在文獻(xiàn)[21]兩階段優(yōu)化的基礎(chǔ)上，REN等[32]提出3階段優(yōu)化DLBP，第三階段利用2-opt算法調(diào)整和改善優(yōu)化結(jié)果。

雖然目前啟發(fā)式方法已不是DLBP研究的重點(diǎn)，但啟發(fā)式方法可為元啟發(fā)式方法求解DLBP提供較好的初始種群，加快收斂速度，另外，可依據(jù)啟發(fā)式規(guī)則進(jìn)行快速解碼，得到綜合較優(yōu)的工位分配方案。

2.3 元啟發(fā)式方法

智能算法是DLBP求解方法的研究熱點(diǎn)，它可在較短時(shí)間內(nèi)求解出大規(guī)模DLBP的滿意解或較優(yōu)解。智能算法主要包含3個(gè)模塊：編碼、搜索策略、解碼。在編碼階段主要采用基于任務(wù)的單層編碼方式，這種編碼方式直接產(chǎn)生一個(gè)個(gè)體X1×n=(1,2,…,n)，元素的個(gè)數(shù)等于拆卸任務(wù)數(shù)，個(gè)體中的每個(gè)元素對(duì)應(yīng)于拆卸任務(wù)，依次拆卸則得到一種拆卸方案，如個(gè)體(1,3,2,6,5,8,7,4)表示拆卸序列為：1-3-2-6-5-8-7-4。此外，在編碼階段采用隨機(jī)鍵編碼[33]，隨機(jī)產(chǎn)生和序列相同個(gè)數(shù)的隨機(jī)數(shù)，在滿足優(yōu)先關(guān)系的基礎(chǔ)上，對(duì)應(yīng)隨機(jī)數(shù)大的任務(wù)則優(yōu)先拆卸。解碼過程是將可行解序列分配到具體工作站，具體步驟如下：

(1)輸入可行拆卸序列X、節(jié)拍CT，開啟第一個(gè)工作站W(wǎng)S=1，當(dāng)前工位剩余可分配時(shí)間為TR，令TR=CT。

(2)按照序列X的任務(wù)順序，判斷任務(wù)i的操作時(shí)間ti是否大于TR，若是，令TR=CT，并開啟新的工作站，WS←WS+1，否則令TR←TR-ti。

(3)循環(huán)步驟(2)直至序列X的任務(wù)分配完畢，輸出拆卸方案。

不同的算法搜索策略不一樣，所以不同算法求解的效果不同。遺傳算法、蟻群算法及人工蜂群算法在DLBP求解過程中運(yùn)用的比較廣泛。在遺傳算法方面，文獻(xiàn)[30]基于AOG的描述方法，構(gòu)建作業(yè)時(shí)間隨機(jī)的并行工位的DLBP的模型，考慮兩種不同的適應(yīng)度評(píng)估方法，并在交叉變異后的新解增加修復(fù)算法，采用多樣化策略，取10%的Pareto非劣解和隨機(jī)產(chǎn)生的方式更新種群；KALAYCI等[34]將遺傳算法和變鄰域搜索算法相結(jié)合來求解工序相依的DLBP模型(sequence-dependent DLBP, SDDLBP)，采用多種變異操作，產(chǎn)生不同的鄰域結(jié)構(gòu)，其效果優(yōu)于其他多種算法；李六柯等[35]提出了一種Pareto免疫遺傳算法，融合遺傳算子和免疫算子，基于拆卸方向改變對(duì)作業(yè)時(shí)間的影響，建立考慮作業(yè)調(diào)整時(shí)間的DLBP模型，將算法與仿真技術(shù)結(jié)合進(jìn)行求解。在蟻群算法方面，文獻(xiàn)[16]研究蟻群算法(ACO)求解基本的DLBP問題，并通過19個(gè)規(guī)模的隨機(jī)算例驗(yàn)證；丁力平等[5，12]將小生境技術(shù)嵌入更新操作中搜索Pareto最優(yōu)解，算法使用Pareto思想來動(dòng)態(tài)過濾獲得的非支配解集。在人工蜂群算法方面，文獻(xiàn)[36]采用啟發(fā)式方法來產(chǎn)生初始解，引入危害和需求屬性，依據(jù)任務(wù)的權(quán)重大小選擇優(yōu)先拆卸任務(wù)，采用可變步長的動(dòng)態(tài)搜索策略，通過P25驗(yàn)證算法，然后運(yùn)用于求解P52。文獻(xiàn)[37]考慮在人工蜂群算法中融入變鄰域算法思想，設(shè)計(jì)交換、插入、逆序和多次插入的多種鄰域結(jié)構(gòu)，針對(duì)多目標(biāo)SDDLBP，采用字典排序方法處理多個(gè)目標(biāo)，增加最小化總的拆卸時(shí)間目標(biāo)，分別對(duì)P10、P25、P47求解進(jìn)行算法驗(yàn)證和對(duì)比。文獻(xiàn)[15]建立考慮能耗的拆卸線平衡問題的數(shù)學(xué)模型，并將能耗目標(biāo)集成到成本和工作負(fù)荷的目標(biāo)中，采用人工蜂群算法獲得P32節(jié)能的拆卸方案。

隨著元啟發(fā)式方法的不斷出現(xiàn)，有學(xué)者研究其他智能算法求解DLBP，如變鄰域搜索算法[38]、人工魚群算法[39]、貓群算法[40]、螢火蟲算法[41]、教學(xué)優(yōu)化算法[32]等。

3 DLBP的擴(kuò)展和補(bǔ)充

建立合適的模型是DLBP的另一研究重點(diǎn)和熱點(diǎn)。在基本DLBP模型的基礎(chǔ)上，通過釋放一些約束、假設(shè)條件，或添加一些符合實(shí)際的特殊因素，構(gòu)成新的DLBP模型。目前擴(kuò)展的模型有多種，依據(jù)不同的分類標(biāo)準(zhǔn)[42]歸納，結(jié)果見表5。

表5 DLBP擴(kuò)展模型

基本DLBP是基于理想狀況建立的優(yōu)化模型，而實(shí)際拆卸過程具有高度不確定性和差異性，因此國內(nèi)外學(xué)者開始研究復(fù)雜的實(shí)際拆卸過程。針對(duì)型號(hào)、系列不一致等或損壞程度不同，目前研究主要有以下幾個(gè)方面：第一，工藝路線相近或?qū)儆谕活惍a(chǎn)品，可采用混流拆卸線；第二，可考慮作業(yè)時(shí)間的隨機(jī)性，統(tǒng)計(jì)出拆卸作業(yè)時(shí)間的均值和方差，假設(shè)作業(yè)時(shí)間服從正態(tài)分布，允許在一定范圍內(nèi)隨機(jī)波動(dòng)，也可考慮作業(yè)時(shí)間是模糊的，通過三角模糊數(shù)確立拆卸作業(yè)時(shí)間；第三，建立不完全拆卸的模型或者部分拆卸模型，只拆卸有需求和危害的零部件，其余可采用暴力拆卸，考慮由于零部件損壞，導(dǎo)致緊后工序拆卸的零部件無法拆卸的情況，通過多階段優(yōu)化求解。

3.1 隨機(jī)型DLBP

(16)

式中，μi、σi為第i個(gè)拆卸作業(yè)時(shí)間的均值和標(biāo)準(zhǔn)差；Sm為工作站m的任務(wù)集合；α為工作站滿足節(jié)拍約束的概率；Φ-1(α)為概率α的反函數(shù)值。

針對(duì)廢舊(EOL)產(chǎn)品，BENTAHA等[45-46]采用整數(shù)規(guī)劃和Monte Carlo抽樣、上下限二階錐規(guī)劃和分段線性近似精確求解。上述文獻(xiàn)均考慮作業(yè)時(shí)間服從正態(tài)分布的情況，而現(xiàn)實(shí)拆卸過程中受干擾因素很多，拆卸作業(yè)時(shí)間可能不嚴(yán)格遵守正態(tài)分布，因此需要考慮其他更加符合實(shí)際的隨機(jī)作業(yè)時(shí)間處理方法。

3.2 模糊型DLBP

(17)

式中，a1、a2、a3分別為拆卸時(shí)間下界、最有可能時(shí)間、拆卸時(shí)間上界。

文獻(xiàn)[10]針對(duì)自動(dòng)引擎拆卸實(shí)例的模糊環(huán)境，考慮模糊作業(yè)時(shí)間及拆卸零件的模糊需求，采用模糊權(quán)重優(yōu)化4個(gè)目標(biāo)函數(shù)，分別通過GAMS和MATLAB軟件求解，并使用模糊均值和分散排序技術(shù)比較所求結(jié)果優(yōu)劣。除了考慮模糊節(jié)拍和作業(yè)時(shí)間，還可考慮模糊空閑時(shí)間和模糊平衡率[11]，上述文獻(xiàn)均利用權(quán)重處理多目標(biāo)，而文獻(xiàn)[47]針對(duì)多目標(biāo)模糊DLBP，采用融入Pareto思想的人工魚群算法，并與文獻(xiàn)[11]對(duì)比，表明所提算法更加有效。

3.3 考慮工序相依的DLBP

(18)

其他約束均不變。

KALAYCI等[34,38]對(duì)SDDLBP進(jìn)行研究，以最小化工作站數(shù)目、均衡指數(shù)、危害指數(shù)和需求指數(shù)為優(yōu)化目標(biāo)，采用基于字典排序的多種智能算法對(duì)拆卸方案進(jìn)行優(yōu)化。與經(jīng)典DLBP的主要區(qū)別在于改變了實(shí)際作業(yè)時(shí)間，所有任務(wù)的總拆卸時(shí)間是變化的，故將模型進(jìn)一步擴(kuò)展，增加最短總拆卸時(shí)間的目標(biāo)[37]，以便減小工人和機(jī)器的作業(yè)負(fù)荷。SDDLBP與基本DLBP相比，改變了節(jié)拍約束的表達(dá)式，由于考慮干擾任務(wù)的時(shí)間增量，所以總的完工時(shí)間是變化的。進(jìn)一步研究，可增加工具更換時(shí)間[15]和方向改變調(diào)整時(shí)間[35]，同時(shí)考慮不完全拆卸的情況，使模型進(jìn)一步豐富。

3.4 U形布局DLBP

傳統(tǒng)拆卸線都為直線形布局，待拆卸產(chǎn)品直線排列在傳動(dòng)設(shè)備上，工人分布在設(shè)備一側(cè)。U形拆卸線是將設(shè)備按著“U”形排列，工人在設(shè)備兩側(cè)完成拆卸作業(yè)，U形布局與直線布局相比，可減少工人行走距離和工位數(shù)，提高拆卸效率，待拆卸產(chǎn)品入口和出口在同一側(cè)，可降低物流成本，更加有利于平衡工作站時(shí)間。在基本模型的基礎(chǔ)上，將任務(wù)分配約束、優(yōu)先關(guān)系約束分別修改為

(19)

(20)

?aij=1

式中，xik為0-1變量，若第i個(gè)任務(wù)分配在第k個(gè)工作站的入口側(cè)，則為1，否則為0；yik為0-1變量，若第i個(gè)任務(wù)分配在第k個(gè)工作站的出口側(cè)，則為1，否則為0。

文獻(xiàn)[48]建立U形布局的拆卸線，提出一種啟發(fā)式方法求解，最小化工作站的數(shù)量，同時(shí)處理有危害、高需求和低拆卸成本的組件或零件。在文獻(xiàn)[44]基礎(chǔ)上，谷新軍等[49]建立多目標(biāo)SMUDLB/S模型，通過基于分解和動(dòng)態(tài)鄰域搜索的混合多目標(biāo)進(jìn)化算法(HMOEA/D)求解，另外還考慮了需求零部件數(shù)量、危害屬性及方向改變次數(shù)共10個(gè)影響因素，采用標(biāo)準(zhǔn)L12正交排列產(chǎn)生多個(gè)算例來驗(yàn)證。

3.5 平行拆卸DLBP

圖1 平行布局拆卸線Fig.1 Parallel layout disassembly line

為了快速滿足拆卸零件的需求，學(xué)者提出平行布局的拆卸線平衡問題，主要包括平行多線布局和并行工位布局，分別如圖1和圖2所示。平行多線布局拆卸線可以拆卸不同的產(chǎn)品，實(shí)現(xiàn)工位共享，有效減少工位數(shù)；同時(shí)裝配線和拆卸線混合平行布局，可允許部分拆卸的有用零部件經(jīng)過處理后，直接供貨給裝配線，減少備貨時(shí)間及物料搬運(yùn)路徑。并行工位布局拆卸線雖然會(huì)導(dǎo)致額外成本的增加，但一方面可縮短節(jié)拍時(shí)間和提高拆卸效率，另一方面，提高生產(chǎn)線的柔性和可靠性，若并行工位發(fā)生故障，允許生產(chǎn)線以較低的生產(chǎn)率運(yùn)行，不會(huì)造成停產(chǎn)。

圖2 并行工位拆卸線Fig.2 Parallel workstation disassembly line

HEZRE等[2]首先提出平行拆卸線平衡問題(parallel DLBP, PDLBP)，考慮拆卸過程中兩條平行直線布局拆卸線，并和直線形布局DLBP對(duì)比，發(fā)現(xiàn)平行DLBP改善了工作站數(shù)目，為研究平行DLBP提供了研究基礎(chǔ)，但仍存在很多地方需要進(jìn)一步研究，如沒有考慮平行DLBP特有的約束和假設(shè)，另外，文中采用的最短路徑模型不能夠在合理時(shí)間求解大規(guī)模問題。文獻(xiàn)[20]將裝配線和拆卸線混合布局，采用正逆向平行生產(chǎn)線，產(chǎn)線設(shè)置相同的節(jié)拍和速度，運(yùn)用到汽車拆解上，通過蟻群算法得到較優(yōu)的拆卸方案，提高汽車的拆卸效率。因此后續(xù)研究可采用啟發(fā)式規(guī)則或元啟發(fā)式方法求解大規(guī)模問題，考慮多條平行拆卸線或者多條線平行U形布局。

AYDEMIR-KARADAG等[30]首次提出并行工位拆卸線平衡問題，文中以拆卸線平滑指數(shù)和設(shè)計(jì)成本為目標(biāo)，基于TAOG描述方式，采用改進(jìn)遺傳算法求解所提多目標(biāo)DLBP模型。文中通過一個(gè)0-1決策變量限定工作中心的并行工位最多為2個(gè)，但在實(shí)際拆卸過程中，為更好地提高拆卸效率和可靠性，可能需要的并行工位多于2個(gè)，則無法通過簡單的一個(gè)決策變量控制，為此需要進(jìn)一步考慮并行工位DLBP其他特有的約束和假設(shè)，提高并行工位的數(shù)目上限，這進(jìn)一步增加了模型的難度。

3.6 混合品種DLBP

目前，針對(duì)單類產(chǎn)品的拆卸平衡線研究較多，但為了及時(shí)響應(yīng)市場(chǎng)需求，提供所需的零部件，需研究多產(chǎn)品柔性拆卸線。將產(chǎn)品單個(gè)回收并分類，考慮工藝近似的產(chǎn)品進(jìn)行混合拆卸，如電視機(jī)類、冰箱類等，在混流拆卸過程中，目前主要求解思想是依據(jù)不同產(chǎn)品的優(yōu)先關(guān)系得到綜合優(yōu)先關(guān)系圖，進(jìn)而獲得綜合作業(yè)時(shí)間表，然后當(dāng)作一個(gè)理想化的混合產(chǎn)品來處理，混流DLBP求解難度比基本DLBP難，因?yàn)椴粌H要考慮拆卸序列和工位分配問題，還需要得到不同產(chǎn)品的具體排序過程。

文獻(xiàn)[49]提出混合整數(shù)規(guī)劃求解混流DLBP，基于TAOG表達(dá)考慮手電筒和收音機(jī)混流拆卸情況，首次利用二元模糊目標(biāo)規(guī)劃和模糊多目標(biāo)規(guī)劃方法求解混流DLBP。文獻(xiàn)[44]不僅考慮混流拆卸，同時(shí)融入U(xiǎn)形隨機(jī)拆卸線平衡問題，基于PPD的表述方式，將不同產(chǎn)品的優(yōu)先關(guān)系圖匯總得到綜合優(yōu)先關(guān)系圖，將模型進(jìn)一步擴(kuò)展。

3.7 不完全拆卸DLBP

在實(shí)際拆卸過程中，有些零部件已損壞或沒必要完整拆卸，可采用暴力拆卸方式，因此，部分零件可以直接破碎，通過自動(dòng)分揀機(jī)分離不同類型的可用顆粒，或者因回收的利潤低于拆卸成本而不必進(jìn)行拆卸作業(yè)，這大大減少了拆卸工作。由此,拆卸過程與裝配過程不同，實(shí)際拆卸過程通常是部分拆卸[14,18,23,50-51]。在拆卸時(shí)，可能需要不同數(shù)量的零件和組件，這意味著不同的拆卸深度或速率，因而在基本模型中考慮利潤的目標(biāo)函數(shù)：

(21)

對(duì)任務(wù)分配的約束修改為

(22)

式中，ci為任務(wù)i的拆卸成本；zk表示0-1變量，若第k個(gè)工作站開啟，則為1，否則為0；F為工作站開啟固定成本;S為工作站單位時(shí)間運(yùn)行成本;Ri為單位需求零件i的拆卸利潤;xi為拆卸零件i獲得的單位數(shù)量。

文獻(xiàn)[18]基于AND/OR關(guān)系圖，提出基于拆卸任務(wù)失敗的DLBP模型，考慮由于零部件損壞，導(dǎo)致緊后工序拆卸的零部件無法拆卸的情況，分兩階段優(yōu)化求解，第一階段建立預(yù)測(cè)平衡，第二階段給定拆卸失敗的任務(wù)，然后重新分配任務(wù)。文獻(xiàn)[50]針對(duì)供貨有限及部件可用性的不完全拆卸，提出兩個(gè)數(shù)學(xué)模型，第一個(gè)優(yōu)化整個(gè)拆卸節(jié)拍的利潤，第二個(gè)優(yōu)化整個(gè)拆卸計(jì)劃周期范圍的利潤，最后采用CPLEX精確求解。不完全拆卸DLBP主要思想是在滿足拆卸需求的同時(shí)將危害零件全部拆卸，以最大經(jīng)濟(jì)利潤和拆卸深度為主要優(yōu)化目標(biāo)，與基本DLBP相比，任務(wù)分配約束由式(8)改變?yōu)槭?22)。

3.8 DLBP與供應(yīng)鏈集成優(yōu)化

針對(duì)供應(yīng)鏈網(wǎng)絡(luò)模型，將物流供應(yīng)鏈與DLBP集成優(yōu)化[24-25,52-53]，不僅考慮拆卸中心和工廠之間的組件或零件流，還需要考慮顧客到回收中心的廢舊產(chǎn)品流，在整個(gè)物流網(wǎng)絡(luò)中，同時(shí)優(yōu)化DLBP和逆向供應(yīng)鏈或閉環(huán)物流網(wǎng)絡(luò)中涉及的顧客、回收中心、拆卸中心以及工廠，使拆卸工位和總物流成本最小，讓整個(gè)物流網(wǎng)絡(luò)高效運(yùn)行。

4 結(jié)論與展望

DLBP具有重要的學(xué)術(shù)研究價(jià)值和應(yīng)用價(jià)值，目前研究主要集中于算法和模型方面，提出了很多有效的求解算法，建立了多種數(shù)學(xué)模型，并開拓了DLBP的擴(kuò)展問題和應(yīng)用實(shí)例?？v觀各方面的研究現(xiàn)狀，DLBP的研究領(lǐng)域還存在下列問題值得進(jìn)一步探討和研究：

(1)在模型層面，雖然DLBP已擴(kuò)充很多模型，但為了更加注重模型的實(shí)用性和擴(kuò)展性，需重點(diǎn)研究不同布局形式和不確定條件下的多約束多目標(biāo)問題?？蓮囊韵聨讉€(gè)方面入手：①在實(shí)際拆卸過程中，會(huì)存在特定的約束，如考慮固定工位約束、相斥約束等新的約束條件；②目前優(yōu)化的目標(biāo)多涉及經(jīng)濟(jì)角度、平衡角度，可結(jié)合環(huán)境、資源等指標(biāo)，擴(kuò)充相關(guān)的目標(biāo)函數(shù)來度量，從多個(gè)維度建立多目標(biāo)優(yōu)化模型；③考慮多線的不同連接方式，如垂直連接、平行連接和DLBP混合連接方式等，縮短貨物供應(yīng)和轉(zhuǎn)運(yùn)時(shí)間；④依據(jù)不同布局形式，可深入研究雙邊、平行拆卸線的情況；⑤目前大多數(shù)DLBP是基于節(jié)拍已知的情況，可拓展深入研究節(jié)拍未知的第二類DLBP問題；⑥考慮產(chǎn)品相關(guān)拆卸信息的高度分散性和不確定性，如使用年限、損壞程度等差異性，解決復(fù)雜實(shí)際拆卸問題。

(2)在方法層面，以往針對(duì)多目標(biāo)優(yōu)化問題多采用權(quán)重、字典排序等方法，近年來，多目標(biāo)優(yōu)化中引入Pareto思想，但得到的多個(gè)非劣解依然難以抉擇，為此可采用先優(yōu)化后決策的思想，引入多準(zhǔn)則決策技術(shù)，篩選得到最滿意的唯一解；另一方面，Pareto 支配會(huì)降低高維目標(biāo)的排序效率，改進(jìn)高維DLBP的非支配解排序方法顯得格外重要，而NSGA-Ⅲ、HMOEA/D及模糊支配度具有求解高維多目標(biāo)優(yōu)化問題的優(yōu)勢(shì)，可將其運(yùn)用到DLBP中。為求解大規(guī)模DLBP，高效元啟發(fā)式算法將是一個(gè)重要研究方向，可研究新的編碼和解碼方式，例如多層編碼或多段編碼；另外還需探討高效的搜索策略，尋求多種離散化操作設(shè)計(jì)。

(3)在應(yīng)用層面，目前DLBP的研究大多局限于確定問題，相關(guān)應(yīng)用的研究領(lǐng)域有限，有必要依據(jù)具體實(shí)際特征，進(jìn)一步拓寬其對(duì)應(yīng)的應(yīng)用范圍。一方面，不斷將DLBP相關(guān)理論和算法研究發(fā)展和完善，注重涉及實(shí)際DLBP問題，運(yùn)用到機(jī)電產(chǎn)品的拆卸回收或檢修，例如汽車拆卸、軌道車輛檢修等；另一方面，將解決DLBP的算法推廣至求解其他離散優(yōu)化問題中。