麻雀搜索算法解決柔性作業(yè)車間調度問題

楊紅雄 王惠酩

（天津理工大學管理學院，天津 300384）

隨著智能化在制造業(yè)中的普及，解決車間生產(chǎn)調度的問題能有效提高車間的工作學習效率，實現(xiàn)車間現(xiàn)場管理的有序化、智能化和高效化。為了合理地協(xié)調控制各個機器的生產(chǎn)以實現(xiàn)多方面目標的pareto最優(yōu)狀態(tài)，學者們經(jīng)過多年的研究，使用各種不同的方法來分析和解決生產(chǎn)環(huán)節(jié)的FJSP。隨著研究的逐漸深入，為了更貼近車間生產(chǎn)現(xiàn)場的工作狀態(tài)，人們將柔性車間這一概念與車間調度問題相融合并提出了FJSP。由于FJSP問題在生產(chǎn)中廣泛存在，因此，該問題引起了國內外相關學者的廣泛關注與研究[1?5]。Ishibuchi H使用遺傳算法求解FJSP問題，但算法的有效性較低[6]。Deng Q W使用NSGA-II算法并考慮分兩階段對多目標FJSP進行求解，并通過一些常用的函數(shù)驗證算法的準確性[7]。Kaya S等人對相關文獻進行了綜述研究，并分析了多目標FJSP的最新算法的思想解決以完工時間最大、機器負荷最小和瓶頸工序負荷最小為目標的FJSP問題。陳魁等提出了優(yōu)化小生境粒子群的算法求解模型，將運輸時間這一變量加入FJSP問題，構建以完工時間最大化、機器負載最大化以及機器總負荷最小為目標的模型[8]。

2020年，薛建凱等人受到麻雀尋找食物和躲避天敵的行為啟發(fā)提出麻雀搜索算法（sparrow search algorithm，SSA）[9]。該算法由于具有搜索精度高、收斂速度快、穩(wěn)定性強和有效地避免局部最優(yōu)值等方面的優(yōu)點，受到了國內外學者廣泛關注。毛清華等發(fā)現(xiàn)原始的SSA算法容易陷入局部最優(yōu)問題，提出了將SSA與正弦余弦混合算法相融合的算法(improved sparrow search algorithm,ISSA)。并對算法的結果進行測驗，證明 ISSA 具有更高的尋優(yōu)精度和更快的求解效率[10]。湯安迪等人為了解決規(guī)劃無人機航跡時方案的求解難度大、方案不容易收斂等一些問題，使用了基于混沌麻雀搜索算法的航跡規(guī)劃方法，根據(jù)算法來規(guī)劃無人機的航跡方案，證明了SSA算法可以有效地解決這類問題[11]。楊瑋等以降低企業(yè)冷鏈物流的成本作為優(yōu)化目標，考慮到冷鏈物流企業(yè)在貨物存儲和貨物運輸?shù)拳h(huán)節(jié)會產(chǎn)生成本的現(xiàn)象，并結合我國最近正在實行的碳交易政策，將企業(yè)的碳排放代價同其他代價綜合考慮，建立以總代價最低為目標的成本模型，設計并改良了麻雀搜索算法進行計算，證明了麻雀搜索算法可以有效地解決冷鏈物流運輸問題[12]。韓統(tǒng)等人提出了一種將對數(shù)螺旋策略和自適應步長策略相混合的思想與麻雀搜索算法相結合（logarithmic spiral strategy and adaptive step size strategy of the SSA,LASSA）來解決無人機協(xié)同航向規(guī)劃問題。驗證了LASSA可以有效地解決多無人機協(xié)同航跡規(guī)劃問題[13]。

綜上所述，就算法的研究現(xiàn)狀來說，由于SSA是最近提出的一種算法，具有收斂速度快，不易陷入局部最優(yōu)等優(yōu)點。并且目前的研究使用SSA解決的大部分都是無人機領域的問題，將SSA運用于實際車間生產(chǎn)制造中的研究較少。本文首次使用SSA解決柔性作業(yè)車間調度方面的問題，提出了基于FJSP的SSA算法，以最大完工時間最小和總能耗最小為優(yōu)化目標求解FJSP。首先對FJSP問題進行描述并根據(jù)其特點分析建模，然后介紹了一種可以求解FJSP問題的SSA算法，利用標準算例進行仿真驗證，由于SSA算法具有收斂速度快、結構簡單和不易陷于局部最優(yōu)的特點，解決了傳統(tǒng)算法在解決SSA問題時收斂速度慢，易于陷入局部最優(yōu)的問題，證明了SSA求解FJSP的可行性、高效性和優(yōu)越性。

1 問題描述與建模

1.1 問題描述

作業(yè)車間調度是根據(jù)實際車間有限的可用資源和已定的生產(chǎn)計劃，在滿足工藝約束的基礎上合理安排生產(chǎn)路線，均衡生產(chǎn)負荷，完成生產(chǎn)計劃的同時實現(xiàn)某種既定目標的問題。FJSP是為了解決作業(yè)車間調度如何才能與多臺并行機相結合而提出的，主要涉及以下兩個問題：

（1）按什么順序加工工件。

（2）如何合理地分配機器。

FJSP已被證明是更復雜的NP-hard問題，本文的FJSP問題主要是基于解決以上2個問題，并結合車間的實際生產(chǎn)為了達到完成時間最短和總流程時間最短的目標求出的pareto最優(yōu)解。

FJSP可以用以下例子來描述：設車間有m臺機器，需要加工n個工件，每臺機器表示為M1,M2,···,Mn。每個工件表示為N1,N2,···,Nn。每個工件在機器上一次性完成的工藝過程叫工序，Oij表示工件i的第j道工序。最終的目標是使完成這批工件所用的時間最短和消耗的能源最少。相關的約束條件有：

（1）一臺機器在某一時刻只加工一個工件。

（2）每個工件加工生產(chǎn)的工序相同，工序的加工順序相同，根據(jù)算例的不同，不同工件在不同機器上加工消耗的時間不同。

（3）相同工件在某一時刻不能被不同的兩臺機器加工。

（4）工件在加工過程中不能更換機器加工。經(jīng)典的FJSP如下所示。以5臺機器加工3個工件，每個工件有3個加工工序的情況為例，加工的時間表如表1所示。

1.2 數(shù)學模型

數(shù)學模型可以清晰直觀地表達FJSP，我們將定義以下幾個參數(shù)變量：

r：工件總數(shù)，共有r個需要加工的工件，每個工件表示為N1,N2,···,Nr。

n：工序總數(shù)，工件Ni共有n道工序(i=1,2,···,r)。

k：機器總數(shù)，共有k個可以加工的機器，每臺機器表示為M1,M2,···,Mk。

Oij：工件Ni的第j道工序(j=1,2,···,n)。

Ωk：所有機器的集合{M1,M2,···,Mk}。

Ωik：工件Ni的第j道工序所有可選加工機器的集合，是機器集合Ωk的子集，Ωik∈{M1,M2,···,Mk}。

表13×5的完全柔性作業(yè)車間加工時間表

mik：工件Ni的第j道工序所有可以選擇的加工機器數(shù)。

Mijh：工件Ni的第j道工序(Oij)選擇在機器Mh上加工(h=1,2,···,k)。

Pijh：工序Oij在機器Mh上的加工時間。

Sij：工件Ni的第j道工序(Oij)的開始加工的時間。

Cij：工序Oij的完成加工時間。

Ci：工件Ni的完成加工的時間。

Cmax：所有工序完工時最大的完工時間。

Wt：所有機器加工完成最大工作負荷。

FJSP的約束條件有：約束條件是限制操作的可能分配的規(guī)則。FJSP問題主要有以下幾個有數(shù)條件：

式（1）表示加工第i個工件的第j道工序（Oij）只能在該道工序可以選擇的機器集合（Ωik）中選擇一臺機器進行加工。式（2）表示加工第Ni個工件的第j道工序（Oij）的完工時間應大于等于其在該機器上的開始加工時間與加工時間之和。式（3）表示一個零件的不同工序間需要滿足先后順序。式（4）表示機器上相鄰工件之間前一工件工序的完成加工時間應小于等于下一工件工序的開始加工時間。式（5）表示所有工件最后一道工序的完工時間都小于等于最大完工時間。

本文考慮生產(chǎn)現(xiàn)場的時間生產(chǎn)情況，以最大完工時間（Cmax）和機器最大工作負荷（Wt）為目標，建立最小化數(shù)學模型。目標函數(shù)如式（6）和式（7）。

1.3 雙目標優(yōu)化

對于2個目標的FJSP問題目前主流的解決方法主要有3種：

（1）目標規(guī)劃法：該方法主要用于解決參數(shù)和約束較少的優(yōu)化問題，首先需求出各子目標的最優(yōu)值，然后將各子目標的最優(yōu)值作為初始問題的約束。最后，將每個子目標的值與其最優(yōu)值做差，最終的結果就是初始問題的最優(yōu)解。

（2）功效系數(shù)法：該方法對每個目標函數(shù)進行賦值，通過每個目標對于整體結果的重要性來決定賦值的大小，綜合函數(shù)值最優(yōu)的結果及為函數(shù)的最優(yōu)解。

（3）動態(tài)權重法：該方法對每個目標函數(shù)進行動態(tài)賦值，與功效系數(shù)法不同的是，在算法迭代過程中，每迭代一次權重系數(shù)就變化一次，直到得到最優(yōu)解為止。

文獻[14]認為產(chǎn)品的加工時間越小對于制造商降本增效的影響越突出，在車間調度的實施過程中，Cmax越小說明總生產(chǎn)周期越短，有助于提高企業(yè)的生產(chǎn)效率與資源利用率，Wt越小說明生產(chǎn)消耗的能耗越小，有助于降低企業(yè)生產(chǎn)成本。功效系數(shù)法相較其他兩種方法更適用于子目標之間不均衡、具有主導性的多目標問題，因此，本文考慮使用功效系數(shù)法求解FJSP問題。用dj(0

因此，目標函數(shù)可以表示為

其中：ω1+ω2=1。

本文根據(jù)文獻[15]中的Delfi調查法得到ω1和ω2，對應權重分別為0.7、0.3，在實際生產(chǎn)調度問題中該權重值應根據(jù)車間生產(chǎn)需求情況進行調整。

2 求解FJSP的SSA流程設計

SSA中每一只麻雀都代表一組可行的調度方案，麻雀的適應度值表示調度方案的合理程度，適應度值越高則表示方案越可行。麻雀尋找食物的過程可以被想象為“發(fā)現(xiàn)者-追隨者”模型，SSA將群內個體分為發(fā)現(xiàn)者、追隨者和偵察者3種類型，為了提高個體的捕食幾率，當追隨者通過發(fā)現(xiàn)者獲取食物時，種群中的一些個體為了增加自己的捕食量會與其他同類爭搶食物，同時，以安全第一為原則按比例將一部分麻雀作為偵察者進行偵察和預警，當偵察者發(fā)現(xiàn)危險時及時警告其他麻雀如果發(fā)現(xiàn)危險則停止進食，由發(fā)現(xiàn)者重新尋找食物。通過不斷地捕食和反捕食行為迭代更新進行尋優(yōu)進化。

下面將介紹一種適合解決FJSP的SSA并解決一個以最大完工時間最小和總能耗最小為優(yōu)化目標的FJSP。

2.1 編碼與解碼

SSA通過不斷地更新自身的位置和尋找食物源的方式對優(yōu)化的目標進行搜索，F(xiàn)JSP主要是解決工件排序和機器指派這2個問題，因此，本文使用兩階段向量編碼方法，前一段確定工序的加工順序，后一段確定機器的指派問題，保證了編碼后個體的有效性。

以3個工件每個工件包含兩道工序的問題為例，編碼鏈前半段（第1位?第6位編碼）為工序隨機排序的方案。例如，編碼中第二位的“3”表示工件3的第一道工序；后半段（第7位?第12位編碼）為機器的隨機分配方案，每個編碼表示工序在機器上的加工順序。例如，編碼中第七位的“2”表示工序O12即第一個工件的第二道工序在機器2上加工。隨機生成的編碼鏈按圖1的方式進行存儲。

圖1 編碼方式

在解碼的過程中，首先根據(jù)工序排序編碼鏈確定一個工件在機器上的加工順序，然后機器分配編碼確定各個機器上加工的工序順序，即轉化為一個工序表，根據(jù)工序表將所有工序安排在適當?shù)募庸C器和加工位置上，最后生成可行的調度方案。

2.2 SSA算法步驟

2.2.1 種群初始化

設定算法的各部分參數(shù)如最大迭代次數(shù)、種群數(shù)量、發(fā)現(xiàn)者比例和安全閾值等。

本文隨機生成編碼產(chǎn)生初始調度解，每一只麻雀表示一個調度方案，由n只麻雀組成的種群可以表示為

其中：d為問題的維數(shù)；n為麻雀的數(shù)量。那么，每個方案的適應度表示為

其中：f是適應度值，根據(jù)適應度值的大小對麻雀個體進行排序，進而選擇出最優(yōu)個體和最差個體，得到全局最優(yōu)位置，然后根據(jù)設定的警報值進入迭代循環(huán)。

2.2.2 發(fā)現(xiàn)者的位置更新

在SSA中，麻雀個體相對種群的位置表示可行的調度方案。假設在D維空間中存在N只麻雀，每只麻雀可以表示為一個矩陣

則麻雀i的位置可以記作

式（8）中：n是麻雀的數(shù)量。式（9）中：i表示第i只麻雀。i=1,2,3,···,n。D代表變量的維數(shù)。Xi,1表示問題維數(shù)為1維時，第i只麻雀的位置。

每個個體的適應度值表示為

Fx表示每個個體的適應度值，根據(jù)適應度對麻雀進行排序，選出適應度好的麻雀個體作為發(fā)現(xiàn)者尋找食物源并優(yōu)先獲得食物，帶領其他麻雀向食物源靠近。在種群中，發(fā)現(xiàn)者和追尋者數(shù)量在每次迭代循環(huán)中一般都保持一致，占麻雀種群數(shù)量的10%～20%。發(fā)現(xiàn)者的位置更新公式為

其中：t為算法當前的迭代次數(shù)，i表示第i只麻雀，j表示問題的維數(shù)，表示第t+1次迭代時第i只麻雀在第j維的位置；μ是范圍在（0,1）之間的隨機數(shù)；Tmax是最大迭代次數(shù)；R2∈[0,1]、ST∈[0.5,1]分別代表預警值和安全值；Q是一個遵從[0,1]正態(tài)分布的隨機數(shù)；L是一個所有元素都是1的1×d維矩陣。當R2

2.2.3 追隨者的位置更新

追隨者的位置更新公式為

2.2.4 偵察預警行為

當種群中的偵察者發(fā)現(xiàn)危險或捕食者時，就會向種群發(fā)出警報信號，此時，無論是尋找食物的發(fā)現(xiàn)者還是正在進食的追隨者都會放棄當前食物并改變其位置向安全的位置移動。發(fā)現(xiàn)者到達安全位置后才會繼續(xù)尋找新的食物源，繼續(xù)迭代更新其位置。一般種群都會選取SD（種群數(shù)量的10%～20%）只麻雀作為偵察者對周圍位置的安全偵察預警。偵察者的位置更新公式為

式（14）中：β是步長控制參數(shù)，服從均值為0，方差為1的正態(tài)分布隨機數(shù)。fi是第i只麻雀的適應度值；fg是當前麻雀的全局最優(yōu)適應度值；K是步長控制參數(shù)服從[?1,1]的均勻隨機分布，用于表示麻雀的移動方向；fw是當前適應度值最低的個體；ε是常數(shù)，為了防止出現(xiàn)分母為0的情況，一般 ε的值極小。當fi≠fg時表明，麻雀i的位置處于種群的邊緣，極易受捕食者的攻擊；當fi=fg時表明，麻雀i正處于種群中間的位置，意識到了來自捕食者的危險，需要靠近其他麻雀個體來減少自己被捕食的危險并調整搜索策略。

算法的具體步驟如下：

Step1：輸入算例的數(shù)據(jù)。

Step2：初始化種群，如設定麻雀種群中發(fā)現(xiàn)者的數(shù)量、意識到危險的麻雀所占種群的比例。

Step3：初始化算法參數(shù)并對數(shù)據(jù)進行編碼，生成初始調度方案，找到種群中最好和最差的個體。

Step4：根據(jù)式（13）、（14）更新發(fā)現(xiàn)者、追隨者位置。

Step5：判斷新位置的適應度值是否好于當前位置，如果沒有則保持當前位置不變繼續(xù)下一步操作；如果有則更新當前位置。

Step6：直至收斂或達到最大迭代次數(shù)算法結束并得到優(yōu)化目標的最優(yōu)解。

根據(jù)以上對于數(shù)學模型的描述和算法的步驟，設計基于FJSP問題的流程如圖2所示。

圖2 算法流程圖

3 仿真測試

本文使用MATLAB編程語言并使用MATLAB 2017a運行程序。運行環(huán)境為：WinXP操作系統(tǒng)下內存為8 GB的Intel Core(TM) i5-7200U CPU 2.50 GHz的計算機上運行。

文獻[9]中認為發(fā)現(xiàn)者比例應占種群數(shù)量的10%–20%；安全閾值ST∈[0.5,1]；種群大小和迭代次數(shù)應與對比試驗保持相同設置，因此，SSA算法參數(shù)設定如下：工件總數(shù)為r，機器總數(shù)為k，種群大小為200，迭代次數(shù)為300，發(fā)現(xiàn)者比例為20%，追隨者比例80%，安全閾值為0.5，目標權重ω1=0.7，ω2=0.3。如表2所示。

表2 算法參數(shù)

為了檢驗算法的尋優(yōu)性能和證明算法在解決FJSP問題的可行性，使用實例一證明算法的可行性，使用實例二和實例三對SSA的性能進行比較。實例一是文獻[16]中同樣以最大完工時間和總負荷最小為目標函數(shù)的6×6實際案例；實例二和實例三是Kacem測試集中的3×4和4×5算例。

為驗證SSA在解決實際FJSP問題的可行性，使用文獻[16]中的實際生產(chǎn)車間的原始數(shù)據(jù)。文獻[16]中數(shù)據(jù)來自于某汽車公司總裝車間的生產(chǎn)數(shù)據(jù)，經(jīng)過取整處理后得到規(guī)模為6×6的實驗數(shù)據(jù)。將實例一數(shù)據(jù)代入本文算法中運算，結果與文獻[16]中tsPSO和CMABC算法得出的結果進行對比。表3為示例一實際案例的試驗結果。其中，加粗的結果表示同一算例下使用各算法得到的最優(yōu)值，“N/A”表示相關文獻中沒有給出這一算例的結果。

表3 實際案例實驗結果

結果表明，SSA算法仿真模擬的結果明顯好于其他兩種算法，還給出了與其他兩種算法完全不同的調度方案，增加了企業(yè)生產(chǎn)調度時的選擇方案。從單目標最優(yōu)值來看，SSA算法在Cmax、Wt兩個目標都得到了最優(yōu)解，使企業(yè)在選擇上更加靈活。將實例一的生產(chǎn)數(shù)據(jù)通過SSA運行，得到最優(yōu)解為：Cmax=12、Wt=41，證明了SSA在實際生產(chǎn)的可行性。圖3為實際生產(chǎn)數(shù)據(jù)最優(yōu)解的甘特圖。

圖3 實際案例甘特圖

采用Kacem I[17]設計的測試算例來驗證算法的有效性。將SSA算法與分布估計算法[18]、基于正態(tài)云的狀態(tài)轉移算法[19]及混合人工蜂群算法[20]的文獻中所提及的算例結果進行比較，證明SSA解決柔性車間調度問題的優(yōu)越性。測試結果如表4所示。其中，加粗的結果表示同一算例下使用各算法得到的最優(yōu)值，“N/A”表示相關文獻中沒有給出這一算例的結果。

表4 實際案例實驗結果

結果表明，對于Kacem1問題，SSA得到的3組解除了均優(yōu)于EDA得到的兩組解。從單目標最優(yōu)來看，SSA在Cmax、Wt兩個問題的最優(yōu)解分別為6和15，較其他算法具有較強的求解優(yōu)勢。對于Kacem2問題，雖然CSTA和SSA都得到了（11，32，17.3）的最優(yōu)解，但在解的數(shù)量上，SSA明顯優(yōu)于其他兩種算法，為實際調度的方案提供了更多選擇方式。從單目標最優(yōu)來看，SSA在Cmax、Wt兩個問題的最優(yōu)解分別為11和32，說明SSA具有較強的尋優(yōu)能力，能夠向組合后的單目標最優(yōu)解提供較多的選擇，證明了SSA在可行解數(shù)量和單目標可行解上的優(yōu)勢。圖4和圖5分別給出了Kacem1的最優(yōu)解（6，15，8.7）和Kacem2的最優(yōu)解（11，32，17.3）的最優(yōu)解的甘特圖。

圖4 Kacem1最優(yōu)解的甘特圖

圖5 Kacem2最優(yōu)解的甘特圖

4 結語

針對目前元啟發(fā)式算法在解決FJSP問題時存在收斂速度慢，易于陷入局部最優(yōu)的問題。由于SSA算法具有收斂速度快，尋優(yōu)能力強的特點，本文結合SSA算法提出了一種可以解決FJSP問題的SSA方法。以最大完工時間和總能耗為指標構建了作業(yè)車間調度模型，為了適應FJSP改變了SSA的編碼和解碼方式。最后，使用幾種FJSP的經(jīng)典算例驗證SSA解決FJSP的可行性，說明了SSA在求解FJSP的可行性和高效性。下一步將考慮將SSA應用于更多約束的車間調度問題上，解決更多實際生產(chǎn)問題。