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

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

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

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

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

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

1 柔性生產排程建模

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

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

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

(1)

(2)

(3)

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

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

(4)

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

CTijk≤STij+1

(5)

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

(6)

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

(7)

2 多目標麻雀搜索算法

本文將非支配排序引入基本麻雀搜索算法中，設計了一種多目標麻雀搜索算法，并將其應用于求解柔性車間生產排程問題.

2.1 基本麻雀搜索算法

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

2.1.1 迭代公式

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

(8)

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

當R2

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

(9)

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

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

(10)

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

2.1.2 SSA求解流程

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

2.2 編碼和解碼

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

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

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

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

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

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

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

2.3 Pareto排序與選擇策略

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

2.4 種群的更新

由編碼方式可知，柔性作業(yè)車間問題的解是離散化的，而基于麻雀搜索算法的求解的位置向量是連續(xù)的，因此二者之間需要轉換機制. 本文利用工序染色體的總長度作為第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 非支配排序，選出當前種群的最好位置個體和最差位置個體.

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

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

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

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

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

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

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

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

3.2 算法對比

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

表5 算法結果對比

3.3 仿真結果與分析

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

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

表6 Patero解集

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

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

表7 存在相同值的Pareto解集

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

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

4 結論

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

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

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

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