辛 悅,顧 德

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

0 引言

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

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

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

1 問(wèn)題模型

1.1 問(wèn)題描述以及約束

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

①每道工序開(kāi)始處理后不允許暫停。

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

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

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

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

(1)

(2)

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

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

表1 變量定義Tab.1 Variable definition

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

③比較運(yùn)算。

2 基本粒子群算法

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

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

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

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

(3)

(4)

3 離散改進(jìn)PSO

3.1 編碼方式

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

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

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

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

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

3.2 重構(gòu)公式

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

(5)

(6)

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

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

粒子更新過(guò)程偽代碼如下：

01 初始化N個(gè)粒子位置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中，淺灰色子代編碼來(lái)自父代1，深灰色子代編碼來(lái)自父代2。首先，從父代1編碼中選取相臨的一段編碼放入子代，其順序與位置與父代1相同。然后，在父代2中找出剩余缺少的基因，并按照原來(lái)的順序填入子代編碼空位處。

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

3.4 精英保留策略

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

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

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

3.5 算法步驟

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

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

②利用變異操作隨機(jī)探索個(gè)體位置。

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

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

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

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

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

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

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

(7)

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

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

對(duì)比算法為文獻(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，對(duì)比算法按照原文設(shè)置參數(shù)，每個(gè)算法的種群規(guī)模為50，迭代次數(shù)為200。繪制迭代結(jié)束時(shí)三種算法的近似Pareto前沿，如圖5所示。

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

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

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

表4 算法對(duì)比Tab.4 Comparison of methods

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

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

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

5 結(jié)論

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