離散改進(jìn)PSO求解模糊柔性作業(yè)車間多目標(biāo)調(diào)度

辛 悅,顧 德

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引言

制造業(yè)是當(dāng)今社會的支柱。隨著“工業(yè)4.0”時代的到來以及國家相關(guān)政策的實施，智能制造受到了廣泛關(guān)注[1]。作為智能制造生產(chǎn)過程的關(guān)鍵環(huán)節(jié)，車間需要在有限的設(shè)備生產(chǎn)性能約束下，合理決策工件、工序以及加工設(shè)備，使所得的生產(chǎn)調(diào)度方案能夠?qū)崿F(xiàn)一個或者多個目標(biāo)。因此，調(diào)度方案的合理性對智能制造的效率有著巨大的影響。車間調(diào)度是智能制造的研究熱點之一。

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)是車間調(diào)度問題的進(jìn)一步拓展。其在車間調(diào)度問題的基礎(chǔ)上考慮了同一工件工序所用設(shè)備的彈性選擇。對于FJSP的研究，國內(nèi)外取得了很多進(jìn)展：Yuan等[2]提出了一種新的模因算法，并將一種新的局部搜索算法引入到適應(yīng)的非支配排序遺傳算法(non-dominated sorting genetic alogrithm,NSGA-II)中，以求解FJSP；Tianhua等[3]提出了一種基于雙種群的離散貓群優(yōu)化算法，以得到車間的最優(yōu)調(diào)度方案；Pezzella等[4]提出了一種集成了不同初始種群生成策略、個體選擇策略和新個體復(fù)制策略的遺傳算法，以尋求最優(yōu)調(diào)度方案；Xia等[5]將粒子群算法與模擬退火算法混合，有效求解大規(guī)模多目標(biāo)調(diào)度問題；徐華等[6]利用呈指數(shù)遞減的慣性權(quán)重策略改進(jìn)蝙蝠算法，求解調(diào)度最優(yōu)解。

雖然以上方法很好地求解了FJSP，但僅考慮了確定的生產(chǎn)參數(shù)。在實際情況下，設(shè)備的損耗、電費的漲幅等外界因素使得工序加工時間、生產(chǎn)成本等生產(chǎn)參數(shù)并不是一個確定值。對于此問題，將FJSP中加工時間、加工成本等不確定參數(shù)用三角模糊數(shù)來代替，利用三角模糊函數(shù)對車間調(diào)度優(yōu)化的問題進(jìn)行數(shù)學(xué)建模并設(shè)計相關(guān)問題的目標(biāo)函數(shù)，所得到的調(diào)度結(jié)果更具魯棒性。使用離散改進(jìn)的粒子群優(yōu)化(particle swarm optimization,PSO)算法對調(diào)度方案進(jìn)行尋優(yōu)，保留了調(diào)度算法的多樣性，避免后期迭代過程陷入局部最優(yōu)。同時，通過計算機仿真結(jié)果對比，反映改進(jìn)算法的優(yōu)越之處。

1 問題模型

1.1 問題描述以及約束

FJSP可以敘述為：車間有m臺加工設(shè)備、n個工件，各工件有多道工序，每道工序有多臺可選設(shè)備，工序的加工順序固定，每臺設(shè)備的性能不同。調(diào)度的目的是確定各個加工設(shè)備安放的工件及其工序，使得整個生產(chǎn)系統(tǒng)的加工時間、加工成本這兩個目標(biāo)最小化。其具體約束如下。

①每道工序開始處理后不允許暫停。

②一臺設(shè)備在某一時刻只可處理一個工件。

③在t=0時，所有工件都可以被可選設(shè)備集中的機器加工。

④同一工件按照設(shè)定工序加工，不同工件優(yōu)先級相同。

根據(jù)符號定義，本文的目標(biāo)函數(shù)可表示為：

(1)

(2)

式中：minNcost為最小加工總成本；minNperiod為最小完工時間。

為便于分析，對建模涉及的變量進(jìn)行定義，如表1所示。

表1 變量定義Tab.1 Variable definition

1.2 三角模糊數(shù)運算

③比較運算。

2 基本粒子群算法

粒子群算法模擬了鳥類群體的覓食特性[7]，是全世界群體算法研究者的研究熱點。其主要遵循以下兩個尋優(yōu)規(guī)則。

①根據(jù)個體自身搜尋經(jīng)驗進(jìn)行搜索。

②根據(jù)社會最優(yōu)個體搜尋經(jīng)驗進(jìn)行搜索。

其主要的速度和位置更新操作如式(3)與式(4)所示。

(3)

(4)

3 離散改進(jìn)PSO

3.1 編碼方式

FJSP包括兩個子問題，分別為工序排序問題(operations sequencing，OS)與機器選擇問題(machines selection，MS)。對于一個調(diào)度方案的編碼示例如圖1所示。

圖1 編碼示例Fig.1 Example of code

圖1中：OS部分的首個1表示工件1的首道工序O11；MS部分的首個1表示O11的可選加工設(shè)備集的第一個設(shè)備。使用工序?qū)?yīng)可選設(shè)備集的順序編號，而不是原始的機器編號，可以保證后續(xù)引入交叉、變異操作后產(chǎn)生的解仍是可行解。

假設(shè)其加工設(shè)備集為{M1，M2}，則該數(shù)字表示M1；假設(shè)所有工件工序集合為{M1，M2}，則編碼意義如圖2所示。使用OS與MS分離的編碼方式，能有效解決調(diào)度任務(wù)在計算機中的存儲方式，便于算法運算。

圖2 編碼意義Fig.2 Meaning of code

3.2 重構(gòu)公式

由于傳統(tǒng)PSO算法是連續(xù)算法，在迭代后期存在多樣性喪失的問題，無法處理FJSP之類的復(fù)雜組合優(yōu)化問題。因此，本文根據(jù)廣義粒子群思想[8]，設(shè)計新算法框架，重構(gòu)了PSO的公式，使得算法具有解決離散問題的能力。在粒子群的位置與速度更新操作中引入遺傳算法的交叉、變異操作，其改進(jìn)公式如式(5)與式(6)所示。

(5)

(6)

則由式(6)可知，變異概率不會大于0.25。新設(shè)計的算法框架以遺傳算法交叉變異操作的離散操作算子替換原有公式的加乘運算，可有效利用遺傳算法能夠保留多樣性的特點、確保算法迭代后期的多樣性、提升算法的尋優(yōu)性能。

本文采用加入擁擠測度的快速NSGA-II[9]對粒子個體評價。更新個體歷史最優(yōu)位置的方式為：若粒子當(dāng)前位置可以支配個體歷史最優(yōu)位置，則將其作為個體歷史最優(yōu)位置。而對于全局歷史最優(yōu)位置的更新方式為：若在所有粒子個體中，存在一個粒子位置能支配全局歷史最優(yōu)位置，則更新為該粒子的位置。

粒子更新過程偽代碼如下：

01 初始化N個粒子位置xg，最大迭代次數(shù)G，粒子速度vg

02 Forg=1 toG

03 Fori=1 toN

04 Ifr

06 End If

07 Ifr

09 End If

10 Ifr

12 End For

14 End For

3.3 OX交叉操作

本文f2交叉操作采用的是順序交叉方式，如圖3所示。圖3中，淺灰色子代編碼來自父代1，深灰色子代編碼來自父代2。首先，從父代1編碼中選取相臨的一段編碼放入子代，其順序與位置與父代1相同。然后，在父代2中找出剩余缺少的基因，并按照原來的順序填入子代編碼空位處。

圖3 順序交叉方式Fig.3 The way of order crossover

3.4 精英保留策略

為保護(hù)粒子的多樣性，使用帶外部記憶庫的精英保留策略，如圖4所示。

圖4 精英保留策略Fig.4 Elite retention strategy

粒子位置更新后形成新種群，并對個體進(jìn)行評價。每一次對新種群評價排序后，都需要對外部記憶庫進(jìn)行更新，將非支配等級最高的新精英個體與記憶庫中的精英個體進(jìn)行比較。若當(dāng)前個體被記憶庫中的某個體支配，則丟棄該解；若記憶庫中的某個體被新精英個體支配，則將被支配個體剔除并將新個體存入記憶庫。若記憶庫的個體與新精英個體不存在支配與被支配關(guān)系，則直接將新的精英個體放入記憶庫中。使用帶外部記憶庫的精英保留策略，使得算法能夠充分利用迭代優(yōu)化過程中的信息并將其用于指導(dǎo)子代的產(chǎn)生，以提高算法的尋優(yōu)性與收斂性。

3.5 算法步驟

結(jié)合離散化改進(jìn)和精英保留策略，整體的算法步驟如下。

①初始化個體位置和速度，全局最優(yōu)及個體最優(yōu)。

②利用變異操作隨機探索個體位置。

③利用交叉操作獲取個體最優(yōu)位置信息，以更新個體位置。

④利用交叉操作獲取全局最優(yōu)位置信息，更新個體位置。

⑤更新粒子群中個體的位置與速度。

⑥對粒子個體進(jìn)行快速非支配排序，更新全局最優(yōu)、個體最優(yōu)及外部記憶庫。

⑦確認(rèn)是否已達(dá)到最大迭代次數(shù)；若達(dá)到，則停止運算并輸出最優(yōu)解；若未達(dá)到，則返回步驟⑦。

4 試驗仿真及結(jié)果分析

為驗證本文算法的有效性，進(jìn)行試驗測試。測試環(huán)境為：Win7 x64 專業(yè)版系統(tǒng)，8 GB DDR3內(nèi)存，I7-4900MQ處理器，編程語言為MATLAB 2016a，試驗數(shù)據(jù)參考文獻(xiàn)[10]。采用C測度來對比算法之間的性能優(yōu)越性，測度函數(shù)如式(7)所示。

(7)

式中：a、b分別為算法A、B產(chǎn)生的Pareto解；Count為解集的個數(shù)。

若C(A,B)>C(B,A)，則算法A優(yōu)于算法B。為便于比較，采用三角模糊數(shù)的準(zhǔn)則一來使得模糊數(shù)近似于定值，以此構(gòu)造近似Pareto前沿。

對比算法為文獻(xiàn)[10]的自適應(yīng)離散多目標(biāo)花授粉算法(adaptive discrete multi-objective flower pollination algorithm,ADMOFPA)以及文獻(xiàn)[11]的多目標(biāo)粒子群優(yōu)化(multi-objective particle swarm optimization,MOPSO)算法。本文算法仿真參數(shù)為w=0.4，c1、c2設(shè)置為1.5，對比算法按照原文設(shè)置參數(shù)，每個算法的種群規(guī)模為50，迭代次數(shù)為200。繪制迭代結(jié)束時三種算法的近似Pareto前沿，如圖5所示。

圖5 近似Pareto前沿示意圖Fig.5 Approximate Pareto front

由圖5可以看出，本文算法的近似Pareto前沿在ADMOFPA和MOPSO算法的左下方，因此更逼近最優(yōu)解。由于粒子群初始值設(shè)置欠妥，導(dǎo)致Pareto解集存在少量劣解，但這不影響近似最優(yōu)解的產(chǎn)生。三種算法的C測度結(jié)果如表4所示，可知本文所得Pareto解支配其余算法的比例遠(yuǎn)大于被支配的比例。

根據(jù)NSGA-II的擁擠測度對各算法所得的Pareto前沿進(jìn)行排序，排在首位的解即該算法的最優(yōu)解。

表4 算法對比Tab.4 Comparison of methods

本文算法最優(yōu)解調(diào)度方式如圖6所示。

圖6 最優(yōu)解調(diào)度方式Fig.6 Sispatching mode of optimal solution

圖6中，下三角表示開始加工，上三角表示結(jié)束加工，編碼意義為工件標(biāo)號與工序標(biāo)號。本文算法、MOPSO、ADMOFPA所得最大完工時間與生產(chǎn)成本的最優(yōu)解值分別為(115,3 398),(116,3 425),(173,3 172)。由三組最優(yōu)解可知,本文所得最優(yōu)解支配MOPSO的解，相比ADMOFPA的最優(yōu)解，近似成本雖然有略微的劣勢但在完工時間上卻有絕對的優(yōu)勢。因此，本文算法更優(yōu)。

5 結(jié)論

本文針對多目標(biāo)模糊柔性作業(yè)車間調(diào)度問題，提出了一種離散改進(jìn)PSO算法。該算法使用遺傳算法的交叉、變異算子重構(gòu)了PSO的位置與速度更新公式，并針對多目標(biāo)使用帶外部記憶庫的精英保留策略。最后，通過對比多種算法的車間實例仿真結(jié)果，驗證了改進(jìn)算法的合理性。今后，可將算法用于實際的生產(chǎn)中，以提高算法的適用性。