基于多目標(biāo)麻雀搜索算法的柔性車間生產(chǎn)排程方法

張富強， 吳 磊， 惠記莊， 邵樹軍， 杜 超

(1.長安大學(xué)道路施工技術(shù)與裝備教育部重點實驗室， 西安 710064；2.長安大學(xué)智能制造系統(tǒng)研究所， 西安 710064；3.陜西法士特齒輪有限責(zé)任公司， 西安 710119)

個性化的客戶需求和激烈的市場競爭促使傳統(tǒng)的集中代工生產(chǎn)模式向大規(guī)模個性化定制生產(chǎn)模式轉(zhuǎn)變[1-2]. 多品種、小批量、高質(zhì)量、強交貨期、低消耗等要求成為當(dāng)前柔性車間必須面臨的問題. 在此背景下，組織協(xié)調(diào)各類制造資源，并對生產(chǎn)過程進行有效管控來敏捷響應(yīng)市場多樣化和不確定的需求，快速制造出客戶產(chǎn)品顯得尤為重要.

柔性車間生產(chǎn)排程是當(dāng)前的研究熱點問題. 多數(shù)研究僅針對最大完工時間、交貨延遲期等單目標(biāo)進行建模，但是多個目標(biāo)同時優(yōu)化更加符合實際生產(chǎn)狀況. 部分學(xué)者利用MOEAD(multiobjective evolutionary algorithm based on decomposition)[3]將多目標(biāo)分解為單目標(biāo)進行求解，但是該方法不適用于優(yōu)化目標(biāo)數(shù)值規(guī)模相差較大的情況，并且權(quán)值的均勻性難以保證，權(quán)值難以選取，對柔性車間生產(chǎn)排程問題的適用度較低；利用非支配排序和精英保留策略產(chǎn)生Pareto前沿解的方法更加適用于實際柔性車間生產(chǎn)排程. 在算法求解方面，運籌學(xué)、數(shù)學(xué)等領(lǐng)域方法主要解決小規(guī)模排程問題；而啟發(fā)于自然界生物群體的集體性行為而設(shè)計的群智能算法被眾多學(xué)者和專家用于解決大規(guī)模排程問題. Sassi等[4]提出了一種基于分解的多目標(biāo)人工蜂群算法，可以高效且穩(wěn)定地求解多目標(biāo)生產(chǎn)排程問題；李益兵等[5]將動態(tài)領(lǐng)域搜索引入人工蜂群算法，針對車間生產(chǎn)中的碳排放量、噪聲、廢棄物等問題進行優(yōu)化，獲得了較好的排程結(jié)果；黃海松等[6]采用輪盤賭機器派選方式等到質(zhì)量較高的初始化種群，通過離散花朵授粉算法求解多目標(biāo)調(diào)度問題；陳魁等[7]將小生境技術(shù)引入粒子群算法，避免了算法早熟收斂和不穩(wěn)定性，實現(xiàn)了車間多目標(biāo)排程；Nouiri等[8]將粒子群優(yōu)化算法嵌入到多智能體系統(tǒng)中，為求解動態(tài)如機器故障、維護等的柔性生產(chǎn)排程提供了一種途徑. 盡管采用群智能算法求解柔性車間生產(chǎn)排程問題是當(dāng)前求解大規(guī)模生產(chǎn)排程的有力工具，部分算法也已被用于求解多目標(biāo)柔性車間生產(chǎn)排程問題，但是目前并沒有任何一種算法可以獲取所有問題的最優(yōu)解，所以學(xué)者們還在進行相關(guān)研究，以期待獲得更加有效的方法.

麻雀搜索算法(sparrow search algorithm,SSA)是薛建凱等于2020年提出的具有高性能的全局搜索能力的新型群智能算法，主要是受麻雀的覓食行為以及反捕食過程啟發(fā)而設(shè)計的算法，相比于灰狼優(yōu)化算法、粒子群算法、引力搜索算法，它具有更快的求解速度、更高的求解精度、更佳的全局搜索能力[9]. SSA已被成功運用于多個工程優(yōu)化問題的求解中[10-14]，但是目前沒有將其應(yīng)用于求解柔性車間生產(chǎn)排程問題的研究.

本文將非支配排序引入麻雀搜索算法中，提出了一種多目標(biāo)麻雀搜索算法(multi-objective sparrow search algorithm, MOSSA)，并將其應(yīng)用于多目標(biāo)柔性生產(chǎn)排程問題的求解中. 通過Pareto等級和擁擠度定義最好和最差位置個體，利用SSA進行種群更新，尋找最優(yōu)解集，實現(xiàn)多目標(biāo)優(yōu)化. 采用兩段式編碼規(guī)則生成初始種群，利用MOSSA迭代更新獲取Pareto前沿解，求解多目標(biāo)柔性車間生產(chǎn)排程問題，最后通過仿真實驗驗證了所提出的MOSSA對于生產(chǎn)排程問題求解的可行性和優(yōu)越性.

1 柔性生產(chǎn)排程建模

車間生產(chǎn)排程問題可簡要概括如下：車間中有n個待加工工件，m臺加工機器，每個工件Ji包括ri(ri≥1)道工序，按照指定的工藝路線進行加工,每道工序Oij可在不同的機床上加工，由于不同機器的加工能力不同，工序Oij的加工時間取決于所分配的機器.

為便于模型表達，引入表1數(shù)學(xué)符號定義.

柔性作業(yè)車間中，加工完成時間是生產(chǎn)調(diào)度中最直觀的優(yōu)化指標(biāo)，直接反映車間生產(chǎn)效率，所以在排程中，完工時間應(yīng)該加以考慮；另一方面，在新的制造模式下，綠色制造是其中的一個重要理念，因此考慮生產(chǎn)加工過程中的加工能耗指標(biāo)，是優(yōu)化車間生產(chǎn)制造過程的一個重要途徑，總的加工能耗越小，越符合制造要求，由于車間生產(chǎn)的機器柔性，同一機器可以加工多個不同的工序，應(yīng)盡可能使車間的總機器負(fù)載最小，減小車間的生產(chǎn)消耗；此外，不同機器的加工成本是不一樣的，為最大化車間效益，應(yīng)降低加工成本. 所以，本文以降低柔性車間的完工時間、機器總負(fù)載以及總的加工成本為優(yōu)化目標(biāo). 目標(biāo)函數(shù)表達式為

(1)

(2)

(3)

根據(jù)實際生產(chǎn)情況，存在如下約束條件：

1) 工件開始時間與加工時間要小于完成時間，即

(4)

2) 上一道工序的結(jié)束時間要小于下一道工序的開始時間，即

CTijk≤STij+1

(5)

3) 每個工件的完工時間都應(yīng)該在總的完工時間之前，即

(6)

4) 一臺機器同一時間只能加工一個工件，即

(7)

2 多目標(biāo)麻雀搜索算法

本文將非支配排序引入基本麻雀搜索算法中，設(shè)計了一種多目標(biāo)麻雀搜索算法，并將其應(yīng)用于求解柔性車間生產(chǎn)排程問題.

2.1 基本麻雀搜索算法

圈養(yǎng)家麻雀分為“探索者”和“追隨者”2種，探索者主要是為種群提供整個麻雀群覓食的區(qū)域和方向，追隨者通過探索者來獲取食物，麻雀種群中探索者和追隨者的身份是動態(tài)變化的，可以發(fā)生轉(zhuǎn)換. 同時，種群中部分麻雀為“偵察者”，承擔(dān)偵察預(yù)警工作，它們在覓食的過程中時刻注意周圍環(huán)境，一旦察覺到捕食者威脅，會迅速逃離當(dāng)前位置. 麻雀搜索算法就是模擬麻雀種群搜索食物的過程設(shè)計的啟發(fā)式算法.

2.1.1 迭代公式

探索者具有較高的能源儲備，在種群中負(fù)責(zé)食物搜索工作，并且在發(fā)現(xiàn)捕食者時帶領(lǐng)追隨者去往安全區(qū)域. 在每次迭代的過程中，探索者的位置更新描述為

(8)

式中：t代表當(dāng)前迭代數(shù)；j=1,2,…,d，d表示麻雀個體具有d個維度信息；itermax表示最大的迭代次數(shù)；Xi,j表示第i個麻雀在第j維中的位置信息;隨機數(shù)α介于0與1之間；預(yù)警值R2∈(0,1]和安全值ST∈[0.5,1]；隨機數(shù)Q服從正態(tài)分布；L是一個所有元素為1的1×d的矩陣.

當(dāng)R2

追隨者在覓食過程中時刻監(jiān)視著探索者，它們會和找到更好食物源的探索者搶奪食物. 除此之外，適應(yīng)度值較低的部分追隨者會飛往其他各處覓食. 在每次迭代的過程中，追隨者的位置更新描述為

(9)

式中：Xp是探索者的最佳位置；Xworst表示當(dāng)前全局最差位置；A表示一個1×d的矩陣,其中每個元素隨機賦值為1或-1,并且A+=AT(AAT)-1. 當(dāng)i>n/2時，第i個追隨者處于饑餓的狀態(tài)，它將隨機飛往其他地方尋找食物；i≤n/2時，表示追隨者位于當(dāng)前種群最優(yōu)位置附近，食物資源充足，可就近覓食[9].

部分麻雀覓食的同時肩負(fù)警戒的任務(wù)，當(dāng)察覺到危險時，將發(fā)出警示，無論是探索者還是追隨者，都將逃離當(dāng)前位置另尋食物. 位置更新描述為

(10)

式中：Xbest是當(dāng)前的全局最佳位置；隨機數(shù)β～N(0,1),控制步長；隨機數(shù)K介于-1～1，控制麻雀個體的移動方向；fi是麻雀個體i的適應(yīng)度值；fg和fw分別是t次迭代后全局最大和最小適應(yīng)度值；極小值ε，防止分母為0.fi>fg表示麻雀個體位于種群邊緣，察覺到了危險，向最好位置個體移動；fi=fg表示麻雀個體是最好位置個體，它察覺到危險將飛向種群邊緣，逃離當(dāng)前位置[9].

2.1.2 SSA求解流程

首先設(shè)置探索者和偵察者比例、預(yù)警值的大小，初始化種群；其次計算適應(yīng)度函數(shù)并找出最好和最差位置的麻雀個體；按照式(8)～(10)對探索者、追隨者以及偵察者位置進行更新，獲取當(dāng)前種群最優(yōu)位置，與上一代種群比較，若比之前種群位置更好，則進行更新，否則不更新，再次重新迭代，滿足終止條件后停止.

2.2 編碼和解碼

由于柔性作業(yè)車間同時擁有工序柔性和機器柔性，編碼方式采用兩段式編碼. 第一段基于工序進行，根據(jù)染色體中工件的序號出現(xiàn)的次序編碼，第k次出現(xiàn)的工件序號表示該工件的第k道工序. 第二段基于機器進行，根據(jù)工件可用機器編碼，依次為工件Ji(i=1,2,…，n)的每道工序可用機器之一，標(biāo)號代表相應(yīng)工序的加工機器. 例如工序基因鏈[32111434]表示加工工序為O31O21O11O12O13O41O32O42；若此時的機器基因鏈為[34142434]，表示O11使用3號機器，O12使用4號機器，O13使用1號機器，O21使用4號機器，O31使用2號機器，O32使用4號機器，O41使用3號機器，O42使用4號機器，解碼結(jié)果如圖1所示.

圖1 示例的解碼結(jié)果Fig.1 Decoding result of the example

為了使算法更加適用于實際生產(chǎn)車間，定義每個工件開始加工時間不一定相同，以每個工件的到達時間為開始時間. 工件的每道工序開始加工時間可分為以下4種情況：

1) 若為第一道工序，且機器未曾使用過，則該工序的開始時間為工件到達時間.

2) 若為第一道工序，且機器曾使用過，則開始時間為工件到達時間與機器上一次使用時間中的較大者.

3) 若不是第一道工序，機器未曾使用過，則開始時間為上一道工序的結(jié)束時間.

4) 若不是第一道工序，且機器曾使用過，則開始時間為上一道工序結(jié)束時間和機器上一次加工時間中的較大者.

2.3 Pareto排序與選擇策略

為減少計算復(fù)雜度，采用Konak等[15]提出的一種快速非支配排序方法進行排序. 本文優(yōu)先選擇Pareto等級低的個體，相同等級中選取擁擠度值大的個體，并在選取出的種群中將Pareto等級為1、擁擠度值最大的個體定義為位置最佳個體，等級最高、擁擠度值最小的個體定義為位置最差個體.

2.4 種群的更新

由編碼方式可知，柔性作業(yè)車間問題的解是離散化的，而基于麻雀搜索算法的求解的位置向量是連續(xù)的，因此二者之間需要轉(zhuǎn)換機制. 本文利用工序染色體的總長度作為第t次迭代的位置，利用公式(8)～(10)計算得到的值與工序染色體總長度比較，選取更小的值作為t+1次迭代中染色體需要變更位置的數(shù)量s.更新種群時，工序段染色體隨機交換s個節(jié)點的位置，機器段染色體隨機選取s個節(jié)點，更新為其他的可用機器之一.

算法步驟如下，流程圖見圖2.

圖2 MOSSA流程圖Fig.2 Flow chart of MOSSA

步驟1輸入?yún)?shù)：最大迭代次數(shù)G，探索者數(shù)量PD,偵察者數(shù)量SD，安全值ST.

步驟2初始化種群P0,t=0.

步驟3生成子一代種群.

步驟3.1 非支配排序，選出當(dāng)前種群的最好位置個體和最差位置個體.

步驟3.2 基于SSA的麻雀種群更新.

步驟4父、子代合并.

步驟5快速非支配排序選取新的子代種群.

步驟6基于SSA的麻雀種群更新.

步驟6.1 fori=1:PD

使用式(8)更新麻雀種群位置；

End for

步驟6.2 fori=(PD+1):N

使用公式(9)更新麻雀種群位置；

End for

步驟6.3 forj=1:SD

使用公式(10)更新麻雀種群位置；

End for

步驟7如果t

2.5 收斂性分析

MOSSA將非支配排序引入麻雀搜索算法，麻雀搜索算法具有較好的全局收斂性，由于非支配排序的支配特性， MOSSA每次迭代過程中，都在向Pareto等級為1的方向趨近，因此MOSSA具有較好的收斂性.

3 案例仿真

為了驗證MOSSA求解多目標(biāo)生產(chǎn)排程問題有效性，以文獻[16]中的完全柔性的車間調(diào)度問題為算例進行了仿真實驗，算例工藝路線數(shù)據(jù)如表2所示，8個批次的零件可在7個機器上加工，每臺機器的加工時間不一樣，表3所示為每臺設(shè)備的單位時間加工成本. 仿真軟件為matlab2018a，硬件如下：處理器為Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHz，運行內(nèi)存為8 GB.

3.1 參數(shù)靈敏度分析

麻雀種群由探索者與追隨者組成，二者比例之和為1，同時部分麻雀還承擔(dān)著偵察預(yù)警的作用，因此，仿真實驗中對實驗結(jié)果可能有較大影響的參數(shù)是探索者比例和偵察者比例，二者決定每次迭代中式(8)～(10)的循環(huán)次數(shù)，影響尋優(yōu)能力以及跳出局部最優(yōu)的能力. 采用控制變量法進行實驗，研究探索者和偵查者比例的影響，實驗中選取迭代次數(shù)為200，麻雀種群為100，為消除實驗中可能存在的

表2 算例中工藝路線數(shù)據(jù)[16]

表3 算例中機器加工成本[16]

誤差，每一組參數(shù)運行10次取平均值；為消除由目標(biāo)函數(shù)數(shù)量級不同帶來的影響，對運行結(jié)果進行z-score規(guī)范化，并將規(guī)范化后的數(shù)值取絕對值后求和，將所得值作為評價標(biāo)準(zhǔn)，得到表4所示結(jié)果；從中可知，不同參數(shù)情況下，數(shù)值變化不大，說明在該

表4 探索者和偵察者比例靈敏度分析值

模型算例中，探索者比例和偵察者比例對MOSSA的影響不大.

3.2 算法對比

為了驗證MOSSA求解多目標(biāo)柔性車間規(guī)劃問題的性能，將算法運行參數(shù)設(shè)置為：種群大小為100，迭代次數(shù)為200，探索者比例為20%，追隨者比例為80%，負(fù)責(zé)偵察的麻雀比例為10%，安全值為0.8，運行20次后得到的各目標(biāo)函數(shù)均值與其他算法結(jié)果[16]對比，結(jié)果如表5所示. 由表5中可知，3個目標(biāo)函數(shù)均尋找到更佳的結(jié)果，MOSSA相對于其他3種算法具有更好的收斂性能，具有更好的尋優(yōu)能力，尤其是相比于GA算法有較大程度的提升，相比于多目標(biāo)粒子群算法(multi-objective particle swarm optimization, MOPSO)和多目標(biāo)教學(xué)優(yōu)化算法(multi-objective teaching-learning based optimazation algorithm, MOTLBO)提升較小. 運行速度方面，MOSSA相對于其余三者均有提升，相對于GA、MOPSO和MOTLBO平均運行時間分別縮短了10.53、4.53、3.83 s.

表5 算法結(jié)果對比

3.3 仿真結(jié)果與分析

為了驗證了MOSSA在求解多目標(biāo)生產(chǎn)排程問題的可行性，選取種群大小為100、迭代次數(shù)為200、探索者比例為20%、負(fù)責(zé)偵察的麻雀比例為10%、安全值為0.8進行仿真實驗. MOSSA隨機運行一次后產(chǎn)生的Pareto解集如表6所示，相應(yīng)的Pareto前沿如圖3所示，隨機選取其中的一組解繪制甘特圖如圖4所示. 在圖4所示排程安排下，車間完工時間為12 h，加工成本為664元，機器總負(fù)載為53 h，調(diào)度結(jié)果滿足算例要求.

算法運行過程中發(fā)現(xiàn)，Pareto等級為1的解集中有目標(biāo)函數(shù)值完全相等的個體，甚至是存在所有等級為1的解都為同一值的現(xiàn)象，即算法收斂到一個點上，但是比較相應(yīng)的工序編碼與機器編碼發(fā)現(xiàn)二者之間存在差異. 如表7所示的為一個Pareto解集，其中只有8個解的目標(biāo)函數(shù)值是不一樣的，圖5中(a)和(b)分別是解集中的第3個解和第6個解的排程甘特圖，可知，相同目標(biāo)函數(shù)值的甘特圖是不相同的，說明二者的編碼是不一樣的，比較其他幾個解發(fā)現(xiàn)，編碼結(jié)果也不相同，說明解集中的解是不同的個體. 上述實驗結(jié)果表明，在該模型中，多目標(biāo)麻雀搜索算法具有較好的收斂性. 另一方面，該種情況下，如果生產(chǎn)過程中存在某臺機器故障，或者某毛坯到達車間時間延遲等動態(tài)擾動時可以快速替換為另一種排程方式，達到完全相同的效果，提高生產(chǎn)效率，實現(xiàn)動態(tài)高效的排程；如圖5所示，假設(shè)生產(chǎn)過程中工件3的毛坯無法在開機時間送達車間，則可選擇圖5(b)的排程方式，工件3的毛坯只需在12 h之前送達即可. 這在一定程度上反映了MOSSA對于多目標(biāo)柔性車間排程的有效性以及MOSSA高效的搜索性能.

表6 Patero解集

圖3 柔性車間Pareto前沿Fig.3 Pareto front of flexible workshop

圖4 柔性車間排程甘特圖Fig.4 Gantt chart of flexible workshop scheduling

表7 存在相同值的Pareto解集

圖5 相同目標(biāo)值的不同排程方式Fig.5 Different scheduling methods with the same target value

對于迭代優(yōu)化獲取的Pareto解集中相同目標(biāo)函數(shù)值的排序結(jié)果，首先根據(jù)工廠狀況，如機器狀況、工件毛坯的到達時間等進行選擇，選取最適應(yīng)當(dāng)前工廠狀況的排序結(jié)果；其次，若工廠狀況良好，正常運行，以最小化單機總負(fù)載為二次優(yōu)化目標(biāo)，對排序結(jié)果進行再次選擇，盡可能減少單機工作負(fù)載過大的情況，避免出現(xiàn)瓶頸機器，合理分配機器的利用率，提高機器使用壽命.

4 結(jié)論

1) 以最小化完工時間、最低車間總負(fù)載和最小化車間生產(chǎn)成本建立多目標(biāo)柔性車間生產(chǎn)排程數(shù)學(xué)模型.

2) 提出了一種融合非支配排序和麻雀搜索算法的多目標(biāo)算法MOSSA；通過兩段式編碼以及連續(xù)化轉(zhuǎn)變實現(xiàn)對柔性車間生產(chǎn)排程問題的求解.

3) 通過控制變量法進行實驗，結(jié)果表明，在該模型下，探索者比例和偵察者比例對MOSSA的影響較小，二者的靈敏度不高.

4) 通過算例對比MOSSA與其他算法的性能，結(jié)果表明MOSSA解決多目標(biāo)柔性車間生產(chǎn)排程的可行性、有效性和優(yōu)越性.