多目標(biāo)斗鏈?zhǔn)交炝鞑鹦毒€平衡的Pareto花朵授粉算法

曾艷清，張則強(qiáng)，張 穎，劉思璐，李云鵬

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

0 引言

科技的快速發(fā)展加快了產(chǎn)品更新?lián)Q代的步伐，由此產(chǎn)生了大量的廢舊產(chǎn)品。處理廢舊產(chǎn)品的主要方式有再制造、再使用和回收。再制造和再使用能夠延長產(chǎn)品的使用周期，而廢舊產(chǎn)品的拆卸回收能夠?qū)崿F(xiàn)資源能源的再利用，并能夠減少廢舊產(chǎn)品中有危害物質(zhì)對生態(tài)環(huán)境的影響，同時(shí)也能夠?yàn)椴鹦镀髽I(yè)帶來可觀的經(jīng)濟(jì)效益。拆卸生產(chǎn)線是處理大規(guī)模廢舊產(chǎn)品的最主要的方式。拆卸線具有高效率、低成本、低污染等優(yōu)勢，已被眾多拆卸企業(yè)所采用。為進(jìn)一步提高拆卸線的生產(chǎn)效率，在滿足多種生產(chǎn)約束的前提條件下，如何合理地將拆卸任務(wù)分配到生產(chǎn)線中，并滿足多項(xiàng)生產(chǎn)線指標(biāo)的優(yōu)化，依然是一項(xiàng)難題，即拆卸線平衡問題(Disassembly Line Balancing Problem, DLBP)[1]。

現(xiàn)有文獻(xiàn)中，一般通過優(yōu)化工作站內(nèi)任務(wù)分配或是改善生產(chǎn)線布局形式來提高生產(chǎn)線效率。在進(jìn)行任務(wù)分配時(shí)要求每個(gè)工作站中的負(fù)荷盡可能相同，均衡工作站作業(yè)時(shí)間一直被視為拆卸線平衡問題最主要的優(yōu)化目標(biāo)。但拆卸線平衡問題是離散組合優(yōu)化問題，通過算法優(yōu)化分配到工作站中任務(wù)的方式，并未改變作業(yè)不均衡的本質(zhì)，因?yàn)楣と吮还潭ㄔ诠ぷ髡局校由瞎と俗鳂I(yè)效率和作業(yè)任務(wù)的差異，生產(chǎn)線難以真正實(shí)現(xiàn)負(fù)荷平衡。

學(xué)術(shù)界針對生產(chǎn)線不平衡問題的主要研究成果是斗鏈模型。斗鏈作為一種生產(chǎn)組織方式，規(guī)定工人可以在連續(xù)的多個(gè)工位中作業(yè)。這種作業(yè)方式突破了固定工位的限制，工人只需按一定的作業(yè)效率排列在生產(chǎn)線上，無需過多干預(yù)，生產(chǎn)線最終即可實(shí)現(xiàn)自我平衡[2]。因斗鏈生產(chǎn)組織方式良好的自組織性和自平衡性，已被廣泛應(yīng)用于裝配線與快遞物流業(yè)中[3]。故本文考慮將斗鏈生產(chǎn)組織方式應(yīng)用于拆卸線中，以提升拆卸線的平衡性能。

此外，因較多待拆卸產(chǎn)品具有結(jié)構(gòu)和工藝相似的特點(diǎn)，混合品種拆卸線(簡稱混流拆卸線)受到眾多拆卸企業(yè)的青睞[4]。混流拆卸線不僅能夠提高生產(chǎn)線的利用率，還能夠減少生產(chǎn)線建設(shè)成本，具有廣闊的應(yīng)用前景。因此，在拆卸線形式上，本文將構(gòu)建混流拆卸線平衡模型。

拆卸線平衡問題是典型的NP-hard問題[5]，因問題約束較復(fù)雜，優(yōu)化目標(biāo)較多，求解難度較大，學(xué)術(shù)界求解該問題的出發(fā)點(diǎn)是探索高效求解方法，主要包括精確方法、啟發(fā)式方法和包含群智能算法在內(nèi)的元啟發(fā)式方法。如McGovern等[6]、Avikal等[7]均采用啟發(fā)式方法對拆卸線平衡問題進(jìn)行求解。雖然啟發(fā)式方法能夠快速得到問題的解，但很難求得最優(yōu)解。Altekin等[8]通過數(shù)學(xué)規(guī)劃法求解以利潤為導(dǎo)向的拆卸線平衡問題，并用CPLEX軟件求得問題的最優(yōu)解；Bentaha等[9]提出了隨機(jī)作業(yè)時(shí)間的混合整數(shù)拆卸線平衡模型，同樣采用精確方法進(jìn)行求解。精確方法能夠得到小規(guī)模問題的最優(yōu)解，但在求解大規(guī)模問題時(shí)難以在合理時(shí)間范圍內(nèi)獲得滿意解。McGovern等利用遺傳算法[5]、蟻群算法[10]等元啟發(fā)式算法對多目標(biāo)拆卸線平衡問題進(jìn)行了優(yōu)化，能夠快速獲得問題的近優(yōu)解或滿意解?；ǘ涫诜鬯惴ㄗ鳛橐环N新近提出的元啟發(fā)式方法，具有參數(shù)少、結(jié)構(gòu)簡單、局部搜索能力強(qiáng)等優(yōu)點(diǎn)，在拆卸序列優(yōu)化和車間調(diào)度問題中均表現(xiàn)出較優(yōu)的求解性能。基于此，本文考慮將花朵授粉算法用于優(yōu)化拆卸線平衡問題，進(jìn)一步拓展問題的優(yōu)化途徑。

拆卸線平衡問題是多目標(biāo)組合優(yōu)化問題，其優(yōu)化目標(biāo)主要包括最小化工位空閑時(shí)間、最大化拆卸利潤、最小化拆卸危害[5]。文獻(xiàn)[7-9，11-12]并未考慮這些優(yōu)化目標(biāo)，無法全面準(zhǔn)確地評價(jià)拆卸線的性能。而文獻(xiàn)[5-6，10，13]在求解多目標(biāo)問題時(shí)采用字典順序法或加權(quán)法這類單目標(biāo)方法進(jìn)行求解，一次只能得到一個(gè)解，無法獲得在各個(gè)目標(biāo)上各有側(cè)重的多種平衡方案，喪失了多目標(biāo)問題解的多樣性。丁力平等[14]采用基于Pareto支配關(guān)系的多目標(biāo)蟻群算法優(yōu)化拆卸線平衡問題，能夠得到多個(gè)較優(yōu)方案。在此基礎(chǔ)上，張則強(qiáng)課題組采用擁擠距離篩選非劣解的精英保留策略進(jìn)一步提高了多目標(biāo)元啟發(fā)式方法的求解性能[15-19]。借鑒上述多目標(biāo)優(yōu)化方法，本文將設(shè)計(jì)多目標(biāo)花朵授粉算法對多目標(biāo)斗鏈?zhǔn)交炝鞑鹦毒€平衡問題進(jìn)行優(yōu)化。

綜上所述，本文考慮在混流拆卸線中實(shí)施斗鏈生產(chǎn)組織方式，建立多目標(biāo)斗鏈?zhǔn)交炝鞑鹦毒€平衡模型，同時(shí)構(gòu)造基于Pareto支配關(guān)系的多目標(biāo)花朵授粉算法，設(shè)計(jì)結(jié)合問題特征的算法策略，并驗(yàn)證模型和算法的性能，以及分析斗鏈?zhǔn)交炝鞑鹦毒€的實(shí)際應(yīng)用能力。

1 斗鏈?zhǔn)交炝鞑鹦毒€平衡問題

1.1 問題描述

斗鏈?zhǔn)且环N生產(chǎn)組織方式，只需將工人按照作業(yè)效率從小到大的順序分配到生產(chǎn)線上，生產(chǎn)線就能夠?qū)崿F(xiàn)自平衡，且達(dá)到最大生產(chǎn)效率。在斗鏈生產(chǎn)線中，工人按照各自效率朝著生產(chǎn)線下游方向作業(yè)，當(dāng)遇到下游工人時(shí)即交接手中任務(wù)，同時(shí)沿生產(chǎn)線上游方向返回，直到遇到上游工人時(shí)即接替其手中任務(wù)，如此循環(huán)，工人最終將在固定的位置進(jìn)行任務(wù)交接，工人作業(yè)區(qū)間固定，作業(yè)任務(wù)也固定，此時(shí)斗鏈系統(tǒng)收斂，生產(chǎn)線達(dá)到平衡，生產(chǎn)效率最高[2]。

在斗鏈拆卸線中，為實(shí)現(xiàn)生產(chǎn)線的平衡，不設(shè)固定工作站，工人可以按照各自作業(yè)效率來完成平衡狀態(tài)時(shí)的任務(wù)量。在理想斗鏈系統(tǒng)中，作業(yè)速度遠(yuǎn)大于傳送帶速度和返回速度，故不考慮傳送帶速度和返回速度對系統(tǒng)的影響，但在拆卸線中工人作業(yè)速度并非遠(yuǎn)大于返回速度，故需要考慮返回速度對系統(tǒng)平衡性的影響。文獻(xiàn)[20]已驗(yàn)證了考慮返回速度時(shí)斗鏈系統(tǒng)依然能夠收斂，且每個(gè)工人的作業(yè)時(shí)間與返回時(shí)間之和相等。將斗鏈拆卸線上所有任務(wù)歸一化為1，工人m與工人m+1之間的交接位置

(1)

式中：vk表示工人k的作業(yè)速度，wk表示工人k的返回速度，M表示總工人數(shù)，且k,m=1, 2, …,M。

工人m的工作區(qū)間

(2)

工人m的作業(yè)任務(wù)比重

(3)

在斗鏈拆卸線中，將所有零部件的平均作業(yè)時(shí)間之和視為所有工人需要完成的總?cè)蝿?wù)量，而每個(gè)工人將按照各自的作業(yè)效率完成平衡區(qū)間內(nèi)的任務(wù)量。待拆卸產(chǎn)品一般多樣化，為提高拆卸線的利用率，可將具有相似結(jié)構(gòu)的同類產(chǎn)品放在同一拆卸線上進(jìn)行拆卸作業(yè)，實(shí)現(xiàn)同類產(chǎn)品的混流拆卸。根據(jù)各品種中的零件優(yōu)先關(guān)系建立綜合優(yōu)先關(guān)系圖，不同品種的產(chǎn)品零件不盡相同，引入零件存在變量δnq，

(4)

則在混流拆卸線中零件n的綜合拆卸時(shí)間

(5)

式中：ωq為品種q的拆卸比例，tnq為品種q中零件n的拆卸時(shí)間，Q為總的品種數(shù)，q=1, 2, …,Q。

斗鏈拆卸線中工人的作業(yè)速度不同，但在工作區(qū)間內(nèi)完成各自拆卸任務(wù)所需的時(shí)間相同，可將該時(shí)間類比于傳統(tǒng)拆卸線中的節(jié)拍。為確保完成拆卸任務(wù)量，拆卸線上的工人數(shù)及其作業(yè)速度需滿足

(6)

其中TC表示拆卸線節(jié)拍，即完成單位比例下的Q種產(chǎn)品時(shí)，每個(gè)拆卸工人的有效作業(yè)時(shí)間，其表達(dá)式為

(7)

式中：ηL表示生產(chǎn)線效率，因?qū)嶋H拆卸線上并非所有工作時(shí)間都為有效工作時(shí)間，生產(chǎn)線效率表示有效作業(yè)時(shí)間與工作時(shí)間之比，故0<ηL<1；R表示單位小時(shí)的拆卸任務(wù)量，

(8)

式中：Dy表示年拆卸量，Wy表示年工作周數(shù)，Sw表示每周的工作天數(shù)，Hs表示每天的工作時(shí)間(小時(shí))。

在拆卸線中還需要考慮零部件的拆卸需求和危害性。零件n的拆卸需求量dn是根據(jù)其價(jià)值和市場需求量來確定的，其危害性hn為0-1變量，有

(9)

(10)

(11)

傳統(tǒng)拆卸線中固定工作站和節(jié)拍時(shí)間，而斗鏈拆卸線突破節(jié)拍時(shí)間的限制，但在離散問題中，斗鏈系統(tǒng)難以保證每名工人的作業(yè)時(shí)間與理論作業(yè)區(qū)間完全吻合，工人實(shí)際作業(yè)時(shí)間可能小于、等于或大于理論作業(yè)時(shí)間，即存在等待或超越現(xiàn)象，這些都將影響生產(chǎn)線的效率。故在分配任務(wù)時(shí)盡量使實(shí)際作業(yè)時(shí)間與理論作業(yè)時(shí)間相等，即減小作業(yè)區(qū)間的不均衡性。待拆卸產(chǎn)品的中存在一些高價(jià)值、高需求的零部件，以及某些對環(huán)境或人體有危害的零部件，這些零部件均需盡早拆除，以提高拆卸收益并降低拆卸危害性。故拆卸線平衡問題是一項(xiàng)復(fù)雜的多目標(biāo)優(yōu)化問題。

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

針對多目標(biāo)斗鏈?zhǔn)交炝鞑鹦毒€平衡特性建立其數(shù)學(xué)模型，以尋求可行拆卸序列，同時(shí)滿足最小化作業(yè)區(qū)間負(fù)荷均衡性、盡早拆除高需求和有危害零部件的要求。

(1)除1.1節(jié)已解釋的符號外，數(shù)學(xué)模型中還用到以下符號，其含義分別為：

M為斗鏈?zhǔn)讲鹦毒€上作業(yè)工人數(shù)；

m為作業(yè)工人的編號，即作業(yè)區(qū)間編號，m∈{1, 2,…,M}；

N為拆卸產(chǎn)品需要進(jìn)行拆卸的任務(wù)數(shù)；

n為拆卸任務(wù)編號，n∈{1, 2,…,N}；

xmn為拆卸任務(wù)與作業(yè)區(qū)間的關(guān)系；

ln為拆卸任務(wù)n在拆卸序列中的位置；

vm為第m個(gè)工人的作業(yè)速度；

wm為第m個(gè)工人的返回速度；

a,b為作業(yè)區(qū)間編號，a,b∈{1, 2,…,M}；

i,j為拆卸任務(wù)編號，i,j∈{1, 2,…,N}；

yij為任務(wù)i,j間優(yōu)先關(guān)系值，可以構(gòu)造拆卸任務(wù)間優(yōu)先關(guān)系矩陣Y，其中Y=[yij]N×N。

(2)數(shù)學(xué)模型中的決策變量：

(3)數(shù)學(xué)模型中的輔助變量：

(4)目標(biāo)函數(shù)和約束條件如下：

(12)

(13)

(14)

?m∈{1,2,…,M}；

(15)

(16)

(17)

xmn∈{0,1},?m∈{1,2,…,M},

n∈{1,2,…,N}。

(18)

目標(biāo)函數(shù)中：式(12)表示最小化作業(yè)區(qū)間負(fù)荷均衡指標(biāo)；式(13)表示最小化需求指標(biāo)；式(14)表示最小化危害指標(biāo)。約束條件中：式(15)表示第m個(gè)工人的理論作業(yè)時(shí)間；式(16)表示每一項(xiàng)任務(wù)都必須拆卸，且只能分配到一個(gè)作業(yè)區(qū)間進(jìn)行拆卸；式(17)表示拆卸順序必須滿足任務(wù)間優(yōu)先關(guān)系約束；式(18)表示任務(wù)分配變量是0-1型變量。

2 Pareto花朵授粉算法

花朵授粉算法(Flower Pollination Algorithm, FAP)是模擬花朵的自花與異花兩種授粉特性而提出的，具有較好的全局搜索能力[21]。且該算法結(jié)構(gòu)簡單，所需設(shè)置的參數(shù)少，并已成功應(yīng)用于拆卸序列規(guī)劃等離散組合優(yōu)化問題中。鑒于斗鏈?zhǔn)交炝鞑鹦毒€平衡問題的復(fù)雜性和求解難度，設(shè)計(jì)適用于求解該問題的高效方法，主要包括花朵授粉算法中連續(xù)性操作的離散化，以及Pareto解集和多目標(biāo)處理方法。

2.1 編碼

編碼是根據(jù)拆卸線平衡問題的特點(diǎn)構(gòu)造可行拆卸序列，現(xiàn)有文獻(xiàn)中多為隨機(jī)編碼方式，但受問題約束條件的限制，隨機(jī)編碼極易產(chǎn)生不可行解，這將對算法的效率產(chǎn)生不利影響，為此，本文采用基于優(yōu)先關(guān)系矩陣挑選任務(wù)的方式進(jìn)行編碼，確保編碼結(jié)果均為可行解。

根據(jù)拆卸任務(wù)間的物理約束與幾何約束建立拆卸任務(wù)間的優(yōu)先關(guān)系圖，如圖1所示，圓圈內(nèi)數(shù)字代表拆卸任務(wù)，箭頭連接的兩任務(wù)間存在拆卸順序先后約束。根據(jù)優(yōu)先關(guān)系圖可以構(gòu)建拆卸任務(wù)間的優(yōu)先關(guān)系矩陣Y，其維度與拆卸任務(wù)相同，矩陣中的元素為0-1變量，用1.1節(jié)中的yij表示，圖1中任務(wù)的優(yōu)先關(guān)系矩陣如圖2所示。

基于優(yōu)先關(guān)系矩陣的編碼需要逐個(gè)挑選任務(wù)，矩陣中所在列全為0的未分配任務(wù)即為候選任務(wù)。當(dāng)存在多個(gè)候選任務(wù)時(shí)，為得到較優(yōu)的初始序列，結(jié)合1.1節(jié)中的問題特征，建立如下3種啟發(fā)式規(guī)則。

規(guī)則1優(yōu)先挑選使得作業(yè)區(qū)間的實(shí)際作業(yè)時(shí)間與理論作業(yè)時(shí)間之差最小的任務(wù)，其數(shù)學(xué)表達(dá)式為

(19)

規(guī)則2優(yōu)先挑選需求量最高的任務(wù)，從而使得需求指標(biāo)f2最小，其表達(dá)式為

(20)

規(guī)則3優(yōu)先挑選危害性最大的任務(wù)，從而使得危害性指標(biāo)f3最小，其表達(dá)式為

(21)

在編碼過程中，候選任務(wù)很難同時(shí)滿足3種啟發(fā)式規(guī)則，而三種啟發(fā)式規(guī)則又與3個(gè)目標(biāo)函數(shù)相對應(yīng)，優(yōu)化過程中不設(shè)置各目標(biāo)的優(yōu)化順序，若存在多個(gè)滿足各啟發(fā)式規(guī)則的任務(wù)，則隨機(jī)挑選某一任務(wù)，從而確保了初始解的多樣性。

2.2 解碼

解碼過程是將編碼得到的拆卸序列中的任務(wù)分配到各個(gè)工作區(qū)間，并確定各個(gè)工作區(qū)間內(nèi)任務(wù)的先后順序。解碼時(shí)遵循工作區(qū)間作業(yè)時(shí)間與理論作業(yè)時(shí)間之差最小化原則，其示意圖如圖3所示。圖中：n表示任務(wù)編號，m表示工作區(qū)間編號，TR表示工作區(qū)間理論剩余時(shí)間，Sm表示已分配到工作區(qū)間m的任務(wù)集。

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

在多目標(biāo)問題中是通過解之間的支配關(guān)系來確定解的優(yōu)劣，對于任意的兩個(gè)可行解X1、X2，若X1和X2滿足式(22)，則稱X1Pareto占優(yōu)于X2，或X1支配X2，記為X1X2?？尚薪釾1與X2之間存在支配、被支配以及互不支配3種關(guān)系。

(22)

在多目標(biāo)問題中，將所得的所有可行解進(jìn)行支配關(guān)系比較，篩選出最終的互不支配解，即為Pareto非劣解。一般地，多目標(biāo)的非劣解不止一個(gè)，而是由多個(gè)非劣解組成的Pareto非劣解集合，非劣解集對應(yīng)的目標(biāo)空間稱為Pareto前沿。

將非劣解存儲(chǔ)于外部檔案中，算法在迭代過程中，需要將每次獲得的新解與外部檔案中的非劣解進(jìn)行比較，添加支配解和互不支配解，刪除被支配解，從而實(shí)現(xiàn)外部檔案的更新。

借鑒帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)擁擠距離機(jī)制[22]進(jìn)行非劣解的評價(jià)篩選，先將每個(gè)子目標(biāo)函數(shù)值按升序進(jìn)行排列，然后計(jì)算子擁擠距離，每個(gè)非劣解的擁擠距離為所有子擁擠距離之和，其表達(dá)式為

(23)

2.4 Pareto解集評價(jià)

支配關(guān)系反映的是非劣解之間的優(yōu)劣關(guān)系，無法對Pareto解集進(jìn)行評價(jià)，為此，本文引入Hypervolume指標(biāo)[23]對算法迭代過程中求得的Pareto解集進(jìn)行評價(jià)。Hypervolume指標(biāo)所求得的所有非劣解到參考解之間的超體積。在算法迭代過程中，隨著非劣解不斷逼近真實(shí)Pareto前沿，Hypervolume值將不斷增大，當(dāng)算法收斂時(shí)，即所有非劣解達(dá)到真實(shí)Pareto前沿時(shí)，Hypervolume值最大。

如圖4所示，在求最大值的3個(gè)目標(biāo)的目標(biāo)空間中，非劣解集為{S1,S2,S3,S4,S5}，參考點(diǎn)為原點(diǎn)O，各非劣解到O的有效超體積分別為V1,V2,V3,V4,V5，則Hypervolume=V1+V2+V3+V4+V5。Hypervolume值不僅可以反映算法迭代過程中解的質(zhì)量變化情況，還可以用于比較不同算法所得非劣解的性能。

2.5 離散花朵授粉算法

花朵授粉算法包括異花授粉和自花授粉兩種操作。異花授粉主要通過鳥類和昆蟲等具有萊維飛行特征的生物進(jìn)行傳粉，表現(xiàn)為全局搜索方式；自花授粉方式是花粉在自身花朵上進(jìn)行傳播，表現(xiàn)為局部尋優(yōu)方式。通過概率Ps來決定采用全局授粉方式或局部授粉方式。

在花朵授粉算法中，設(shè)花朵種群規(guī)模為Npop，算法最大迭代次數(shù)為gmax，對任一的花朵i(i=1, 2,…,Npop)在第g(g=1, 2,…,gmax)次迭代時(shí)，異花授粉表達(dá)式為

(24)

(25)

式中：λ為常數(shù)，且λ=1.5，Γ(λ)是Gamma函數(shù)，s由式(26)得到：

(26)

式中：

(27)

自花授粉表達(dá)式為

(28)

在拆卸線平衡問題中，將每一花朵定義為一個(gè)可行拆卸序列，因拆卸線平衡問題是離散問題，上式中的連續(xù)性花朵授粉方式不再適用，且授粉后的花朵需要滿足拆卸優(yōu)先關(guān)系，為此需要設(shè)計(jì)滿足問題要求的離散花朵授粉行為。參考離散粒子群算法的操作方式，對異花授粉和自花授粉方式進(jìn)行離散化，離散后的兩授粉表達(dá)式分別為

(29)

(30)

式中：Θ表示兩序列中對應(yīng)位置處的任務(wù)不同時(shí)的交換操作，其中一個(gè)任務(wù)通過執(zhí)行交換操作，趨近于另外一個(gè)任務(wù)，且交換任務(wù)時(shí)需要滿足優(yōu)先關(guān)系約束，若序列中對應(yīng)位置處的任務(wù)相同，則無需執(zhí)行交換操作；‖·‖表示每個(gè)相異任務(wù)可執(zhí)行交換的次數(shù)；A⊕〈B〉表示對序列A執(zhí)行B中的交換對。

離散過程中，γL(λ)以及ε與交換總次數(shù)的乘積向上取整，當(dāng)L(λ)<0時(shí)不執(zhí)行交換操作。交換操作時(shí)，如序列X1與X2中第n處任務(wù)不同，X2中第n處的任務(wù)i的最近緊前任務(wù)和最近緊后任務(wù)之間的任務(wù)集合為S1，且S1中任務(wù)j的最近緊前任務(wù)和最近緊后任務(wù)之間的任務(wù)集合為S2，若S1∩S2≠?，則X2中任務(wù)i和任務(wù)j可以交換，i和j為一對可行交換對，‖X1ΘX2‖即為序列X1與X2之間的所有可行交換對數(shù)，交換對數(shù)乘以系數(shù)γ做向上取整處理，即〈γ‖X1ΘX2‖〉=γ‖X1ΘX2‖?。

2.6 算法流程

將離散花朵授粉算法與多目標(biāo)優(yōu)化方法相結(jié)合，構(gòu)造Pareto花朵授粉算法，用于求解多目標(biāo)斗鏈?zhǔn)交炝鞑鹦毒€平衡問題。所提算法的具體流程如下：

步驟1參數(shù)初始化，設(shè)置種群規(guī)模Npop，算法迭代次數(shù)gmax，花朵授粉方式轉(zhuǎn)換概率PS，外部檔案Q=?。

步驟2種群初始化，隨機(jī)生成初始可行花朵，并計(jì)算每個(gè)花朵的適應(yīng)度值F=[f1,f2,f3]。

步驟3根據(jù)Pareto支配關(guān)系篩選非劣解，并將非劣解集存儲(chǔ)于外部檔案Q中。

步驟5循環(huán)迭代開始，令當(dāng)前迭代次數(shù)g=1。

步驟6對每個(gè)花朵執(zhí)行授粉行為，令當(dāng)前花朵編號i=1。

步驟10若i

步驟11根據(jù)Pareto支配關(guān)系更新外部檔案Q。

步驟12更新種群，將外部檔案中非劣解作為種群。計(jì)算外部檔案中非劣解個(gè)數(shù)NQ，若NQ>Npop，則挑選擁擠距離較大的Npop個(gè)非劣解作為種群，否則隨機(jī)生成新的花朵添加到種群中以維持種群規(guī)模。

步驟13若g

步驟14尋優(yōu)結(jié)束，輸出外部檔案中的Pareto解集及其適應(yīng)度函數(shù)。

3 算法驗(yàn)證

為驗(yàn)證所提算法的有效性，針對不同規(guī)模的拆卸線平衡問題進(jìn)行測試。算法實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Inter Core i3-2100 M, 3.10 GHz, 2 GB內(nèi)存，在Windows 7系統(tǒng)下采用MATLAB R2017b軟件開發(fā)了算法的實(shí)驗(yàn)程序?，F(xiàn)有文獻(xiàn)中尚未發(fā)現(xiàn)有關(guān)斗鏈?zhǔn)交炝鞑鹦毒€實(shí)例報(bào)道，故只能采用其他類型的拆卸線實(shí)例進(jìn)行算法驗(yàn)證。針對不同類型的拆卸線算例，拆卸線平衡問題的本質(zhì)特征并未改變，只需根據(jù)問題特征改變算法的編碼和解碼操作，而離散花朵授粉算法的授粉行為方式不變，故可以采用其他類型的拆卸線實(shí)例對所提算法的求解性能進(jìn)行驗(yàn)證。

3.1 完全拆卸線算例

現(xiàn)有文獻(xiàn)中求解完全拆卸線算例主要包括25項(xiàng)拆卸任務(wù)的某型號手機(jī)拆卸線(P25)和含52項(xiàng)拆卸任務(wù)的電子套結(jié)機(jī)機(jī)殼拆卸線(P52)。P25的目標(biāo)函數(shù)包括最小化工作站數(shù)F1、負(fù)荷均衡指標(biāo)F2、需求指標(biāo)F3和危害指標(biāo)F4；P52的目標(biāo)函數(shù)包括閑置率Fidle、平滑率Fsmooth和拆卸成本Fcost。采用本文所提Pareto離散花朵授粉算法對兩算例進(jìn)行求解，并與現(xiàn)有文獻(xiàn)中的算法結(jié)果進(jìn)行對比。

現(xiàn)有文獻(xiàn)中求解P25的多目標(biāo)算法包括人工魚群算法(Artificial Fish Swarm Algorithm, AFSA)[16]、遺傳模擬退火(Genetic Algorithm and Simulated Annealing, GASA)算法[17]、離散果蠅優(yōu)化算法(Discrete Fruit Fly Optimization Algorithm, DFOA)[18]、螢火蟲算法(Firefly Algorithm, FA)[19]、離散布谷鳥搜索(Discrete Cuckoo Search, DCS)算法[24]、蝙蝠算法(Bat Algorithm, BA)[25]。多目標(biāo)算法的求解結(jié)果如表1所示，表中n表示算法所得非劣解的個(gè)數(shù)。本文FPA的參數(shù)設(shè)置為：Npop=50，gmax=200，PS=0.8。因問題規(guī)模較小，保留求解過程中外部檔案中的所有非劣解，共求解30次，平均求解時(shí)間為18.97 s。在30次求解結(jié)果中共有25次均求得36個(gè)相同非劣解，且該非劣解集為30次求解結(jié)果中的最好解，所有非劣解的目標(biāo)函數(shù)值如表1所示，具體平衡方案見附錄中表1。

表1 現(xiàn)有文獻(xiàn)多目標(biāo)求解P25結(jié)果

續(xù)表1

續(xù)表1

由表1可知， AFSA、GASA、DFOA、FA、DCS、BA、FPA等多目標(biāo)算法能夠求得多個(gè)非劣解，每個(gè)平衡方案各有側(cè)重點(diǎn)，從而驗(yàn)證了多目標(biāo)算法的有效性。分析表1中數(shù)據(jù)可知，AFSA、GASA、DFOA、FA、DCS、BA求得非劣解的數(shù)目有限，而FPA一次能夠求得36個(gè)非劣解，且FPA的非劣解集中包含了其他多目標(biāo)算法的最好非劣解，F(xiàn)PA的非劣解更接近問題的真實(shí)Pareto前沿，表明FPA的尋優(yōu)能力更強(qiáng)。FPA求解P25的結(jié)果為現(xiàn)有文獻(xiàn)中已知的最好非劣解集，因該問題的真實(shí)Pareto前沿未知，在針對該問題的后續(xù)研究中，可將其作為其他方法求解性能的參考值。

在求解P52時(shí)，現(xiàn)有文獻(xiàn)中的求解方法包括粒子群優(yōu)化(Particle Swarm Optimization, PSO)[14]、AFSA[16]、GASA[17]、DFOA[18]、改進(jìn)粒子群優(yōu)化(Improved PSO, IPSO)算法[26]。采用本文所提FPA對P52進(jìn)行求解，參數(shù)設(shè)置為：Npop=50，gmax=200，PS=0.8。算法共運(yùn)行20次，平均運(yùn)行時(shí)間為142.81 s，取20次結(jié)果中的較優(yōu)解，共求得8個(gè)非劣解，具體平衡方案及其目標(biāo)函數(shù)值見附錄中表2。所有非劣解在目標(biāo)空間中的分布與其他5種多目標(biāo)算法結(jié)果對比，如圖5所示。除了ACO中4個(gè)非劣解的Fidle=0.175 7外，其他所有算法的非劣解的Fidle=0.057 9，故只選取ACO中Fidle=0.057 9的較優(yōu)解進(jìn)行對比。為便于對比各非劣解的優(yōu)劣，圖5給出了所有非劣解在目標(biāo)Fsmooth與Fcost上的對比情況，并對所有非劣解再次進(jìn)行Pareto篩選，所得Pareto前沿已在圖5中進(jìn)行了標(biāo)示。新的Pareto前沿共包含8個(gè)非劣解，其中7個(gè)非劣解來自FPA，另外一個(gè)非劣解來自DFOA，由此可知FPA的求解性能優(yōu)于其他7種多目標(biāo)算法。

在單目標(biāo)極值探索方面，F(xiàn)PA的非劣解在目標(biāo)Fsmooth與Fcost上均有所提高，F(xiàn)smooth最優(yōu)值為0.999 5，F(xiàn)cost的最優(yōu)值為125.502，均為現(xiàn)有文獻(xiàn)中的已知最好結(jié)果。綜上分析可知，在求解完全拆卸的小規(guī)模問題(P25)和大規(guī)模問題(P52)中，本文所提FPA均表現(xiàn)出較優(yōu)的求解性能。

3.2 部分拆卸線算例

3.1節(jié)中的兩個(gè)算例均為完全拆卸線平衡問題，現(xiàn)有研究中已將拆卸線平衡問題拓展到了部分拆卸線平衡問題，因部分拆卸線平衡問題的可行域更大，故其求解更加復(fù)雜。文獻(xiàn)[24，26]分別采用IPSO和DCS對含55項(xiàng)拆卸任務(wù)的不完全拆卸線算例(P55)進(jìn)行求解，分別得到3個(gè)和9個(gè)平衡方案。該算例包括4個(gè)目標(biāo)函數(shù)，分別為拆卸任務(wù)數(shù)F1、工作站數(shù)F2、空閑均衡指標(biāo)F3、拆卸成本F4，TC為實(shí)際節(jié)拍。采用本文所提FPA對該算例進(jìn)行求解，設(shè)Npop=50，gmax=200，PS=0.8，共求得5個(gè)平衡方案，如表2所示。

表2 FPA求解P55結(jié)果

將FPA與IPSO、DCS計(jì)算所得的非劣解分別在4個(gè)目標(biāo)及TC上進(jìn)行對比，分別對比最小值(min)、均值(avg)和最大值(max)，如表3所示。由表3對比可知，F(xiàn)PA方案在4個(gè)目標(biāo)和TC上的最小值、平均值、最大值均優(yōu)于IPSO與DCS的方案。FPA取得最小拆卸任務(wù)數(shù)34；工作站數(shù)和DCS相同，均為3個(gè)工作站；空閑負(fù)荷均衡指標(biāo)最小值都為0，但FPA的均值要小于DCS的均值；拆卸成本方面，F(xiàn)PA能達(dá)到最小拆卸成本3.519，其均值比IPSO與DCS分別提高了33.74%和7.84%；節(jié)拍也相應(yīng)減小，F(xiàn)PA最小節(jié)拍為135，比IPSO、DCS最小節(jié)拍分別減小10和7，從而驗(yàn)證了FPA比IPSO、DCS更具優(yōu)越性。

表3 FPA與IPSO、DCS求解P55結(jié)果對比

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

課題組在某拆卸企業(yè)現(xiàn)場調(diào)研，得到廢舊電視機(jī)相關(guān)拆卸案例數(shù)據(jù)。待拆卸的電視機(jī)有3種不同品種，共含27個(gè)零部件，各品種電視機(jī)的年拆卸量分別為Q1=30 000，Q2=40 000，Q3=30 000，則最小拆卸品種比例為ω1∶ω2∶ω3=3∶4∶3，具體拆卸信息如表4所示，根據(jù)各品種零部件間優(yōu)先關(guān)系繪制如圖6所示的綜合拆卸優(yōu)先關(guān)系圖。建立3種品種的電視機(jī)混流拆卸線，采用斗鏈生產(chǎn)組織方式，該生產(chǎn)線上的相關(guān)參數(shù)分別為Wy=42，Sw=5，Hs=8，ηL=0.9。設(shè)該拆卸線上工人數(shù)為3人，作業(yè)速度分別為v1=1.1，v2=1.2，v3=1.3，返回速度分別為w1=11，w2=12，w3=13，經(jīng)計(jì)算工人數(shù)及其作業(yè)速度滿足生產(chǎn)要求。

表4 電視機(jī)零部件信息

續(xù)表4

采用Pareto花朵授粉算法對實(shí)例進(jìn)行求解，兼顧求解質(zhì)量與求解效率，將算法參數(shù)設(shè)定為：Npop=50，gmax=100，PS=0.8，計(jì)算Hypervolume值的參考點(diǎn)設(shè)為(50, 2 000, 100)。算法共運(yùn)行10次，平均運(yùn)算時(shí)間為114.28 s，取其中一次較優(yōu)結(jié)果，其Hypervolume值隨迭代次數(shù)的變化如圖7所示，共求得90個(gè)非劣解，非劣解的Pareto前沿如圖8所示。

表5 拆卸平衡方案

在3種方案中：方案S1取得目標(biāo)f1上的最小值0，且所有f1= 0的方案在目標(biāo)f2上相差不大，而S1的目標(biāo)f3最小，此時(shí)f3= 60；方案S2在所有方案中的目標(biāo)f2上取得最小值1 186.8，若要求需求指標(biāo)最小，可以選擇方案S2；方案S3的目標(biāo)f3為最小值46，取得f3= 46的方案共有4個(gè)，而方案S2能同時(shí)兼顧目標(biāo)f1和f2，使得兩目標(biāo)不至于過大，故方案S3為要求危害指標(biāo)最小的折中方案。決策者除了考慮單目標(biāo)要求外，也可以同時(shí)兼顧兩個(gè)目標(biāo)進(jìn)行方案選擇，目標(biāo)側(cè)重點(diǎn)不同，方案選擇也不同，所得90種平衡方案豐富了決策者的決策空間，為斗鏈?zhǔn)交炝鞑鹦毒€的作業(yè)任務(wù)安排提供了參考。

5 結(jié)束語

針對傳統(tǒng)拆卸線難以實(shí)現(xiàn)作業(yè)均衡這一難題，將具有自平衡性的斗鏈生產(chǎn)組織方式應(yīng)用于拆卸線中，并結(jié)合待拆卸產(chǎn)品的多樣性與結(jié)構(gòu)相似性，建立斗鏈生產(chǎn)組織方式下的多目標(biāo)混流拆卸線平衡問題數(shù)學(xué)模型，進(jìn)而設(shè)計(jì)了Pareto離散花朵授粉算法用于求解該問題。在所設(shè)計(jì)算法中，采用結(jié)合問題特征的啟發(fā)式方法來構(gòu)造初始可行解，并提出了多目標(biāo)優(yōu)化策略。將花朵授粉算法離散化，設(shè)計(jì)了基于萊維飛行的離散異花授粉操作和隨機(jī)離散自花授粉操作，增強(qiáng)了算法的全局搜索能力和局部搜索能力，同時(shí)確保了操作結(jié)果的可行性。

在求解25項(xiàng)拆卸任務(wù)算例中，所提算法得到現(xiàn)有研究中已知最優(yōu)的36個(gè)非劣解；在求解52項(xiàng)拆卸任務(wù)算例中，所得結(jié)果進(jìn)一步逼近真實(shí)Pareto前沿；將所提算法的驗(yàn)證拓展到部分拆卸線平衡問題中，其性能優(yōu)于已知多目標(biāo)改進(jìn)粒子群算法和多目標(biāo)布谷鳥算法。并將所設(shè)計(jì)模型和所提算法應(yīng)求解混合品種電視機(jī)拆卸線平衡問題中，得到90個(gè)非劣解，驗(yàn)證了斗鏈生產(chǎn)組織方式下拆卸線的平衡，為決策者提供了多種可選平衡方案。

后續(xù)研究可以考慮將斗鏈生產(chǎn)組織方式應(yīng)用于其他復(fù)雜生產(chǎn)線中，積極探索更加高效策略來提升方法的求解性能，擴(kuò)大斗鏈理論研究的實(shí)際應(yīng)用價(jià)值。