資源約束下拆卸線平衡問題的建模與改進(jìn)混合蛙跳算法

蔡 寧 張則強(qiáng) 張 穎 朱立夏

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

0 引言

資源浪費(fèi)與環(huán)境污染問題已成為制約人類發(fā)展和進(jìn)步的重要因素之一。面對(duì)大量的廢舊機(jī)電產(chǎn)品，通過拆卸可將有用零部件或可修復(fù)零部件再利用，而對(duì)危害零部件進(jìn)行無害處理，進(jìn)而實(shí)現(xiàn)循環(huán)利用和綠色制造，因此，拆卸是組成產(chǎn)品閉環(huán)生命周期的重要環(huán)節(jié)[1]。由于實(shí)際拆卸線中的復(fù)雜性、零件數(shù)量和質(zhì)量的不確定性等，各工作站間普遍存在作業(yè)不均衡現(xiàn)象，這會(huì)影響生產(chǎn)效率，極大增加了拆卸線規(guī)劃設(shè)計(jì)的難度，因此，合理規(guī)劃拆卸方案是優(yōu)化再制造拆卸線平衡及提高作業(yè)效率的關(guān)鍵。

針對(duì)拆卸線所面臨的拆卸方案規(guī)劃難點(diǎn)，國內(nèi)外對(duì)拆卸線平衡問題(disassembly line balancing problem, DLBP)開展了大量的探索和研究。MCGOVERN等[2]通過理論推導(dǎo)證明了DLBP是復(fù)雜的非確定多項(xiàng)式(NP)問題，隨著問題規(guī)模的增大，其求解難度會(huì)呈指數(shù)級(jí)增大。目前DLBP模型的建立主要基于兩種不同的描述方式：零件優(yōu)先關(guān)系圖和任務(wù)優(yōu)先關(guān)系圖[3]。KOC等[4]在AND/OR關(guān)系圖的基礎(chǔ)上，提出了TAOG(transformed AND/OR graph)的描述方式，基于任務(wù)優(yōu)先關(guān)系構(gòu)建了以工作站數(shù)目最小為目標(biāo)的DLBP模型，分別采用整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃進(jìn)行求解；HEZER等[3]最先提出了平行拆卸線平衡問題，使用了兩條平行直線布局拆卸線，基于TAOG描述方式，以最小工作站數(shù)為目標(biāo)，采用最短路徑模型方法求解并與傳統(tǒng)直線型布局DLBP進(jìn)行對(duì)比，研究發(fā)現(xiàn)：采用平行直線布局有利于減少工作站數(shù)目。

上述文獻(xiàn)均是基于任務(wù)優(yōu)先關(guān)系圖，需要引入虛擬任務(wù)且優(yōu)先關(guān)系矩陣難以確定，這將增加求解難度，然而零件優(yōu)先關(guān)系圖的結(jié)構(gòu)簡(jiǎn)單且優(yōu)先關(guān)系矩陣易確定。RIGGS等[5]基于零件優(yōu)先關(guān)系圖，對(duì)壽命周期末端(end of life，EOL)產(chǎn)品的不同狀態(tài)分別賦予不同的概率，并利用聯(lián)合優(yōu)先關(guān)系圖進(jìn)行求解；ZHANG等[6]基于零件優(yōu)先關(guān)系圖，研究了多目標(biāo)模糊DLBP；REN等[7]在零件優(yōu)先關(guān)系圖的基礎(chǔ)上，構(gòu)建了利潤導(dǎo)向下的不完全拆卸線數(shù)學(xué)模型。

在DLBP的求解方法上，目前主要有數(shù)學(xué)規(guī)劃方法、啟發(fā)式方法、智能算法等[8]。AVIKAL等[9]將模糊層次分析法與PROMETHEE方法相結(jié)合來優(yōu)化拆卸任務(wù)分配。雖然啟發(fā)式方法原理簡(jiǎn)單、易操作，但求解精度不高，為提高精度可將數(shù)學(xué)規(guī)劃方法用于求解DLBP。ALTEKIN等[10]建立了以利潤為優(yōu)化目標(biāo)的混合整數(shù)規(guī)劃模型，實(shí)現(xiàn)了整個(gè)拆卸周期的利潤最大化；BENTAHA等[11]建立了機(jī)會(huì)約束二進(jìn)制規(guī)劃模型，考慮隨機(jī)的作業(yè)時(shí)間，優(yōu)化了工位開啟成本和危害零件處理成本。但數(shù)學(xué)規(guī)劃方法只能求解小規(guī)模問題，近年來，隨著問題規(guī)模的增大，求解方法集中在智能優(yōu)化算法上，如引力搜索算法[7]、免疫遺傳算法[12]、蟻群算法[13]和人工蜂群算法[14]等。智能算法具有求解速度快，能夠處理大規(guī)模問題的優(yōu)點(diǎn)，被廣泛應(yīng)用于求解DLBP。針對(duì)多目標(biāo)優(yōu)化問題，丁力平等[13]在多目標(biāo)DLBP優(yōu)化中，引入Pareto解集的思想，能夠得到多種較優(yōu)的方案；汪開普等[15]采用擁擠距離篩選Pareto解集;李六柯等[16]通過Hyper-volume指標(biāo)來評(píng)價(jià)Pareto解集的優(yōu)劣，進(jìn)一步改善了求解質(zhì)量。但上述文獻(xiàn)針對(duì)多個(gè)Pareto非劣解時(shí)，依然難以抉擇。

現(xiàn)有文獻(xiàn)在拆卸過程中考慮資源約束的情況較少，然而實(shí)際拆卸過程中，工具和機(jī)器等資源是有限的。METE等[17]基于TAOG描述，以資源總數(shù)最小化為目標(biāo)，建立單目標(biāo)資源約束的DLBP模型，利用GAMS-CPLEX軟件進(jìn)行精確求解，但忽略了多種資源共同完成一個(gè)任務(wù)的情況，且考慮目標(biāo)單一，不能全面體現(xiàn)出資源約束DLBP問題的特性。目前尚未發(fā)現(xiàn)基于零件優(yōu)先關(guān)系圖定義拆卸過程的資源約束下多目標(biāo)DLBP的研究報(bào)道。針對(duì)DLBP中考慮資源約束的不足，本文提出了資源約束拆卸線平衡問題(resource constrained disassembly line balancing problem, RCDLBP)，建立了多目標(biāo)優(yōu)化的RCDLBP模型，并設(shè)計(jì)了一種結(jié)合Pareto思想的改進(jìn)混合蛙跳算法(shuffled frog leaping algorithm，SFLA)，通過與測(cè)試算例進(jìn)行對(duì)比以驗(yàn)證有效性，并將所提算法運(yùn)用到具體拆卸實(shí)例。

1 資源約束DLBP數(shù)學(xué)模型

1.1 問題描述

參數(shù)定義見表1。RCDLBP是指在滿足資源約束、優(yōu)先關(guān)系約束等條件下，一方面，合理分配各作業(yè)任務(wù)到對(duì)應(yīng)工作站，另一方面，確定拆卸任務(wù)順序，將每個(gè)拆卸任務(wù)合理排序，使得工作站數(shù)、資源種類數(shù)最少及拆卸效率盡可能高?？梢杂盟膮?shù)集合(T,S,Z,P)表示RCDLBP。

圖1為8個(gè)零件的拆卸優(yōu)先關(guān)系圖，假設(shè)完成一項(xiàng)拆卸任務(wù)得到一個(gè)零件，實(shí)線箭頭為AND優(yōu)先關(guān)系，如任務(wù)2、5、6與任務(wù)8滿足AND關(guān)系，當(dāng)任務(wù)2、5、6全部完成拆卸后才可以執(zhí)行任務(wù)8；虛線箭頭為OR優(yōu)先關(guān)系，如任務(wù)2、3和任務(wù)6，任務(wù)2和任務(wù)3至少有一項(xiàng)任務(wù)已完成，任務(wù)6即可執(zhí)行。

在文獻(xiàn)[10, 14]的基礎(chǔ)上，采用一種新的優(yōu)先關(guān)系矩陣P=(ali)n×n，其中ali為0、1、-1三個(gè)變量值，若任務(wù)l∈PAND(i)，則ali=1，若l∈POR(i)，則ali=-1，若兩者均不滿足，則ali=0。資源相關(guān)矩陣Q=(bir)n×R，若任務(wù)i需要資源Zr，則bir=b(i,Zr)=1，否則bir=b(i,Zr)=0。假設(shè)有Z1、Z2、Z3、Z4四種資源，則圖1的優(yōu)先關(guān)系矩陣P、資源相關(guān)矩陣Q可分別表示為

表1 參數(shù)說明表Tab.1 Parameter description table

圖1 拆卸實(shí)例零件優(yōu)先關(guān)系圖Fig.1 Parts priority relationship diagram of disassembly example

Z1Z2Z3Z4

1.2 RCDLBP數(shù)學(xué)模型的建立

為方便數(shù)學(xué)模型的建立，對(duì)RCDLBP進(jìn)行如下假設(shè)[15]：①廢舊拆卸產(chǎn)品屬于完全拆卸，零件不存在缺損等情況；②忽略零件或組件在工作站之間的移動(dòng)時(shí)間；③拆卸線為直線型布局且為單品種拆卸；④拆卸產(chǎn)品的供給量是無限的；⑤拆卸線處于正常不中斷狀態(tài)?；谏鲜瞿Ｐ图僭O(shè)和參數(shù)定義來建立多目標(biāo)RCDLBP模型。

各決策變量的表達(dá)式如下：

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

minGF=(f1，f2，f3)

(1)

(2)

(3)

(4)

約束條件：

(5)

(6)

(7)

‖Nkr‖≠0 ?r,k

(8)

(9)

(10)

Sk+1≤Skk=1，2，…，M-1

(11)

(12)

式(1)為優(yōu)化的三個(gè)目標(biāo)；式(2)為最小化工作站數(shù)；式(3)為最小化危害指數(shù)；式(4) 為最小化資源總數(shù)，盡可能將需要相同資源的任務(wù)分配在同一個(gè)工作站中。約束條件中，式(5)和式(6)為優(yōu)先關(guān)系約束，其中式(5)為AND優(yōu)先關(guān)系約束，式(6)為OR優(yōu)先關(guān)系約束；式(7)表示若存在一個(gè)需要資源Zr的任務(wù)在工作站k中完成，則Mkr=1；式(8)為工作站數(shù)約束，以確定其上下限；式(9)為任務(wù)分配約束；式(10)為拆卸節(jié)拍約束；式(11)確保工作站分配的編號(hào)連續(xù)；式(12)用來確定開啟的工作站有任務(wù)分配。

2 求解RCDLBP的蛙跳算法

混合蛙跳算法(SFLA)具有概念簡(jiǎn)單、計(jì)算速度快、全局尋優(yōu)能力強(qiáng)等特點(diǎn)[18]，且搜索框架靈活，已受到國內(nèi)外學(xué)者的廣泛關(guān)注，在求解車輛路徑問題、柔性車間調(diào)度問題和裝配線序列規(guī)劃問題[18-19]等組合優(yōu)化問題上均表現(xiàn)出一定的優(yōu)越性，而多目標(biāo)RCDLBP也屬于組合優(yōu)化問題，為此，本文設(shè)計(jì)了一種結(jié)合Pareto解集和最大滿意度思想的改進(jìn)SFLA，其主要流程包括種群初始化、種群分組、局部搜索和全局搜索。

2.1 產(chǎn)生初始可行解

本文采用文獻(xiàn)[10]的編碼方式，基于改進(jìn)的優(yōu)先關(guān)系矩陣P，提出了一種新的初始解產(chǎn)生方式，在滿足優(yōu)先關(guān)系條件下可保證解的隨機(jī)性，其步驟如下：

(1)從優(yōu)先關(guān)系矩陣P中選擇每列元素為-1的位置，行編號(hào)對(duì)應(yīng)的所有任務(wù)則構(gòu)成滿足OR關(guān)系任務(wù)集合V1的一個(gè)元素子集，例如由圖1得到的優(yōu)先關(guān)系矩陣P可知，第6列對(duì)應(yīng)任務(wù)為任務(wù)2、3，其他列沒有滿足OR關(guān)系的任務(wù)，則V1={(2, 3, 6)}。

(2)從優(yōu)先關(guān)系矩陣P中找出所有列之和為0對(duì)應(yīng)的任務(wù)，來構(gòu)成當(dāng)前可分配任務(wù)集合V2，若V2≠?，則在V2中隨機(jī)選擇一個(gè)任務(wù)j作為當(dāng)前的拆卸任務(wù)，否則轉(zhuǎn)至步驟(5)。

(3)判斷該任務(wù)是否屬于集合V1中的某個(gè)元素子集的元素，若不屬于則轉(zhuǎn)至步驟(4)，否則找出V1中包含任務(wù)j的元素子集C，其中任務(wù)i為C中的一個(gè)特殊元素，它與其他各元素滿足OR關(guān)系約束。若步驟(2)中選擇的任務(wù)j滿足j∈POR(i)，則令C中排除i的任意元素為l，其對(duì)應(yīng)優(yōu)先關(guān)系矩陣中的元素均滿足ali=0，并轉(zhuǎn)至步驟(4)，否則，直接轉(zhuǎn)至步驟(4)。如針對(duì)圖1對(duì)應(yīng)的優(yōu)先關(guān)系矩陣P,若j=2，則令a26=0、a36=0。

(4)通過修改優(yōu)先關(guān)系矩陣P釋放已分配任務(wù)的優(yōu)先順序約束，令P中的第j行和第j列全部置為0，然后轉(zhuǎn)至步驟(2)。

(5)結(jié)束任務(wù)分配，得到初始可行解。

2.2 種群分組方式

由于本文涉及多個(gè)目標(biāo)協(xié)同優(yōu)化，無法簡(jiǎn)單地對(duì)所求解進(jìn)行排序，但在尋優(yōu)過程中需要保存種群中每次全局搜索得到的最優(yōu)解Gbest及每次局部搜索得到的各個(gè)族群中的最優(yōu)解Pbest和最差解Pworst，因此采用一種基于最大滿意度的方法進(jìn)行排序，具體步驟如下：

(1)求出每個(gè)青蛙個(gè)體對(duì)應(yīng)于不同目標(biāo)的滿意度μ(fi(X))，其計(jì)算表達(dá)式如下：

μ(fi(X))=

(13)

式中，ci為第i個(gè)目標(biāo)通過單目標(biāo)優(yōu)化得到的較優(yōu)值；X為拆卸序列向量；fi(X)為多目標(biāo)優(yōu)化時(shí)第i個(gè)目標(biāo)值；δi為第i個(gè)目標(biāo)的伸縮值。

(2)計(jì)算出每個(gè)青蛙個(gè)體的最大滿意度λ，并按照從大到小的順序排列，其表達(dá)式如下：

λ=min(μ(f1(X))，μ(f2(X))，…，μ(fH(X)))

(14)

式中，H為目標(biāo)的個(gè)數(shù)。

(3)基于滿意度的排序選擇分組，分組方式如下：

(15)

u=1,2，…,mj=1,2，…,F/m

2.3 局部搜索策略

為了優(yōu)化搜索方向使其最終趨向于全局最優(yōu)個(gè)體，對(duì)蛙群個(gè)體執(zhí)行局部搜索，即對(duì)每個(gè)族群最差的個(gè)體進(jìn)行更新操作，更新策略滿足式：

S=rand(Pbest-Pworst)

(16)

S=rand(Gbest-Pworst)

(17)

Pnew=Pworst+SS≤Smax

(18)

式中，Gbest為蛙群中具有最大滿意度的解；Pbest、Pworst分別為每一個(gè)子族群中具有最大滿意度的解和最差滿意度的解；rand(·)為分布在[0,1]內(nèi)的隨機(jī)數(shù)；S為青蛙的跳動(dòng)步長(zhǎng)；Smax為最大步長(zhǎng)；Pnew為更新后的Pworst。

首先依據(jù)式(16)和式(18)更新最差解，若無改進(jìn)，則依據(jù)式(17)和式(18)更新最差解，若依然無改進(jìn)，則利用初始解產(chǎn)生方式隨機(jī)產(chǎn)生一個(gè)解。針對(duì)離散優(yōu)化問題，為了讓每個(gè)子族群具有一定的更新能力，通常采用調(diào)整序的思想進(jìn)行局部離散搜索，本文在基本SFLA的基礎(chǔ)上，采用文獻(xiàn)[19]中調(diào)整序的思想進(jìn)行局部搜索。

由于DLBP屬于較強(qiáng)約束關(guān)系的組合優(yōu)化問題，需要判斷每個(gè)個(gè)體局部搜索后的可行性，這會(huì)增加額外的運(yùn)行時(shí)間，因此本文在局部搜索中引入一種可滿足優(yōu)先約束關(guān)系的交叉和變異操作。隨機(jī)產(chǎn)生一個(gè)數(shù)，若rand(·)>0.5，則采用交叉操作，若rand(·)≤0.5，則采用變異操作。為了增加解的多樣性，采用一種四點(diǎn)交叉方式，產(chǎn)生4個(gè)隨機(jī)點(diǎn)將每個(gè)父代分為5段，分別為0-1、1-2、2-3、3-4、4-5片段，將父代P1的0-1、2-3、4-5片段全部復(fù)制給子代O1，父代P1剩下1-2、3-4片段的所有元素按照父代P2中相同元素出現(xiàn)的順序排列，并填充到O1的空余位置，按照同樣的原則產(chǎn)生子代O2，具體四點(diǎn)交叉過程如圖2所示。

圖2 交叉操作示意圖Fig.2 Cross operation schematic diagram

具體變異方式見圖3，產(chǎn)生2個(gè)隨機(jī)點(diǎn)，將一個(gè)子代個(gè)體O1分為3個(gè)片段，分別為0-1、1-2、2-3片段，復(fù)制子代O1的0-1、2-3片段給O1new，將中間1-2片段的順序重新排列，其步驟如下：①刪除優(yōu)先關(guān)系矩陣P中關(guān)于0-1、2-3片段所有元素的優(yōu)先關(guān)系約束，然后得到新的優(yōu)先關(guān)系矩陣P*;②在新的優(yōu)先關(guān)系矩陣P*條件下，依據(jù)產(chǎn)生初始解的過程，對(duì)1-2片段的所有元素進(jìn)行隨機(jī)重新排列，將排列好的元素插入到O1new的1-2片段對(duì)應(yīng)的位置，則構(gòu)成新的子代O1new。

圖3 變異操作示意圖Fig.3 Mutation operation schematic diagram

2.4 全局信息交換

為了收集各族群搜索的局部信息，獲得全局最優(yōu)解新的搜索方向，需進(jìn)行全局信息交換。各個(gè)族群經(jīng)過L次局部進(jìn)化搜索后，先將各族群中青蛙個(gè)體混合在一起，不斷更新種群，然后將青蛙個(gè)體按滿意度降序排序并重新劃分族群，保存當(dāng)代全局最優(yōu)解Gbest，以確保青蛙個(gè)體間的元信息得到充分的傳遞，再重復(fù)進(jìn)行局部搜索和進(jìn)化，直到達(dá)到最大迭代次數(shù)G，最后算法停止運(yùn)行。

2.5 多目標(biāo)處理方法

為協(xié)同優(yōu)化多個(gè)目標(biāo)，本文采用Pareto支配的思想，對(duì)于H個(gè)目標(biāo)最小化問題的任意兩個(gè)解Xp和Xq，若解Xq的每個(gè)子目標(biāo)函數(shù)值均不小于解Xp的每個(gè)子目標(biāo)函數(shù)值，即滿足

(19)

則稱為XpPareto支配Xq。所有Pareto最優(yōu)解對(duì)應(yīng)的目標(biāo)值構(gòu)成Pareto前沿，由于DLBP的復(fù)雜性，真實(shí)的Pareto前沿是未知的，因此本文將當(dāng)前文獻(xiàn)中所求的最好結(jié)果和改進(jìn)蛙跳算法所求結(jié)果匯總，并將Pareto篩選后的結(jié)果作為近似的Pareto前沿。

(20)

包含H個(gè)目標(biāo)的非劣解X的擁擠距離可表示為

(21)

2.6 改進(jìn)蛙跳算法的求解步驟

在求解RCDLBP問題中，改進(jìn)SFLA的流程圖見圖4，具體步驟如下：

(1)設(shè)置改進(jìn)SFLA算法參數(shù)，包括確定種群規(guī)模F、最大迭代次數(shù)G、子族群數(shù)m、局部進(jìn)化次數(shù)L、外部檔案容量Nq。

(2)依據(jù)2.2節(jié)規(guī)則產(chǎn)生規(guī)模為F的初始種群，設(shè)置外部檔案Q=?。

(3)依據(jù)2.3節(jié)規(guī)則將個(gè)體排序并分組，記錄全局最優(yōu)解Gbest和各族群局部最優(yōu)解Pbest、最差解Pworst。

(4)局部進(jìn)化迭代循環(huán)，對(duì)各個(gè)子族群執(zhí)行2.4節(jié)中改進(jìn)的局部搜索，IP為局部迭代計(jì)數(shù)參數(shù)，直到局部進(jìn)化次數(shù)達(dá)到L。

(5)將每個(gè)族群混合，進(jìn)行全局搜索并更新種群，然后進(jìn)行Pareto解集篩選，并更新外部檔案Q, 其中N1為更新種群后計(jì)算得到的非劣解個(gè)數(shù)。

(6)全局循環(huán)至最大迭代次數(shù)G時(shí)算法停止運(yùn)行，其中IG為全局迭代計(jì)數(shù)參數(shù)。

3 算例驗(yàn)證與實(shí)例應(yīng)用

基于Win10系統(tǒng)的MATLAB R2010b平臺(tái)開發(fā)蛙跳算法程序，運(yùn)行環(huán)境為Intel Corel i7-6700(3.40GHz)CPU，8.00G內(nèi)存。對(duì)具有25個(gè)任務(wù)的DLBP算例(以下簡(jiǎn)稱“P25”)進(jìn)行參數(shù)篩選和算法性能驗(yàn)證，并采用改進(jìn)SFLA求解電冰箱拆卸實(shí)例的RCDLBP模型，每個(gè)算例運(yùn)行10次，保存每次運(yùn)行結(jié)果和平均運(yùn)行時(shí)間。

圖4 改進(jìn)混合蛙跳算法流程圖Fig.4 Flow chart of improved shuffled frog-leaping algorithm

3.1 算例驗(yàn)證分析

為便于算法的參數(shù)篩選，同時(shí)為得到近似Pareto前沿以便于對(duì)比驗(yàn)證，將文獻(xiàn)[21]中的P25拆卸實(shí)例作為測(cè)試算例，引入文獻(xiàn)[21]中最小化均衡指標(biāo)F3、最小化需求指數(shù)F4，P25考慮的其他2個(gè)目標(biāo)和本文f1、f2一樣，分別用F1、F2表示，則P25的優(yōu)化目標(biāo)為minGF=(F1,F2,F3,F4)。

多目標(biāo)改進(jìn)SFLA算法的主要參數(shù)為：種群規(guī)模F、最大迭代次數(shù)G、子族群數(shù)m、局部進(jìn)化次數(shù)L和外部檔案容量Nq，為了得到較好的求解效果，從參數(shù)常用的選擇范圍中篩選最佳參數(shù)組合：種群規(guī)模F為{100,150,200,250}，最大迭代次數(shù)G為{80,90,100,110}，子族群數(shù)m為{5,10,25,50}，局部進(jìn)化次數(shù)L為{10,15,20,25}，外部檔案容量Nq為{8,10,12,14}。利用Minitab軟件進(jìn)行田口實(shí)驗(yàn)和統(tǒng)計(jì)分析，將五因子四水平的參數(shù)組合成16組實(shí)驗(yàn)，采用改進(jìn)SFLA求解P25的多目標(biāo)數(shù)學(xué)模型，每組參數(shù)運(yùn)行10次，計(jì)算出所求非劣解的最大滿意度的平均值，其結(jié)果見表2。

表2 最佳參數(shù)組合實(shí)驗(yàn)Tab.2 Optimal parameter combination experiment

由表2可知，滿意度均值越大，所求解的質(zhì)量越好。采用田口實(shí)驗(yàn)中的望大特性函數(shù)對(duì)表2中的結(jié)果進(jìn)行分析，見圖5。依據(jù)信噪比的均值越大對(duì)應(yīng)的參數(shù)越優(yōu)的準(zhǔn)則，可得到圖5最佳參數(shù)組合為：F=200，G=100，m=50，L=10，Nq=12。

圖5 效果圖Fig.5 Effect diagram

采用最佳參數(shù)組合求解P25，可得12組Pareto非劣解，其結(jié)果見表3。為綜合評(píng)價(jià)改進(jìn)SFLA算法多目標(biāo)優(yōu)化的性能，并與基本SFLA和經(jīng)典的多目標(biāo)優(yōu)化算法NSGA-Ⅱ[20]進(jìn)行對(duì)比，基本SFLA的參數(shù)設(shè)置為：Smax=5，其他參數(shù)則依據(jù)最佳參數(shù)設(shè)置。采用程序運(yùn)行時(shí)間td、非支配解比率(RP)、趨近度(CM)、空間評(píng)價(jià)指標(biāo)(SP)4個(gè)指標(biāo)對(duì)比分析基本SFLA、改進(jìn)SFLA、NSGA-Ⅱ，性能對(duì)比結(jié)果見表4，其中，td用于評(píng)價(jià)程序的運(yùn)行速度，該值越小越好；RP用于評(píng)價(jià)所求非劣解集不被其他非劣解集支配的非劣解個(gè)數(shù)所占比重，非支配解比率的值越大表示解的質(zhì)量越好；趨近度是收斂性指標(biāo)，用于反映非劣解與真實(shí)Pareto前沿的的逼近程度，趨近度指標(biāo)的值越小越好；空間評(píng)價(jià)指標(biāo)是分布性指標(biāo)，用于反映方法的分布性能，空間評(píng)價(jià)指標(biāo)的值越大越好，說明分布越均勻。

表3 改進(jìn)FSLA求解P25的結(jié)果Tab.3 The result of P25 solved by improved FSLA

通過分析表4可知，NSGA-Ⅱ分布性較好，運(yùn)行時(shí)間適中，但收斂性很差；基本SFLA分布性較好，收斂性較好，但運(yùn)行時(shí)間最長(zhǎng)；改進(jìn)SFLA雖然分布性稍差一些，但收斂性、求解質(zhì)量和運(yùn)行時(shí)間均優(yōu)于其他二種算法，因此，改進(jìn)SFLA求解多目標(biāo)DLBP的綜合性能優(yōu)于其他兩種算法，具有良好的求解優(yōu)勢(shì)。

表4 多目標(biāo)優(yōu)化的性能對(duì)比Tab.4 Performance comparison of multi-objective optimization

注：加粗的數(shù)據(jù)為最優(yōu)結(jié)果。

3.2 實(shí)際案例分析

現(xiàn)以某企業(yè)廢舊電冰箱拆卸為實(shí)例，表5所示為電冰箱的相關(guān)拆卸信息(如拆卸時(shí)間t、零件危害指數(shù)h、需求資源Z等),其中拆卸主要用到4種資源Z1～Z4，分別代表扳手、專用夾具、配送框、機(jī)器。圖6為電冰箱的拆卸任務(wù)優(yōu)先關(guān)系圖，結(jié)合企業(yè)實(shí)際生產(chǎn)計(jì)劃，設(shè)定節(jié)拍Tc=130 s。

表5 冰箱拆卸信息表Tab.5 Refrigerator disassembly information form

運(yùn)用改進(jìn)SFLA對(duì)具有25個(gè)任務(wù)的電冰箱拆卸實(shí)例進(jìn)行優(yōu)化，按照最佳參數(shù)組合設(shè)置改進(jìn)SFLA的參數(shù)，求解電冰箱的RCDLBP模型，并得到4組Pareto非劣解，其結(jié)果見表6。

為了便于決策，采用種群分組中涉及的最大滿意度方法，依據(jù)式(13)、式(14) 確定最大滿意度值。由表6可知，最大滿意度值為0.667，方案3為最佳拆卸方案，其具體任務(wù)分配情況見圖7。

圖6 電冰箱優(yōu)先關(guān)系圖Fig.6 Priority relation diagram of refrigerator

表6 電冰箱的拆卸方案Tab.6 Refrigerator disassembly program

圖7 最滿意的電冰箱拆卸任務(wù)分配Fig.7 The most satisfactory refrigerators dismantling assignment

4 結(jié)論

(1)考慮實(shí)際拆卸過程中的AND/OR關(guān)系，對(duì)優(yōu)先關(guān)系矩陣進(jìn)行修改，加入了OR關(guān)系的描述，同時(shí)增加了資源約束相關(guān)的約束條件和目標(biāo)，構(gòu)建以工作站數(shù)目、危害指數(shù)、資源總數(shù)均最小的多目標(biāo)資源約束拆卸線平衡問題(RCDLBP)模型。

(2)將Pareto的思想融入混合蛙跳算法(SFLA)中，針對(duì)多目標(biāo)優(yōu)化問題，依據(jù)最大滿意度進(jìn)行排序使種群快速分組，為改進(jìn)局部搜索策略和提高收斂速度，提出了一種新的交叉、變異操作，為維護(hù)外部檔案容量且保持解的均勻分布，采用了擁擠距離機(jī)制。

(3)在算例驗(yàn)證過程中，依據(jù)田口實(shí)驗(yàn)篩選出改進(jìn)SFLA的最佳參數(shù)組合，將具有25個(gè)任務(wù)的拆卸線平衡問題算例作為測(cè)試算例并與基本SFLA和NSGA-Ⅱ所求結(jié)果進(jìn)行對(duì)比，通過非支配解率、運(yùn)行時(shí)間、趨近度和空間評(píng)價(jià)指標(biāo)對(duì)比分析所求Pareto解集，并驗(yàn)證了改進(jìn)SFLA的優(yōu)越性。將所提出的改進(jìn)SFLA用于求解電冰箱的RCDLBP模型，得到了4組Pareto非劣解，為便于決策，采用最大滿意度法篩選出了一個(gè)最滿意的拆卸方案。