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

楊紅雄 王惠酩

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

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

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

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

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

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

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

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

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

1.2 數學模型

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

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

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

k：機器總數，共有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的完全柔性作業車間加工時間表

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

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

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

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

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

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

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

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

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

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

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

1.3 雙目標優化

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

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

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

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

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

因此，目標函數可以表示為

其中：ω1+ω2=1。

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

2 求解FJSP的SSA流程設計

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

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

2.1 編碼與解碼

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

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

圖1 編碼方式

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

2.2 SSA算法步驟

2.2.1 種群初始化

設定算法的各部分參數如最大迭代次數、種群數量、發現者比例和安全閾值等。

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

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

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

2.2.2 發現者的位置更新

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

則麻雀i的位置可以記作

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

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

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

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

2.2.3 追隨者的位置更新

追隨者的位置更新公式為

2.2.4 偵察預警行為

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

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

算法的具體步驟如下：

Step1：輸入算例的數據。

Step2：初始化種群，如設定麻雀種群中發現者的數量、意識到危險的麻雀所占種群的比例。

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

Step4：根據式（13）、（14）更新發現者、追隨者位置。

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

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

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

圖2 算法流程圖

3 仿真測試

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

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

表2 算法參數

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

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

表3 實際案例實驗結果

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

圖3 實際案例甘特圖

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

表4 實際案例實驗結果

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

圖4 Kacem1最優解的甘特圖

圖5 Kacem2最優解的甘特圖

4 結語

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