肖閃麗，王宇嘉，于 慧

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

在實(shí)際生產(chǎn)中拆卸線平衡問(wèn)題(Disassembly Line Balancing Problem, DLBP)需要同時(shí)優(yōu)化多個(gè)相互牽制甚至互相矛盾的目標(biāo)，是一類典型的NP組合優(yōu)化問(wèn)題。Gungor等人[1]首先提出了DLBP，并采用了一種啟發(fā)式算法，但該方法的缺點(diǎn)是求解效果具有不確定性。Altekin和Llambert等人[2-3]利用啟發(fā)式算法求解基于拆卸利潤(rùn)最優(yōu)的DLBP。文獻(xiàn)[4]提出了基于線性加權(quán)的多目標(biāo)蟻群算法, 但其實(shí)質(zhì)仍是單目標(biāo)優(yōu)化。文獻(xiàn)[5～6]分別運(yùn)用改進(jìn)的蟻群算法和遺傳算法求解多目標(biāo)DLBP，但在實(shí)際求解過(guò)程中卻把多目標(biāo)問(wèn)題轉(zhuǎn)化成了具有優(yōu)先順序的單目標(biāo)問(wèn)題。Kongar等人[7]利用遺傳算法，考慮了多個(gè)目標(biāo)來(lái)實(shí)現(xiàn)DLBP，但其針對(duì)大規(guī)模問(wèn)題的求解性能還有待提升。丁力平等人[8]提出Pareto蟻群算法求解拆卸線的多目標(biāo)問(wèn)題，其目標(biāo)為平均閑置率、負(fù)荷均衡指標(biāo)和拆卸成本，但在解決復(fù)雜的DLBP上可能會(huì)出現(xiàn)早熟現(xiàn)象。Kalayci等人[9-11]提出了基于鄰居變異操作的粒子群優(yōu)化算法、蜂群算法和蟻群算法，但其沒(méi)有考慮算法自身存在易陷入局部最優(yōu)的問(wèn)題。

粒子群算法憑借實(shí)現(xiàn)容易、控制參數(shù)少以及收斂速度快的特點(diǎn)[12]，目前廣泛應(yīng)用在工業(yè)生產(chǎn)上。本文根據(jù)生產(chǎn)實(shí)際的需要構(gòu)建了DLBP數(shù)學(xué)模型，并采用基于維度學(xué)習(xí)的多目標(biāo)粒子群算法(DL-MOPSO)對(duì)其進(jìn)行優(yōu)化求解。

1 多目標(biāo)拆卸線平衡問(wèn)題的數(shù)學(xué)模型

1.1 拆卸線平衡問(wèn)題描述

1.2 拆卸線平衡問(wèn)題數(shù)學(xué)模型

(1)盡可能減小工作站的數(shù)量

minf1=m

(2)最小化工作站的空閑時(shí)間

(3)最小化需求指數(shù)：根據(jù)市場(chǎng)需要對(duì)零件進(jìn)行拆卸，減少庫(kù)存壓力

其中，PSi表示在拆卸序列中第i個(gè)零件；dPSi代表任務(wù)為PSi的零部件的需求量；N為自然數(shù)集；

(4)盡早拆除危害零部件：可減少危害，節(jié)約成本。

綜上所述，本文對(duì)拆卸線平衡問(wèn)題優(yōu)化的數(shù)學(xué)模型如式(1)所示

minf=min{f1,f2,f3,f4}

(1)

約束條件如式(2)所示

(2-a)

(2-b)

(2-c)

其中，ti為第i個(gè)任務(wù)的作業(yè)時(shí)間；式(2-a)表示每個(gè)任務(wù)必須要分配給工作站，且只能分配給一個(gè)工作站；式(2-b)表示工作站數(shù)的取值范圍；m*表示所需的最小工作站數(shù)；式(2-c)表示任務(wù)i分配給工作站j時(shí)，其之前的任務(wù)都已經(jīng)分配給j之前的工作站，即保證在滿足拆卸任務(wù)優(yōu)先關(guān)系的情況下分配作業(yè)任務(wù)；IP表示在任務(wù)i之前的集合。

2 動(dòng)態(tài)鄰居維度學(xué)習(xí)的多目標(biāo)粒子群算法

2.1 粒子的編碼與解碼

拆卸線平衡問(wèn)題是離散優(yōu)化問(wèn)題，與連續(xù)優(yōu)化問(wèn)題不同，在求解之前要確定粒子的編碼與解碼方案。本文利用帶優(yōu)先權(quán)的零入度拓?fù)渑判蚍椒ń⒘Ｗ游恢门c拆卸序列之間的映射關(guān)系[13]。

以7個(gè)零部件的拆卸為例，其用優(yōu)先圖表示的拆卸任務(wù)之間的先后關(guān)系如圖1所示，其拆卸優(yōu)先權(quán)如表1所示。

圖1 7個(gè)零部件拆卸優(yōu)先順序

粒子維度1234567優(yōu)先權(quán)0.20.30.40.10.50.50.6

由圖1可得, 開(kāi)始只有零件O1的入度為0，故選擇O1為拆卸序列的第一個(gè)，接下來(lái)零件O2和O4的入度為0，但零件O2的優(yōu)先權(quán)大于O4的優(yōu)先權(quán)，因此下一個(gè)可用來(lái)拆卸的零件為O2。重復(fù)上述過(guò)程，直到零件集為空集。該粒子經(jīng)解碼后得到的可行的拆卸序列(Feasible disassembly Sequence，F(xiàn)OS)為[1，2，5，6，3，4，7]。

2.2 動(dòng)態(tài)鄰居拓?fù)浣Y(jié)構(gòu)

Suganthan等[14]提出了將環(huán)形結(jié)構(gòu)與星形結(jié)構(gòu)結(jié)合起來(lái)的動(dòng)態(tài)鄰居構(gòu)建策略來(lái)減小種群陷入局部最優(yōu)的概率。在粒子鄰居數(shù)增長(zhǎng)模型中，當(dāng)任意兩個(gè)粒子滿足式(3)時(shí)，認(rèn)定上述兩粒子為鄰居關(guān)系

(3)

其中，xi和xbin為種群中任意兩粒子；t為算法當(dāng)前迭代次數(shù)；tmax為算法最大迭代次數(shù)；dmax是任意兩個(gè)粒子間的最大距離。

2.3 構(gòu)建最優(yōu)維度粒子

為平衡學(xué)習(xí)過(guò)程中的探索性能和開(kāi)發(fā)性能[15]，在DL-MOPSO算法中，選取每個(gè)粒子鄰居中最優(yōu)維度。

粒子i的每一維學(xué)習(xí)對(duì)象根據(jù)式(4)選取，構(gòu)成的新學(xué)習(xí)個(gè)體為

(4)

2.4 粒子的速度更新

為提高種群的多樣性，本文按如下方法對(duì)粒子進(jìn)行更新：

步驟 1 隨機(jī)選出粒子i的p(j∈p)個(gè)維數(shù)，根據(jù)式(5-a)使粒子i向gbest學(xué)習(xí)

vi,j=wvi,j+rand()(gbestj-xi,j)

(5-a)

步驟 2 再隨機(jī)選出粒子i的q(j∈q)個(gè)維數(shù)，根據(jù)式(5-b)使粒子 向鄰居中最優(yōu)維度組成的新個(gè)體pbestbin學(xué)習(xí)

vi,j=wvi,j+rand()(pbestbin(j)-xi,j)

(5-b)

步驟 3 剩余維數(shù)D-p-q(j∈D-p-q)根據(jù)式(5-c)使粒子i向自身的pbest學(xué)習(xí)

vi,j=wvi,j+rand()(pbesti,j-xi,j)

(5-c)

其中，p和q分別由精英概率pm和學(xué)習(xí)概率pc決定；pc決定了粒子的某一維向pbest或pbestbin的學(xué)習(xí)能力；pm決定了粒子的某一維向gbest的學(xué)習(xí)能力。

2.5 學(xué)習(xí)樣本的選取和隨機(jī)向?qū)W(xué)習(xí)策略

2.5.1 全局最優(yōu)位置的選取

本文根據(jù)密集距離distancei[16]的大小選擇全局最優(yōu)解，其計(jì)算如式(6)所示，擁有密集距離較大的粒子將作為全局最優(yōu)粒子

(6)

2.5.2 個(gè)體最優(yōu)位置的更新

本文提出一種隨機(jī)向?qū)W(xué)習(xí)策略來(lái)更新pbest，即當(dāng)一個(gè)粒子連續(xù)T代個(gè)體最優(yōu)位置沒(méi)有得到提升時(shí)，隨機(jī)產(chǎn)生若干個(gè)粒子與pbest進(jìn)行支配性比較，在支配的粒子中隨機(jī)選擇一個(gè)粒子替代pbest；當(dāng)條件不滿足時(shí)，隨機(jī)選擇一個(gè)其它粒子的pbest進(jìn)行更新。

3 面向拆卸線平衡問(wèn)題的多目標(biāo)粒子群優(yōu)化

步驟 1 算法初始化，包括：種群規(guī)模Num；外部檔案規(guī)模NP；粒子位置x和速度v；搜索空間維數(shù)D(實(shí)際為拆卸產(chǎn)品的零件數(shù)量)；慣性權(quán)值w；粒子全局最優(yōu)位置gbest；個(gè)體最優(yōu)歷史位置pbest；粒子最優(yōu)維度個(gè)體pbestbin；學(xué)習(xí)概率pc；精英概率pm；隨機(jī)向?qū)W(xué)習(xí)持續(xù)代數(shù)閾值T；最大迭代次數(shù)tmax；目標(biāo)向量f；拆卸任務(wù)偏序集Z；工作站節(jié)拍CT；

步驟 2 對(duì)粒子進(jìn)行解碼操作，根據(jù)優(yōu)先關(guān)系確定外部檔案NP中的粒子；

步驟 3 從外部檔案中隨機(jī)選取兩個(gè)粒子，根據(jù)式(6)計(jì)算密集距離確定所對(duì)應(yīng)粒子的全局最優(yōu)位置gbest；

步驟 4 根據(jù)式(3)確定粒子的鄰居個(gè)數(shù)，利用式(4)確定粒子每一維學(xué)習(xí)樣本；

步驟 5 采用隨機(jī)向?qū)W(xué)習(xí)策略更新粒子個(gè)體最優(yōu)歷史位置pbest；

步驟 6 根據(jù)式(5-a)～(5-c)更新粒子的速度v；

步驟 7 計(jì)算每個(gè)FOS狀態(tài)下的適應(yīng)度函數(shù)，并對(duì)外部檔案文件NP進(jìn)行更新和維護(hù)；

步驟 8 如果終止條件成立，則停止搜索，對(duì)非劣解進(jìn)行解碼，輸出非劣解和非劣解所對(duì)應(yīng)的目標(biāo)值，否則轉(zhuǎn)到步驟 3；

步驟 9 對(duì)得到的最優(yōu)拆卸序列完成工作站的分配。

4 實(shí)驗(yàn)分析

實(shí)例1 以零件數(shù)目為10的部件拆卸為例，零部件優(yōu)先順序如圖2所示，其拆卸時(shí)間、需求和危害等信息見(jiàn)文獻(xiàn)[17]，工作節(jié)拍CT為40s。

圖2 零部件拆卸優(yōu)先順序

本文算法與文獻(xiàn)[5]、文獻(xiàn)[9]和文獻(xiàn)[18]的優(yōu)化結(jié)果進(jìn)行比較，如表2所示，本文的優(yōu)化結(jié)果在需求指數(shù)f3上遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)[5]；相對(duì)于文獻(xiàn)[9]和文獻(xiàn)[18]，本文所得優(yōu)化解與其互不支配。由上可得，本文所提算法的優(yōu)勢(shì)在于不僅得到了優(yōu)于或與現(xiàn)有文獻(xiàn)一致的拆卸序列，而且在考慮了生產(chǎn)實(shí)際情況后，為決策者提供了更多的備選拆卸方案，尤其在對(duì)產(chǎn)品不同需求方面為決策者提供了有利的參考。

表2 零件數(shù)目為10的優(yōu)化結(jié)果

實(shí)例2 以零件數(shù)目為25的部件拆卸為例，其零部件優(yōu)先順序如圖3所示，拆卸時(shí)間、需求和危害等信息見(jiàn)文獻(xiàn)[19]，工作節(jié)拍CT為18s。

表3列出了現(xiàn)有算法在DLBP上所優(yōu)化的經(jīng)典解，本文所得優(yōu)化解如圖4所示。從表3中可以看出，文獻(xiàn)[5]在該問(wèn)題上不能得到較好結(jié)果，說(shuō)明隨著拆卸規(guī)模的增大，其求解精度下降。本文算法所得優(yōu)化解(f1=9,f2=9,f3=806,f4=74)相比與文獻(xiàn)[7]、文獻(xiàn)[9]和文獻(xiàn)[18]，在工作站數(shù)為理論值且空閑時(shí)間f2保持一致的前提下，本文算法所求得的需求指數(shù)f3和盡早拆除危害零部件f4均得到了不同程度的改善，尤其需求指數(shù)f3相對(duì)來(lái)說(shuō)有了大幅度下降。根據(jù)支配解的定義，文獻(xiàn)[18]的優(yōu)化結(jié)果支配文獻(xiàn)[7]和文獻(xiàn)[9], 而本文得到的解在每一個(gè)目標(biāo)函數(shù)上均優(yōu)于文獻(xiàn)[18]。由本實(shí)例可以看出，隨著問(wèn)題的復(fù)雜程度的增加，本文所提算法能夠找到解決多目標(biāo)DLBP較優(yōu)的拆卸序列。

圖3 25個(gè)零部件優(yōu)先拆卸順序

結(jié)果來(lái)源方法文獻(xiàn)[5]ACO--------文獻(xiàn)[9]PSO9985780續(xù)表3 文獻(xiàn)[18]VNS9982576文獻(xiàn)[7]MOACO911898859992787

圖4 各工作站上作業(yè)元素及時(shí)間(f1=9,f2=9,f3=806,f4=74)

從上述實(shí)例可以看出，本文所提出的算法可以有效解決DLBP問(wèn)題，并且隨著問(wèn)題規(guī)模的增大，可以顯著提高拆卸效率，避免算法易陷入局部最優(yōu)，在平衡多個(gè)拆卸目標(biāo)的同時(shí)，給出多種拆卸策略，滿足了不同決策者的實(shí)際需要。

5 結(jié)束語(yǔ)

本文從經(jīng)濟(jì)性和環(huán)保性角度，構(gòu)建了包含4個(gè)決策目標(biāo)的拆卸線平衡問(wèn)題數(shù)學(xué)模型，并根據(jù)模型特點(diǎn)采用基于維度學(xué)習(xí)的多目標(biāo)粒子群算法進(jìn)行求解。該算法通過(guò)動(dòng)態(tài)的鄰居拓?fù)浣Y(jié)構(gòu)、最優(yōu)個(gè)體維度學(xué)習(xí)和隨機(jī)向?qū)W(xué)習(xí)策略保證了種群的多樣性，避免種群早熟陷入局部最優(yōu)，有效提高了算法的全局搜索能力。最后，通過(guò)對(duì)不同規(guī)模的拆卸線平衡問(wèn)題進(jìn)行驗(yàn)證，結(jié)果表明本文所提出的方法在處理大規(guī)模拆卸線平衡問(wèn)題時(shí)，能夠?yàn)闆Q策者提供多種拆卸策略，在滿足最小工作站要求下，提高拆卸效率，為解決大規(guī)模多目標(biāo)拆卸線平衡問(wèn)題提供了一種有效的解決方法。

[1]GungorA,GuptaSM,PochampallyK,etal.Complicationsindisassemblylinebalancing[J].ProceedingsofSPIE-TheInternationalSocietyforOpticalEngineering, 2000, 4193:289-298.

[2]AlekinFT,KandillerL,OzdemirelNE.Disassemblylinebalancingwithlimitedsupplyandsubassemblyavailability[C].Bellingham,Washington:ProceedingsofSPIE,SPIA,2004.

[3]NazarianE,KoJ,WangH.Designofmulti-productmanufacturinglineswiththeconsiderationofproductchangedependentinter-tasktimes,reducedchangeoverandmachineflexibility[J].JournalofManufacturingSystems, 2010, 29(1):35-46.

[4]ChenBW,SongSM,ChenXL.Vehicleroutingproblemwithfuzzydemandsanditsheuristicantcolonyalgorithm[J].JournalofComputerApplications, 2006, 26(11):2639-2638.

[5]McGovernSM,GuptaSM.Antcolonyoptimizationfordisassemblysequencingwithmultipleobjectives[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2006, 30(5):481-496.

[6]KongarE,GuptaSM.Disassemblysequencingusinggeneticalgorithm[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2006, 30(5):497-506.

[7]DingLP,FengYX,TanJR,etal.Anewmulti-objectiveantcolonyalgorithmforsolvingthedisassemblylinebalancingproblem[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2010, 48(5):761-771.

[8]KalayciCB,GuptaSM.Aparticleswarmoptimizationalgorithmwithneighborhood-basedmutationforsequence-dependentdisassemblylinebalancingproblem[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2013, 69(1):197-209.

[9]BentahaML,BattaaO,DolguiA.Asampleaverageapproximationmethodfordisassemblylinebalancingproblemunderuncertainty[J].Computers&OperationsResearch, 2014, 51(3):111-122.

[10]KalayciCB,GuptaSM.Antcolonyoptimizationforsequence-dependentdisassemblylinebalancingproblem[J].JournalofManufacturingTechnologyManagement, 2013, 24(3):413-427.

[11]AwadAR,ChibanSO.Recentadvancesinglobaloptimizationforcombinatorialdiscreteproblems[J].AppliedMathematics, 2015, 6(11):1842-1856.

[12] 王閃閃.基于群智能算法的神經(jīng)網(wǎng)路建模研究[J].電子科技,2017,30(4):56-59.

[13]DouJ,SuC,LiJ.Adiscreteparticleswarmoptimizationalgorithmforassemblylinebalancingproblemoftype1[C].ThirdInternationalConferenceonMeasuringTechnologyandMechatronicsAutomation.IEEE, 2011.

[14]SuganthanPN.Particleswarmoptimizerwithneighborhoodoperator[C].Piscataway,NJ,USA:ProceedingsofIEEECongressonEvolutionaryComputation(CEC), 1999.

[15]LynnN,SuganthanPN.Comprehensivelearningparticleswarmoptimizerwithguidancevectorselection[C].Singapore:IEEESymposiumonSwarmIntelligence, 2013.

[16]RaquelCR,NavalPC.Aneffectiveuseofcrowdingdistanceinmulti-objectiveparticleswarmoptimization[C].WashingtonDC:InGeneticandEvolutionaryComputationConference, 2005.

[17]LuC,HuangHZ,FuhJYH,etal.Amulti-objectivedisassemblyplanningapproachwithantcolonyoptimizationalgorithm[J].ProceedingsoftheInstitutionofMechanicalEngineersPartBJournalofEngineeringManufacture, 2008, 222(11):1465-1474.

[18]TrikiH,MellouliA,HachichaW,etal.Ahybridgeneticalgorithmapproachforsolvinganextensionofassemblylinebalancingproblem[J].InternationalJournalofComputerIntegratedManufacturing, 2015, 29(5):504-519.

[19]KalayciCB,PolatO,GuptaSM.Ahybridgeneticalgorithmforsequence-dependentdisassemblylinebalancingproblem[J].AnnalsofOperationsResearch, 2016, 242(2):321-354.