考慮工位約束及能耗的雙邊拆卸線平衡問題建模與優(yōu)化

謝夢柯，張則強(qiáng)，蔣 晉

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

0 引言

中國制造2025[1]是我國實(shí)施制造強(qiáng)國戰(zhàn)略的第一個十年行動綱領(lǐng)，綱領(lǐng)中五大工程第四點(diǎn)——綠色制造工程明確指出國家應(yīng)大力開展資源回收利用、再制造和低能耗等技術(shù)產(chǎn)業(yè)化示范。而我國制造業(yè)及其產(chǎn)品的能耗約占全國總能耗的2/3，可見高能耗必將成為制約我國制造業(yè)發(fā)展的重要因素[2]。因此，將能耗作為主要優(yōu)化目標(biāo)，對企業(yè)節(jié)能減排和降低成本具有重要意義。此外，現(xiàn)代化企業(yè)還應(yīng)堅持可持續(xù)發(fā)展道路，加大對廢舊產(chǎn)品進(jìn)行回收利用的力度。然而，廢舊產(chǎn)品數(shù)量龐大且大多需進(jìn)行拆卸作業(yè)才能獲得可回收零部件，為提高回收效率，回收過程常采用生產(chǎn)線方式進(jìn)行。拆卸生產(chǎn)線?？紤]工作站數(shù)、均衡指標(biāo)、拆卸需求指標(biāo)及拆卸危害指標(biāo)等多方因素。自Gungor等[3]首次提出拆卸線平衡問題(Disassembly Line Balancing Problem，DLBP)以來，DLBP很快又被證明為NP-hard問題[4]。傳統(tǒng)拆卸線多以單邊和U 型為主[5]，面對受特定作業(yè)方向約束的部件，傳統(tǒng)拆卸方式會因頻繁轉(zhuǎn)換拆卸方向?qū)е虏鹦缎蕠?yán)重降低。而采用雙邊拆卸方式能有效減少拆卸方向的轉(zhuǎn)換[6]，降低生產(chǎn)成本，提高生產(chǎn)效率。

與單邊拆卸線不同，雙邊拆卸線的工作站沿傳送裝置兩側(cè)布置，每兩個平行工作站形成一個組合工作站(亦可用組合工作站包含兩個平行工位進(jìn)行描述)，組合工作站左右兩側(cè)皆可分配拆卸任務(wù)[7]。當(dāng)前雙邊拆卸研究采用傳統(tǒng)單邊或U 型拆卸線中的優(yōu)先關(guān)系約束，未考慮實(shí)際拆卸過程中拆卸方向的變換會對任務(wù)分配造成影響。如文獻(xiàn)[8]中，單一使用0，1變量表示任務(wù)間優(yōu)先關(guān)系，當(dāng)出現(xiàn)具有優(yōu)先關(guān)系約束的任務(wù)分配至同一組合工作站不同側(cè)、不同組合工作站不同側(cè)和不同組合工作站同一側(cè)3種情況時，上述優(yōu)先關(guān)系約束則不能滿足任務(wù)間的分配關(guān)系。因此，對于具有優(yōu)先關(guān)系約束的任務(wù)，本文采用建立時間軸的方式，以考慮工位的優(yōu)先關(guān)系約束代替?zhèn)鹘y(tǒng)優(yōu)先關(guān)系約束。對于分配至同一工作站內(nèi)的不同任務(wù)，現(xiàn)有雙邊研究中未明確指出其相對位置關(guān)系，如文獻(xiàn)[9]中，任務(wù)間站內(nèi)排序僅根據(jù)編碼產(chǎn)生的拆卸序列依次排布而未給出具體的線性表達(dá)。針對這一問題，本文明確給出站內(nèi)任務(wù)間相對位置約束表達(dá)式，即當(dāng)前分配任務(wù)所在工作站內(nèi)，先于該任務(wù)分配至此工作站的其他任務(wù)應(yīng)滿足其排序在當(dāng)前分配任務(wù)之前。上述兩種問題建模過程將在第1.4節(jié)數(shù)學(xué)模型中進(jìn)行詳細(xì)闡述?，F(xiàn)有DLBP研究很少考慮實(shí)際拆卸過程中的能源消耗[10]，且現(xiàn)有雙邊DLBP中還未對能耗進(jìn)行深入研究。因此，本文針對該研究方向的不足，對拆卸過程主要能耗來源進(jìn)行分析，并將能耗來源簡化為拆卸任務(wù)所需能耗、組合工作站開啟待機(jī)能耗及回收可利用產(chǎn)品所需能耗3方面。將能耗作為優(yōu)化目標(biāo)之一，以此節(jié)約拆卸能耗[11]，降低拆卸成本，有效提高拆卸效率。

已有用于拆卸線平衡問題的常見算法有:線性規(guī)劃[12]、H-K 算法[13]、變領(lǐng)域搜索[14]、強(qiáng)化學(xué)習(xí)[15]等。但上述算法均通過權(quán)重的方式將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進(jìn)行求解，其本質(zhì)依舊為求解單目標(biāo)問題，因而存在難以均衡及協(xié)同優(yōu)化多個子目標(biāo)、目標(biāo)間的量綱不同、互相干涉及權(quán)重的取值受主觀因素影響等問題。而Pareto思想[16]篩選非劣解集時，不需量化各目標(biāo)間的權(quán)重關(guān)系;在比較拆卸方案優(yōu)劣的同時，會權(quán)衡拆卸方案中各個子目標(biāo)的優(yōu)劣，當(dāng)各個子目標(biāo)皆優(yōu)化至較優(yōu)情形時，才說明該拆卸方案較優(yōu)。因而，研究學(xué)者將Pareto思想融入智能算法中提出了以下算法:混合遺傳算法[17]、改進(jìn)人工魚群算法[18]、禁忌搜索算法[19]、遺傳模擬退火[20]算法等。這類智能算法能夠權(quán)衡各個子目標(biāo)，求解出多個拆卸方案供決策者選擇。為保證計算效率，結(jié)合NSGA-II擁擠距離機(jī)制[21]對Pareto非劣解集進(jìn)行二次篩選，選擇擁擠距離較大的較優(yōu)解存入外部檔案中，以提高求解質(zhì)量。

差分進(jìn)化(Differential Evolution，DE)算法是一種隨機(jī)的啟發(fā)式搜索算法[22]，具有較強(qiáng)的魯棒性和全局尋優(yōu)能力，從數(shù)學(xué)角度看，它是一種隨機(jī)搜索算法，從工程角度看則是一種自適應(yīng)的迭代尋優(yōu)過程。除具有較好的收斂性外，DE 算法還易于理解與執(zhí)行，它只包含幾個控制參數(shù)，且在整個迭代過程中數(shù)值保持不變。因此，將DE算法引入拆卸線平衡問題研究中，并結(jié)合Pareto思想及擁擠距離機(jī)制提出一種改進(jìn)差分進(jìn)化(Improved Differential Evolution，IDE)算法。

本文首先考慮工位優(yōu)先關(guān)系約束及站內(nèi)任務(wù)間位置約束，建立以最小化工作站數(shù)、工作站空閑指標(biāo)、危害指標(biāo)及能耗指標(biāo)的多目標(biāo)DLBP 數(shù)學(xué)模型;然后將IDE算法與經(jīng)典案例和雙邊拆卸案列進(jìn)行對比，驗(yàn)證其可行性與有效性;最后通過打印機(jī)拆卸實(shí)例計算分析，進(jìn)一步將DLBP與實(shí)際相結(jié)合。

1 考慮能耗的DLBP數(shù)學(xué)模型

1.1 問題描述與假設(shè)

雙邊拆卸線沿傳送裝置左右兩側(cè)分別布置工作站，平行的兩個工作站形成一個組合工作站。解碼過程中，對于不同拆卸任務(wù)，只能分配至左側(cè)工作站記拆卸方向?yàn)長，只能分配至右側(cè)記拆卸方向?yàn)镽，任意分配拆卸方向記為E。如圖1所示，為8任務(wù)拆卸優(yōu)先關(guān)系圖，圈內(nèi)數(shù)字表示拆卸任務(wù)編號，上方對應(yīng)該任務(wù)的拆卸方向。以任務(wù)2為例，其緊前任務(wù)為1，緊后任務(wù)為6和8，拆卸方向?yàn)橛覀?cè)。相比于傳統(tǒng)單邊或U 型拆卸線，雙邊布局在位置上有所改變，解碼過程需要遵循兩側(cè)平行工位約束。分配拆卸任務(wù)時，應(yīng)避免拆卸任務(wù)皆分配至組合工作站同一側(cè)，而是將拆卸任務(wù)均勻分配至組合工作站的兩側(cè)，以此確保整個拆卸生產(chǎn)過程達(dá)到負(fù)載均衡能耗最低的效果。

綜合考慮雙邊拆卸線特點(diǎn)，作做出如下假設(shè):

(1)拆卸產(chǎn)品不斷供應(yīng)。

(2)拆卸產(chǎn)品均進(jìn)行完全拆卸。

(3)不考慮待拆卸產(chǎn)品存在缺失或破損的情況。

(4)組合工作站左右兩側(cè)拆卸作業(yè)互不影響。

(5)工作站之間拆卸作業(yè)互不影響。

(6)所有拆卸任務(wù)皆有拆卸方向，對應(yīng)于L，R，E。

(7)組合工作站成對開啟。

(8)拆卸過程不受兩側(cè)工作站的位置干涉影響。

1.2 符號說明

i，j，s表示拆卸任務(wù)編號。

I表示拆卸任務(wù)集合，

M表示組合工作站數(shù)集合。

Wm表示第m對組合工作站開啟，則Wm=1，否則Wm=0。

m，z表示組合工作站編號。

k表示組合工作站的邊，k=1為左邊，k=2為右邊。

ximk表示任務(wù)i分配至第m個組合工作站的k邊。

yismk表示若任務(wù)i，s皆分配至第m個組合工作站的k邊，當(dāng)任務(wù)i先于任務(wù)s分配至該工作站內(nèi)時記yismk=1，否則yismk=0;當(dāng)任務(wù)s先于任務(wù)i分配至該工作站內(nèi)時記ysimk=1，否則ysimk=0。

BTimk表示分配在第m個組合工作站k邊的任務(wù)i的起始作業(yè)時刻。

FTjmk表示分配在第m個組合工作站k邊的任務(wù)j的截止作業(yè)時刻。

ti表示拆卸任務(wù)i所需時間;

CT表示節(jié)拍時間。

PL表示拆卸任務(wù)只能分配在左側(cè)工作站的拆卸任務(wù)集。

PR表示拆卸任務(wù)只能分配在右側(cè)工作站的拆卸任務(wù)集。

PE表示拆卸任務(wù)能分配在任意一側(cè)工作站的拆卸任務(wù)集。

di表示對拆卸任務(wù)i的需求指標(biāo)，若有需求，則di=1，否則di=0。

hi表示拆卸任務(wù)i的危害指標(biāo)，若有危害，則hi=1，否則hi=0。

nL表示左側(cè)拆卸任務(wù)集合。

nR表示右側(cè)拆卸任務(wù)集合。

li表示拆卸任務(wù)i分配至左側(cè)拆卸序列第l個。

ri表示拆卸任務(wù)i分配至右側(cè)拆卸序列第r個。

ei表示拆卸任務(wù)i所需能耗，為已知量。

em表示第m個組合工作站開啟時待機(jī)能耗，為已知量。

ed表示對需求零件進(jìn)行回收所需能耗，為已知量。

Aij表示任務(wù)優(yōu)先關(guān)系，若任務(wù)j是i的緊前拆卸任務(wù)，則Aij=1，否則Aij=0。

k(i)為任務(wù)位置屬性，若為左側(cè)作業(yè)則k(i)=1;若為右側(cè)作業(yè)，則k(i)=2;否則為3。

1.3 能耗分析

選擇任務(wù)i進(jìn)行拆卸時，假設(shè)所需能源包含一切用于拆卸該任務(wù)的能耗。例如，對拆卸工具啟動、照明、傳輸裝置啟動、人因等因素皆進(jìn)行歸一化處理，而不再單獨(dú)考慮。設(shè)定單位時間拆卸任務(wù)i所需能耗值ei，因此拆卸任務(wù)i所需能耗如下:

當(dāng)前工作站未分配任務(wù)時，工作站處于待機(jī)狀態(tài)。設(shè)定單位時間工作站待機(jī)能耗em，則工作站待機(jī)能耗如下:

拆卸過程中對需求零件要進(jìn)行二次處理才能回收利用，例如，零件的分類、搬運(yùn)、清洗等皆需能量供給。將該回收過程統(tǒng)一考慮在拆卸過程中完成，所述能耗用ed進(jìn)行簡化處理?；厥招枨罅慵哪芎娜缦?

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

對于目標(biāo)函數(shù):式(4)為最小化目標(biāo)F，包含4個子目標(biāo);式(5)為開啟工作站數(shù)f1，以減少拆卸線作業(yè)長度，從而有效減少能耗，提高空間利用率以及拆卸效率;式(6)為空閑指標(biāo)f2，減少工作站空閑待機(jī)時間，均勻分配拆卸任務(wù)使工作站負(fù)載均衡，減少拆卸資源浪費(fèi);式(7)為危害指標(biāo)f3，待拆卸產(chǎn)品中會有對人以及環(huán)境造成污染的有害物質(zhì)，因此需將危害零件集中盡早拆卸，以此降低拆卸危害;式(8)為能耗指標(biāo)f4，拆卸作業(yè)所需的成本主要源于能耗，因此減少拆卸能耗能有效提升經(jīng)濟(jì)效益。

對于約束條件:式(9)為拆卸任務(wù)分配約束，鑒于所提拆卸類型屬于完全拆卸，需將任一拆卸任務(wù)分配在指定工作站中進(jìn)行拆卸作業(yè);式(10)為開啟工位約束，保證工位依次成對開啟;式(11)為拆卸任務(wù)與開啟工位約束，拆卸任務(wù)被分配至某工位時，該工位處于開啟狀態(tài);式(12)為節(jié)拍約束，對于任一工作站內(nèi)所有拆卸任務(wù)作業(yè)時間之和不大于節(jié)拍時間。

式(13)為優(yōu)先關(guān)系約束，假設(shè)任務(wù)j是i的緊前任務(wù)，即Aij=1，且任務(wù)s先于i分配至第m個組合工作站k側(cè)。建立如圖2所示拆卸作業(yè)時間軸。確定任務(wù)i起始作業(yè)時刻BTimk，如式(18)所示。

式(14)與式(15)為站內(nèi)拆卸任務(wù)相對關(guān)系約束。假設(shè)任務(wù)s先于i分配至第m個組合工作站k側(cè)。該約束限定任務(wù)i與任務(wù)s僅能分配至同一組合工作站的同側(cè)。通過以下4種情況驗(yàn)證該約束的有效性。①當(dāng)任務(wù)i與任務(wù)s分配至不同組合工作站同側(cè)時，如圖3a所示，例如:任務(wù)s分配至第一個組合工作站左側(cè)，任務(wù)i分配至第二個組合工作站左側(cè)，即xi21=0，xs11=1，yis21=0，ysi11=1，可見不滿足上述約束;②當(dāng)任務(wù)i與任務(wù)s分配至相同組合工作站不同側(cè)時，如圖3b所示，例如:任務(wù)s分配至第二個組合工作站左側(cè)，任務(wù)i分配至第二個組合工作站右側(cè)，即xi22=0，xs21=1，yis22=0，ysi21=1，可見不滿足上述約束;③當(dāng)任務(wù)i與任務(wù)s分配至不同組合工作站且不同側(cè)時，如圖3c所示，例如:任務(wù)s分配至第一個組合工作站左側(cè)，任務(wù)i分配至第二個組合工作站右側(cè)，即xi22=0，xs11=1，yis22=0，ysi11=1，可見不滿足上述約束;④當(dāng)任務(wù)i與任務(wù)s分配至同一組合工作站同側(cè)時，如圖3d所示，例如:任務(wù)s分配至第二個組合工作站左側(cè)，任務(wù)i分配至第二個組合工作站左側(cè)，即xi21=1，xs21=1，yis21=0，ysi21=1，滿足上述約束。對比上述4種情形，僅第4種情形滿足所提約束，因而驗(yàn)證了該約束能有效限定分配至同一工作站內(nèi)任務(wù)間的位置關(guān)系。相比現(xiàn)有拆卸線平衡問題研究中以編碼序列依次分配拆卸任務(wù)，所建約束更能明確地線性表達(dá)站內(nèi)任務(wù)間相對位置關(guān)系。

式(16)與式(17)為拆卸任務(wù)分配約束，即只能在左側(cè)進(jìn)行拆卸作業(yè)的任務(wù)僅分配至左側(cè)工作站;只能在右側(cè)進(jìn)行拆卸作業(yè)的任務(wù)僅分配至右側(cè)工作站。

2 改進(jìn)差分進(jìn)化算法

2.1 改進(jìn)差分進(jìn)化算法

DE算法是一種基于自身種群差異的隨機(jī)演化算法，常在連續(xù)空間進(jìn)行優(yōu)化計算，具有快速收斂的能力。要將DE 算法用于求解混合整數(shù)規(guī)劃問題(Mixed Integer Programming，MIP)，需對算法進(jìn)行離散化改進(jìn)處理。鑒于DE算法參數(shù)少，全局搜索能力強(qiáng)，結(jié)合差分隨機(jī)策略DE/rand(如式(20)所示)，差分進(jìn)化策略DE/best(如式(21)所示)，提出一種IDE算法。

式中:F在[0，2]之間取值，為變異算子;g為進(jìn)化代數(shù);xr1，g、xr2，g和xr3，g對應(yīng)于第g代種群中3個互不相同且不同于個體Pb，g的個體;(xr2，g-xr3，g)為偏差向量。

式中:F為變異算子，在[0，2]之間取值;g為進(jìn)化代數(shù);qr1，g、qr2，g和qr3，g對應(yīng)于第g代種群中3個互不相同且不同于個體Pb，g的個體;(qr2，g-qr3，g)為偏差向量。

2.1.1 差分隨機(jī)策略

為避免IDE算法因計算過程快速陷入早熟狀態(tài)而無法做到全局搜索等問題，將差分隨機(jī)策略加入算法尋優(yōu)過程，以確保解的多樣性，從而保證算法的分布性能。差分隨機(jī)策略具體步驟如下:

步驟1采用式(20)獲得第b個個體Pb，g發(fā)生第g+1次進(jìn)化的變異向量Prand，g+1，其中，b∈{1，2，...，N-Nevol}。

步驟2選用偏差向量中元素與xr1，g進(jìn)行變異操作得到新個體Prand，g+1(可能有多個)。

步驟3Prand，g+1與Pb，g分別進(jìn)行交叉操作獲得第g+1代的新個體Pb，g+1。

步驟4對第g 次進(jìn)化得到的所有新個體Pb，g+1和Pb，g進(jìn)行Pareto比較，將其中一個Pareto較優(yōu)解替換Pb，g，即完成Pb，g的更新。

2.1.2 差分進(jìn)化策略

為使所提算法具備快速尋優(yōu)性能，將差分進(jìn)化策略加入IDE算法中，保證算法能夠快速收斂，以此提高算法運(yùn)算效率。差分進(jìn)化策略步驟如下:

步驟1采用式(21)獲得第b個個體Pb，g發(fā)生第g+1次進(jìn)化的變異向量Pbest，g+1，其中b∈{N+1-Nevol，N+2-Nevol，…，N}。

步驟2選用偏差向量中元素與qr1，g進(jìn)行變異操作得到新個體Pbest，g+1(可能有多個)。

步驟3按式(22)獲取第g+1代的新個體Pbest，g+1。

式中:rand表示在[0，1]之間產(chǎn)生一個隨機(jī)數(shù);CR為交叉算子，取值范圍[0，1]。當(dāng)rand＞CR時，隨機(jī)選擇外部檔案中個體qbest與Pb，g進(jìn)行交叉操作獲得第g+1代的新個體Pb，g+1;當(dāng)rand≤CR時，將Pbest，g+1與Pb，g進(jìn)行交叉操作獲得第g+1代的新個體Pb，g+1。

步驟4對第g次進(jìn)化所得的所有新個體Pb，g+1和Pb，g進(jìn)行模擬退火處理，即進(jìn)行Pareto比較，將其中一個Pareto較優(yōu)解替換Pb，g，即完成Pb，g的更新。

2.1.3 變異交叉

差分隨機(jī)策略及差分進(jìn)化策略所用變異及交叉操作，分別如圖4和圖5所示。以差分隨機(jī)策略中拆卸任務(wù)數(shù)量為8個的待變異個體Pb，g=[1，2，5，3，6，8，7，4]為例:

(1)對于變異 獲取第g代種群中3個互不相同且不同于個體Pb，g的個體:xr1，g=[1，3，2，5，6，8，7，4]，xr2，g=[1，2，3，5，6，8，7，4]，xr3，g=[1，2，3，6，5，8，7，4];得到偏差向量(xr2，g-xr3，g)=(5，6)，對于偏差向量中的拆卸任務(wù)5，其在xr1，g中的緊前任務(wù)為拆卸任務(wù)1，緊后任務(wù)為拆卸任務(wù)8，因此在拆卸任務(wù)1和拆卸任務(wù)8之間隨機(jī)插入到拆卸任務(wù)1之后，得到第一個變異向量Prand，g+1=[1，5，3，2，6，8，7，4]。同理，對于偏差向量中的拆卸任務(wù)6，可以得到第二個變異向量Prand，g+1=[1，3，6，2，5，8，7，4]?？梢?，變異向量的個數(shù)與偏差向量中拆卸任務(wù)的個數(shù)相同。

(2)對于交叉 假設(shè)Pb，g的隨機(jī)交叉點(diǎn)在第三位置和第五位置，兩個交叉點(diǎn)之間的拆卸任務(wù)為拆卸任務(wù)5、拆卸任務(wù)3和拆卸任務(wù)6，然后根據(jù)這3個拆卸任務(wù)在第一個變異向量中的排序來調(diào)整拆卸任務(wù)5、拆卸任務(wù)3和拆卸任務(wù)6在Pb，g中的排序，即可得到新個體Pb，g+1=[1，2，3，6，5，8，7，4]。

2.2 雙邊拆卸編碼解碼

2.2.1 編碼

DLBP屬于多目標(biāo)離散問題，在編碼過程中需要考慮優(yōu)先關(guān)系約束，形成一個可行的拆卸序列。因此，借鑒一種染色體編碼方式，染色體序號為拆卸任務(wù)編號，如圖4和圖5所示。在編碼過程中引入由0和1組成的優(yōu)先關(guān)系矩陣。任意選擇無緊前任務(wù)的拆卸任務(wù)(對應(yīng)優(yōu)先關(guān)系矩陣中列元素全為0)進(jìn)行分配。當(dāng)前任務(wù)分配后，將該任務(wù)所在列的全部元素變?yōu)?，以此表示該任務(wù)已分配至工作站;將該任務(wù)所在行的全部元素變?yōu)?，以此表示解除該任務(wù)對其他未拆卸任務(wù)的緊前約束。

2.2.2 解碼

雙邊拆卸不同于單邊拆卸，需考慮拆卸任務(wù)的工位約束。拆卸序列上方用L，R，E分別代表該任務(wù)只能分配在組合工作站左側(cè)工位，組合工作站右側(cè)工位及不受工位約束。對于不受拆卸方向約束的任務(wù)，采用一種類啟發(fā)式規(guī)則。建立左右兩側(cè)工作站拆卸任務(wù)的時間軸，在滿足優(yōu)先關(guān)系約束的前提下，將可任意分配拆卸方向的任務(wù)分配至左右兩側(cè)總截止時間較小的一側(cè)。FTL表示組合工作站左側(cè)第一個拆卸任務(wù)開始到當(dāng)前最后一個拆卸任務(wù)結(jié)束的時刻;FTR為組合工作站右側(cè)第一個拆卸任務(wù)開始到當(dāng)前最后一個拆卸任務(wù)結(jié)束的時刻。對于任務(wù)i，BTimk為站內(nèi)起始作業(yè)時刻;BTimk為總起始作業(yè)時刻;WFTimk為站內(nèi)截止作業(yè)時刻;FTimk為總截止作業(yè)時刻。上述時刻在數(shù)學(xué)建模過程中已詳細(xì)闡述，解碼過程不再贅述。

具體解碼步驟如下:

步驟1令i=1。

步驟2判斷任務(wù)i的拆卸方位。若k(i)=1，?i∈PL，將任務(wù)分配至組合工作站左側(cè);若k(i)=2，?i∈PR，將任務(wù)分配至組合工作站右側(cè);若k(i)=3，?i∈PE時，則判斷FTL與FTR大小，根據(jù)下式重新賦值分配方向，即

步驟3若當(dāng)前任務(wù)i與緊前任務(wù)q在同一個組合工作站，則轉(zhuǎn)步驟4，否則轉(zhuǎn)至步驟5。

步驟4確定當(dāng)前任務(wù)i分配時的站內(nèi)起始作業(yè)時刻WBTimk，總起始作業(yè)時刻BTimk，站內(nèi)截止作業(yè)時刻WFTimk與總截止作業(yè)時刻FTimk，轉(zhuǎn)步驟6。

步驟5令該任務(wù)站內(nèi)起始時刻WBTimk=0，BTimk為下一個工作站開始時刻，即BTimk=(m+1)CT，確定站內(nèi)截止時刻WFTimk與總截止時刻FTimk，轉(zhuǎn)步驟6。

步驟6確定當(dāng)前工作站站內(nèi)剩余時間RT=CT-WBTmk，若當(dāng)前任務(wù)ti＞RT，則開啟新的工作站m=m+1，RT=CT;否則，更新站內(nèi)RT，RT=CT-WFTimk。

步驟7繼續(xù)下一任務(wù)分配(i=i+1)，轉(zhuǎn)步驟2，直至任務(wù)分配結(jié)束。

2.3 算法更新機(jī)制

2.3.1 種群更新

算法的全局搜索能力和收斂速度均受種群更新策略影響。為使更新后的種群在收斂性和分布性方面皆優(yōu)于初始種群，本文運(yùn)用模擬退火思想對種群中每一個體進(jìn)行逐步更新，即所用IDE算法每迭代一次后可形成新一代種群(規(guī)模與初始種群一致)，該新種群內(nèi)的個體性能皆優(yōu)于初始種群中對應(yīng)位置的個體。此外，本文設(shè)置獨(dú)立于初始種群之外的外部檔案集來保存較好的非劣解，且運(yùn)用精英策略將外部檔案中的非劣解隨機(jī)插入下一代初始種群中，以提高下一代初始種群的質(zhì)量，從而加速算法尋優(yōu)過程。

2.3.2 外部檔案更新機(jī)制

本文所提IDE算法求解大規(guī)模算例時所產(chǎn)生偏差向量的維度較大，因而變異交叉后得到的較優(yōu)個體也較多，若將這類非劣解放入外部檔案中，將使其規(guī)模急劇增大，算法運(yùn)算效率大幅度降低。因此，結(jié)合Pareto思想對新得到的非劣解進(jìn)行一次篩選，再與外部檔案結(jié)合進(jìn)行第二次篩選，從而提升算法運(yùn)算性能，提高其求解效率。Pareto思想具體解釋為:假設(shè)兩個拆卸序列A，B對應(yīng)的適應(yīng)度函數(shù)值分別為AFj，BFj，有j個子目標(biāo)j∈{1，2，3，…，n}。若AFj，BFj滿足式(23)，則稱A支配B，B為支配解，A為非支配解，即較優(yōu)解，所有非支配解形成的解集為Pareto解集。但Pareto解個數(shù)無法預(yù)測且數(shù)量較多，為保證算法運(yùn)算效率，需對外部檔案規(guī)模進(jìn)行限定。

現(xiàn)有對外部檔案進(jìn)行更新的較好方法包括:聚類法、自適應(yīng)網(wǎng)格法、ε分配法和偏好排序法。但上述方法存在計算效率低、后退和收縮等問題。而文獻(xiàn)[23]經(jīng)試驗(yàn)得出運(yùn)用NSGA-II擁擠距離機(jī)制所得結(jié)果更好，因擁擠距離機(jī)制不需要將新的方案與外部檔案中方案進(jìn)行比較，僅根據(jù)各個方案的子目標(biāo)進(jìn)行計算篩選。NSGA-II擁擠距離機(jī)制解釋為:假設(shè)處于邊緣的第j個子目標(biāo)的擁擠距離=∞，其中E為外部種群規(guī)模。非邊緣的第i個非劣解的第j個子目標(biāo)的擁擠距離如式(24)。

式中，第i個非劣解的擁擠距離計算式為Ci=分別表示第j個子目標(biāo)的最大值和最小值。對子目標(biāo)AFj，j∈{1，2，3，…，n}按照升序方式排列，選取擁擠距離較大的解放入外部檔案。

2.4 算法總流程圖

本文所提IDE算法將差分隨機(jī)策略和差分進(jìn)化策略融入DE算法，保證算法的全局搜索能力和快速收斂性能。結(jié)合Pareto思想和NSGA-II擁擠距離機(jī)制對當(dāng)代種群及外部檔案進(jìn)行更新，保留解的多樣性與優(yōu)越性。采用精英策略將較好解拆入下一代初始種群，以此提高下一代初始種群質(zhì)量。綜上所述，給出算法流程(如圖6)。算法主要步驟如下:

步驟1算法參數(shù)初始化。種群數(shù)量N，最大循環(huán)次數(shù)G，分組率Pam，外部檔案規(guī)模Q。

步驟2生成初始種群，通過Pareto比較初始種群的目標(biāo)函數(shù)值并將Pareto較優(yōu)解輸出至外部檔案中。

步驟3初始化迭代次數(shù)g=1。

步驟4將種群分為數(shù)量為N1的第一種群和數(shù)量為N2的第二種群。

步驟5對第一種群進(jìn)行差分隨機(jī)策略的更新。

步驟6對第二種群進(jìn)行差分進(jìn)化策略的更新。

步驟7運(yùn)用Pareto思想對更新后的當(dāng)代種群進(jìn)行篩選。

步驟8結(jié)合Pareto思想和NSGA-II擁擠距離機(jī)制對外部檔案進(jìn)行更新。

步驟9將外部檔案中的解隨機(jī)插入到下一代初始種群中。

步驟10若g＞G，則輸出外部檔案中的Pareto較優(yōu)解為拆卸任務(wù)分配方案;否則，令g=g+1并轉(zhuǎn)步驟3。

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

3.1 算例驗(yàn)證

為驗(yàn)證所提IDE算法的可行性與高效性，引用單邊拆卸線經(jīng)典案例以及最新發(fā)表文獻(xiàn)中雙邊實(shí)例的求解結(jié)果與之對比。為保證算法的公正性，對比所用結(jié)果皆引用于已發(fā)表文獻(xiàn)。

對于一個算法，其核心體現(xiàn)在結(jié)構(gòu)優(yōu)越性上，且考慮拆卸線平衡問題的特殊性，即雙邊拆卸與單邊拆卸的區(qū)別僅在于解碼方式不同，而算法結(jié)構(gòu)并未發(fā)生改變。因此，將所提算法在結(jié)構(gòu)不變的前提下與經(jīng)典單邊拆卸案例進(jìn)行對比，以此驗(yàn)證本文所提算法的高效性。此外，引用雙邊拆卸實(shí)例與所提算法進(jìn)行對比驗(yàn)證，不僅充實(shí)了對比的可信度，還彌補(bǔ)了現(xiàn)有雙邊拆卸研究中僅與傳統(tǒng)單邊案例進(jìn)行對比驗(yàn)證的不足。

測試實(shí)驗(yàn)所采用的計算機(jī)配置為Pentium(R)Dual-Core CPU E6700@3.20 GHz 4 G，在Win7系統(tǒng)下MATLAB R2014b運(yùn)行。

3.1.1 小規(guī)模算例驗(yàn)證

應(yīng)用文獻(xiàn)[24]中給出的10拆卸任務(wù)小規(guī)模案例。已有文獻(xiàn)所用的算法包括:蟻群優(yōu)化(Ant Colony Optimization，ACO)算法[25]、人工蜂群(Artificial Bee Colony，ABC)算法[24]、啟發(fā)式算法(Heuristic)[26]、禁忌搜索(Tabu Search，TS)[19]。求解目標(biāo)包括:工作站指標(biāo)(F1)，需求指標(biāo)(F2)，空閑指標(biāo)(F3)，危害指標(biāo)(F4)。上述算法對應(yīng)求解結(jié)果如表1所示。

表1 已有算法對P10問題的求解結(jié)果

對于P10問題，建立四水平三因素正交實(shí)驗(yàn)表，通過正交計算，設(shè)置參數(shù)如下:種群規(guī)模N=100，最大循環(huán)次數(shù)G=80，分組率Pam=0.5。算法獨(dú)立運(yùn)行10次，取其中一次求解結(jié)果如表2所示。通過對比可見，ACO、ABC、Heuristic、TS算法獨(dú)立運(yùn)行一次僅能獲得一組拆卸方案。而所提IDE算法能求解到P10問題的7個高質(zhì)量解，且每一個求解方案均不劣于上述求解結(jié)果。此外，縱向?qū)Ρ雀鱾€子目標(biāo)最小值，可見表2中F2與F4最小值皆優(yōu)于表1求得的最小值。因此，驗(yàn)證了IDE算法運(yùn)用于小規(guī)模算例的可行性與高效性。

表2 IDE算法對P10問題求解結(jié)果

3.1.2 中規(guī)模算例驗(yàn)證

應(yīng)用文獻(xiàn)[15]給出的25拆卸任務(wù)中規(guī)模拆卸案例。已有文獻(xiàn)所用算法包括:變領(lǐng)域搜索(Variable Neighborhood Search，VNS)[14]、強(qiáng)化學(xué)習(xí)(Reinforcement Learning，RL)[15]、粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[27]、遺傳算法(Genetic Algorithm，GA)[28]、模擬退火算法(Simulated Annealing，SA)[29]、遺傳模擬退火(Genetic Algorithm Simulated Annealing，GASA)算法[20]等。上述算法對應(yīng)求解結(jié)果如表3所示。

表3 已有算法對P25問題求解結(jié)果

與小規(guī)模案例一致，對于P25問題，通過正交計算，設(shè)定參數(shù)如下:種群規(guī)模N=200，最大循環(huán)次數(shù)G=100，分組率Pam=0.4，外部最優(yōu)種群Q=10。算法獨(dú)立運(yùn)行10次，取其中一次求解結(jié)果如表4。可見，所提IDE算法所求方案中，空閑指標(biāo)F3的最小值為802，危害指標(biāo)F4最小值為70，皆優(yōu)于上述算法相應(yīng)目標(biāo)的最小值，且所得到的解數(shù)量更多，效果較優(yōu)，從而證明了所提算法運(yùn)用在中規(guī)模案例時的可行性與高效性。

表4 IDE對P25問題求解結(jié)果

3.1.3 大規(guī)模算例驗(yàn)證

應(yīng)用文獻(xiàn)[30]中的52拆卸任務(wù)大規(guī)模案例。與中小規(guī)模案例不同，該案例將閑置率FIdel、負(fù)載均衡指標(biāo)FSmooth以及拆卸成本FCost作為目標(biāo)函數(shù)求解。已有文獻(xiàn)求解該算例采用的算法包括:多目標(biāo)細(xì)菌覓食優(yōu)化(Multi-Objective Bacteria Foraging Optimization，MBFO)算法[31]、人工魚群算法(Artificial Fish Swarm Algorithm，AFSA)[32]、ACO算法[16]、GASA 算法[33]、蟻群遺傳優(yōu)化算法(Ant Colony and Genetic Algorithm，ACGA)[34]。對于P52問題，通過正交計算，設(shè)定參數(shù)如下:種群規(guī)模N=200，最大循環(huán)次數(shù)G=200，分組率Pam=0.4，外部最優(yōu)種群Q=10。為保證算法公正性，使算法獨(dú)立運(yùn)行10次，選擇其中較好一次求解結(jié)果，如表5所示。將求解結(jié)果與上述五種算法所求結(jié)果進(jìn)行對比，鑒于各個算法對閑置率的求解結(jié)果皆為0.057 9，因此建立二維直角坐標(biāo)系，對比負(fù)載均衡指標(biāo)及拆卸成本等兩個目標(biāo)函數(shù)，如圖7所示。

表5 IDE對P52問題求解結(jié)果

由表3～表5可見，所提算法求解方案中，負(fù)載均衡指標(biāo)FSmooth最大值為0.999 8，拆卸成本FCost最小值為127，所求目標(biāo)函數(shù)值皆優(yōu)于以往算法求解的極值。除了上述目標(biāo)函數(shù)值的優(yōu)越性，結(jié)合圖7可見，所提IDE算法求解結(jié)果能有效包裹上述5種算法的結(jié)果，且平滑率更高，成本指標(biāo)更低，驗(yàn)證了該算法運(yùn)用在大規(guī)模案例求解時的可行性與有效性。

3.1.4 雙邊實(shí)例驗(yàn)證

應(yīng)用最新發(fā)表的文獻(xiàn)[35]中電冰箱拆卸實(shí)例，該案例優(yōu)化目標(biāo)分別為:工作站指標(biāo)(F1)、需求指標(biāo)(F2)、空閑指標(biāo)(F3)、危害指標(biāo)(F4)。求解結(jié)果如表6所示，可見該文獻(xiàn)中所用蝙蝠算法(Bat Algorithm，BA)求得工作站數(shù)目為6～9，空閑指標(biāo)在5 907～51 679之間。本文所提IDE算法對該案例求解時，設(shè)定參數(shù)如下:種群規(guī)模N=200，最大循環(huán)次數(shù)G=200，分組率Pam=0.3，設(shè)置外部檔案為Q=8。算法獨(dú)立運(yùn)行10次，取其中較好一次如表6所示，求得工作站數(shù)目在5～9之間，空閑指標(biāo)最小值為765。當(dāng)工作站數(shù)量為5 時，可見所提IDE算法求得的工作站數(shù)與空閑指標(biāo)大幅度優(yōu)于BA算法。當(dāng)兩種求解結(jié)果中工作站數(shù)目皆為9時，對比F2、F3和F4可見，IDE算法求得的最后兩組解的目標(biāo)函數(shù)值完全占優(yōu)于BA算法的倒數(shù)第二組解的目標(biāo)函數(shù)值。綜上可見，本文所用IDE算法在求解性能上優(yōu)于BA算法。

3.2 實(shí)例應(yīng)用

為使研究更具實(shí)用性，引用文獻(xiàn)[18]中某打印機(jī)完全拆卸實(shí)例。該實(shí)例中具體信息為本課題組實(shí)地調(diào)研所得，即該打印機(jī)由55個拆卸單元組成，每項(xiàng)拆卸任務(wù)作業(yè)時間(單位:s)取決于多次測試拆卸該任務(wù)實(shí)際作業(yè)時間的平均值。需求數(shù)量(單位:個)根據(jù)市場考察統(tǒng)計得出。任務(wù)的拆卸方向取決于實(shí)際工廠中分配的拆卸方向(1表示左側(cè)拆卸、2表示右側(cè)拆卸，3表示左右均可進(jìn)行拆卸)。最終統(tǒng)計拆卸任務(wù)相關(guān)信息如表7，任務(wù)間優(yōu)先關(guān)系如圖8所示。

表6 BA和IDE求解結(jié)果

表7 打印機(jī)拆卸信息表

根據(jù)該算例特性，通過正交計算，設(shè)定算法參數(shù)如下:種群規(guī)模N=250，最大循環(huán)次數(shù)G=200，分組率Pam=0.4，外部最優(yōu)種群Q=14。為保證求解結(jié)果的穩(wěn)定性，使算法運(yùn)行10次，取較穩(wěn)定一次結(jié)果如表8所示。

由表8可見，所提IDE算法求得的14組方案中，最小工作站數(shù)均為6，最小化空閑指標(biāo)為8 441，最小化危害指標(biāo)為185，最小化能耗指標(biāo)為795。若是著重考慮能耗指標(biāo)，可選擇能耗較少的拆卸方案1，其工位分布如圖9所示。若綜合考慮負(fù)載均衡指標(biāo)，危害指標(biāo)與能耗，可選擇方案3，4，8。

表8 IDE對打印機(jī)拆卸求解結(jié)果

續(xù)表8

4 結(jié)束語

本文針對現(xiàn)有雙邊拆卸線還未深入研究能耗問題的不足，建立了考慮能耗及工位約束的雙邊拆卸線數(shù)學(xué)模型，提出一種改進(jìn)的IDE算法求解以最小化工作站數(shù)、負(fù)載均衡指標(biāo)、危害指標(biāo)和能耗指標(biāo)為優(yōu)化目標(biāo)的多目標(biāo)拆卸線平衡問題。

本文首次采用時間軸的方式線性化表達(dá)任務(wù)間的優(yōu)先關(guān)系約束及站內(nèi)位置約束，彌補(bǔ)了以往拆卸線模型不能精確求解的不足。對所建模型進(jìn)行詳細(xì)闡述，分析了拆卸生產(chǎn)過程中主要能耗來源。針對所提能耗問題，在雙邊拆卸解碼過程中加入對應(yīng)啟發(fā)式分配規(guī)則，以保證求解結(jié)果的穩(wěn)定性與高效性。

將差分隨機(jī)策略及差分進(jìn)化策略融入差分進(jìn)化算法，以此保證算法的全局搜索能力和快速收斂性能。結(jié)合Pareto思想及擁擠距離機(jī)制，保留解的多樣性與優(yōu)越性。運(yùn)用所提算法分別求解P10、P25和P52 3個經(jīng)典案例，并與相關(guān)智能算法進(jìn)行對比，驗(yàn)證所提算法的有效性。為使算法對比更為全面，對比了電冰箱雙邊拆卸實(shí)例，以此確保算法的可行性。最后通過打印機(jī)拆卸實(shí)例計算，求解出14種高質(zhì)量方案，決策者可根據(jù)自身需求進(jìn)行選擇。

本文對空間干涉問題做了相關(guān)假設(shè)，所用實(shí)例為種類單一的簡單產(chǎn)品。因此，考慮雙邊位置干涉因素，對比多種類及復(fù)雜拆卸案例的混流雙邊拆卸線平衡問題值得進(jìn)一步探索。