求解柔性作業車間調度問題的新型改進Jaya算法

裴小兵，祁文博，戴毓彤

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

在現代制造系統中，調度管理問題一直被人們認為是能夠直接影響企業生產經濟效益的一個關鍵問題，生產調度主要指通過有效合理利用現有資源來不斷提高企業生產效率。柔性作業車間調度問題（flexible job shop scheduling problem，FJSP）擴展了調度問題搜索空間，增加了車間調度操作的靈活性，相較于其他傳統作業生產車間，在調度管理問題方面更貼近于實際生產狀況，是近年來制造生產車間調度管理領域的重要研究發展熱點。為解決FJSP，許多學者采用了不同類型的智能優化算法。顧幸生等[1]在自創的問題編解碼方案上建立博弈集，結合粒子群算法提出一種改進博弈粒子群算法。王家海等[2]設計了一種有效的鄰域結構并講其與進化算法結合。Li等[3]以使更優化最大求解完工后時間為目標，提出一種可以結合禁忌搜索算法的遺傳算法來求解FJSP，并由此得到了幾個對于基準問題相對新的最優解。Hao 等[4]提出一種可變長度的染色體編碼方式，針對非支配排序遺傳算法提出了自適應分層策略，仿真實驗表明該改進算法可以提高生產效率。姜天華[5]首次提出了混合灰狼優化算法，將遺傳算子和變鄰域搜索策略相結合。田旻等[6]針對遺傳算法求解FJSP的不足，設計了一種分層混合遺傳算法，將種群劃分為兩層并結合鄰域搜索進行調節。Nouri 等[7]提出了一個集成基于鄰域的遺傳算法和局部搜索技術的整體多智能體模型，以提高解的質量。Shen等[8]開發了一種改進的禁忌搜索算法，以解決具有序列相關設置時間的FJSP，同時考慮了最小化完工時間的性能度量。實驗分析結果表明，與其他實驗算法相比，該實驗方法仍然具有顯著的性能優越性。

從以上研究中可以看出，元啟發式方法已經越來越多地被用于解決FJSP 問題，由于FJSP 的復雜性和多約束性，利用算法優化求解的時間過長成為實時調度策略的主要障礙。在不同的方法中，元啟發式算法具有計算時間合理、求解質量高等優點。Rao[9]于2016 提出了一種新的元啟發式算法Jaya，并將其應用于諸多領域的優化問題中。在文獻[9]中，Jaya 與幾種存在的mete 啟發式優化算法分別進行了實驗比較，實驗和討論結果驗證了其中Jaya 算法的有效性。與現有的大多數元啟發式算法相比，Jaya算法的優勢和競爭力在于不需要調整任何特定的參數，只需要種群規模和迭代次數等常用控制參數以達到最優。并且在相對較少的函數求值次數下提供了最優結果。Jaya 算法的局限性在于無法有效地探索解空間中的區域，容易陷入局部最優解。Gao等[10]以快速最小化柔性機器工作時間負載長度為目標，采用Jaya算法快速求解柔性作業車間調度問題，與國內現有的新型啟發式算法結果進行了比較，實驗結果證明了該新型算法的技術優越性。Rylan等[11]在Jaya算法的基礎上又引入有效的局部搜索技術，提出了一種算法I-Jaya，以最大完工時間為主要性能指標，比較了這種I-Jaya算法與其他常用元啟發式算法的不同性能，驗證了該類算法的性能有效性。然而，通過查閱文獻可知，由于Jaya算法提出時間較晚，國內運用Jaya求解柔性作業車間調度問題的研究還較少，且運用Jaya求解調度問題仍有很大的改進空間。

綜上所述，本文針對Jaya算法易陷入局部最優的缺點，提出一種結合變鄰域搜索的新型改進Jaya 算法（new improved Jaya algorithm，NIJA），它有望在解決FJSP方面取得良好的性能。該算法首先用一種混沌序列與均勻分布相結合的混合策略產生初始種群，以達到保證初始種群多樣性并提高初始種群質量的目的。然后結合Jaya 算法的原理提出一種更新機制實現種群進化，然后執行交叉操作持續改善種群。針對Jaya算法的缺點，結合變鄰域搜索算法中有效的局部搜索機制，設計新的鄰域結構強化搜索的過程，擴大搜索范圍，避免算法陷入局部最優。此外，提出一種接受準則引導搜索空間的新區域，從而提高解的質量。最后經由算例與數值實驗證明了所提方法的可行性和有效性。

1 柔性作業車間調度問題描述

FJSP 可以由n個工件(J1,J2,…,Jn)在m臺機器(M1,M2,…,Mm)上加工，每道工序可以在一臺或者多臺機器上進行加工，這些工序將按預先確定的順序在加工機器上加工，作業加工時間包括運輸時間時間時間和機器設置時間[12]。對于FJSP，包含以下兩個相關子問題，即確定各個工件的加工加工加工機器和確定各個機器上的加工順序，以最小化最大完工時間為目標，其問題約束如下：

（1）同一時刻，每臺機器只能加工一個工件，每個工件只能在一臺機器上加工。

（2）各個工件在各臺機器上的加工時間已知。

（3）各道工序一旦開始加工，中途就不能停止。

（4）每個工件只能在每臺機器上進行一次加工。

（5）各工件在零時刻都可以被加工。

根據FJSP的問題假設，其模型相關符號如下所示。

公式（2）保證它們之間的優先關系，即上一個工序完成后才可進行下一道工序；公式（3）確保任一道工序的完工時間減開始時間等于其加工時間，即工序一旦開始就不能中斷；公式（4）約束每臺機器每次只能加工一道工序；公式（5）限定了每個工件的完工時間不可能大于總完工時間；公式（6）確定最大完工時間。

2 Jaya算法

Jaya是Rao[9]于2016年提出的一種新型元啟發式算法。它的工作原理是持續改進，即解決方案趨向于朝著最優解的方向移動而遠離最差解。Jaya 算法是一種單階段算法，每次迭代只需對一個方程進行求值即可得到新解的值[13]。它還有一個優點，就是它是一種無參數算法，只需要種群規模和迭代次數兩個控制參數。因此，優化參數用來獲得最優解時所需的額外計算工作量被消除。與其他元啟發式算法相比，Jaya算法易于理解和實現。Jaya算法的基本步驟簡述如下：

步驟1 初始化種群大小，設計變量數量和終止標準。

步驟2 識別種群中最優解與最差解。

步驟3 按公式（7）在最優解和最差解的基礎上得到更新解。

步驟4 將更新解與之前的解進行比較，若更新解更好則將其替換，否則保留舊方案。

步驟5 判斷是否滿足終止標準，若滿足則報告最優解，否則返回步驟2。

3 新型改進Jaya算法

Jaya 算法的局限性在于無法有效地探索解空間中的區域，容易陷入局部最優解[14]。為了克服這一問題，本文提出一種新型改進Jaya算法。首先，該算法使用混合策略產生具有優勢的初始種群，并設計了一種新的種群更新機制，對機器分配和工序排序進行了進化，向著最優解移動。然后基于相似度進行交叉操作，并運用變鄰域搜索以增強挖掘鄰近解的能力和保持多樣性的能力，從而獲得更好的解。最后提出了一種接受準則，來改善種群多樣性，從而防止早期收斂。

3.1 整體算法流程框架

算法流程框架如圖1所示，其基本步驟描述如下：

圖1 算法流程框架Fig.1 Algorithm flow diagram

步驟1 設置參數，如種群大小、終止條件、工件數、機器數、工序數及相關處理時間。

步驟2 應用組合策略初始化種群。

步驟3 評估適應度，并得出所有候選解He并計算其目標函數值Ce；確定最高函數值Ce,lbest和最低函數值Ce,lworst，并將對應的兩個候選解標記為Hbest和Hworst。

步驟4 使用Jaya 算法的更新機制得到新的候選解He+1并計算目標值Ce+1。

步驟5 判斷是否滿足Ce+1＜Ce，若滿足則用He+1代替He，否則轉步驟6。

步驟6 檢查是否滿足接受標準，若滿足則用H代替He，否則保留當前解。

步驟7 計算相似度，執行交叉操作。

步驟8 將變鄰域搜索機制應用于每個候選解以進一步篩選。

步驟9 判斷是否滿足終止標準，若滿足則轉到步驟11，否則轉步驟10。

步驟10 返回步驟3直至滿足終止標準。

步驟11 輸出最優解。

3.2 編碼

一個可行解應包含定義問題所涉及的所有方面，本文使用一種雙層編碼策略，以3個工件，9個工序，4個機器的問題為例，如圖2所示。每個數組的結構長度轉換為工序總數，該例中工序順序為（O21，O31，O11，O32，O12，O22，O13，O33，O23）。工序順序上的數組表示工件索引，機器分配數組表示分配機器的索引，所述索引來自可選機器集，相同索引表示同一工件的前后工序。

圖2 編碼示意圖Fig.2 Coding schematic

3.3 初始化種群

初始種群的質量對算法產生最優解的過程有著很大的影響[15]，本文采用一種隨機分布與混沌序列相結合的混合策略產生初試種群，使候選解隨著迭代次數的增多而趨于全局均勻分布。該操作主要分為兩個階段，工序排序階段和機器分配階段，每一道工序的機器都采用混沌序列的方法從可選機器集中產生，根據混沌序列公式生成偽隨機序列。在此過程中實時統計所有機器的被使用次數并計算使用次數均值，當某臺機器的使用次數達到平均值，則優先使用其他機器處理該工序，這樣可保證機器負荷平衡。不斷重復上述步驟，直至生成完整初始種群。具體步驟描述如下：

步驟2 對每個工序隨機產生一個rand值，其中rand∈[0,1] ，根據rand值的大小對所有工序進行升序排序，如圖3所示。

圖3 工序排序Fig.3 Operation sequencing

步驟3 對機器分配隨機產生一組數值，通過公式pn+1=μpn(1 -pn)，其中μ∈( 0,4],pn∈( 0,1) ，生成具有混沌特性的隨機序列，依據一一映射在可選機器集中，確定機器編碼。

步驟4 統計所有機器的被使用次數，若某機器已達到平均被使用次數，則該工序優先使用其他機器。

3.4 個體位置更新機制

Jaya算法基于一個原則：目標函數的解朝著最優解移動而遠離最差解[16]。根據這些概念提出一種適用于FJSP 的更新機制，既通過從一組可選機器中分配適當機器，之后再確定工序順序進行求解[17]。通過消除與最差個體對應的編碼并在保持可行性的同時合并最佳個體編碼來修改個體，生成更新解，實現種群進化[18]。

3.4.1 機器分配更新機制

首先計算當前種群中所有可行解的目標函數值，找出最優值Ce,lbest與最差值Ce,lworst，并找出對應的候選解決方案Hbest和Hworst，執行更新機制，如圖4所示，圖中數組為相應分配機器的索引，首先確定候選解He與最差解Hworst之間相同的機器并從中刪除，然后將Hbest相應位置的機器放入He中，生成新的候選解He+1。以此類推，更新所有候選解。確定機器分配的Jaya更新機制主要步驟如下：

圖4 機器分配更新機制Fig.4 Updating mechanism for machine assignment

步驟1 在Hbest和Hworst之間確定相同編碼的加工機器并從He中刪除。

步驟2 將He中剩余的機器復制到He+1相應位置中。

步驟3 復制Hbest的相應位置的機器放到He+1的空白位置中。

步驟4 根據相應可行機器集檢查更新解He+1的可行性，若不可行，則在可選機器集范圍內隨機分配一個機器。

3.4.2 工序排序更新機制

與機器分配更新機制原理相似，提出了工序排序的Jaya更新機制，找出最優值Ce,lbest與最差值Ce,lworst以及對應的解決方案Hbest與Hworst，圖5中數組為相應工件索引，確定候選解He與最差解Hworst之間相同位置的工件并從中剔除，然后將He剩余工件復制到He+1中的相應位置。剔除Hbest中He的剩余工件，最后將Hbest的剩余工件添加到He+1的空白位置中，生成新的工序順序從而生成候選解He+1。保證了調度的可行性，從而消除了調度修復過程，減少了計算量，其主要步驟如下：

圖5 工序排序更新機制Fig.5 Updating mechanism for operation sequencing

步驟1 在He和Hworst之間確定相同的分配工件并從He中刪除。

步驟2 將He中剩余的工件復制到He+1中。

步驟3 從Hbest中刪除He+1中的剩余工件。

步驟4 復制Hbest的相應工件放到He+1的空白位置中。

3.5 交叉操作

交叉算子本質上是通過搜索解空間中的新區域來改善候選解，一個好的交叉算子應該能夠有效地在后續種群之間交換信息[19]。目前文獻中廣泛使用的是基于優先保持順序的POX 交叉。但通過實驗可以觀察到，在搜索過程后期，工序序列向量中具有相似位置的元素，這使得交叉操作趨于無效化。為克服這一缺點，本文提出一種基于相似度的SPOX 交叉。為有助于交叉操作幾件維護與父代之間的聯系，基于相似性的遞減值將工件分配給子代，這也有助于提高搜索過程的收斂性。每個工件相似度由公式（8）計算得到：

其中Ii表示兩個工序順序編碼中具有相同工件分配的位置總數，Ji表示工件i的總工序數。如圖6 所示，圖中數組為相應工件的索引，工序順序交叉操作過程如下：

圖6 工序排序交叉操作Fig.6 Operation of operation cross

步驟1 根據公式（8）計算He+1與He各工件的Xi值。

步驟2 若所有Xi都等于各工件工序數，則執行步驟3，若Xi值都等于0 則執行步驟4、6，否則執行步驟5、6。

步驟3 隨機選擇一個工序Oi，插入子代的第一個基因位，將受影響的工序向后移動，指導Oi的位置。

步驟4 隨機分配一半的工件給子集Ht。

步驟5 根據Xi的遞減值將一半的工件分配給子集Ht。

步驟6 將屬于子集Ht的工件從He+1中插入子代相同位置，將子集Ht的其余工件從He中從左到右依次插入子代。

如圖7 所示，圖中數組為相應分配機器的索引，機器分配的交叉操作通過當前He+1與舊種群He生成新的子代，過程如下：

圖7 機器分配交叉操作Fig.7 Machine assignment cross operation

步驟1 選擇兩個隨機數k1和k2，使1 ≤k1＜k2＜Ji，k1和k2分別表示要交換的元素集合開始與結束的位置。

步驟2 將He中k1到k2位置上的元素復制到子代中相應位置，He+1中所有其他元素追加到相應位置。

步驟3 檢查可行性，若不可行，則在可選機器集范圍內隨機分配一個機器。

3.6 變鄰域搜索算法

變鄰域搜索算法是一種有效的局部搜索算法，它在搜索過程中的基本思想為，在當前解的不同鄰域之間切換來擴展搜索范圍以進行局部尋優，避免陷入局部最優解[20]。

為進一步提高算法的搜索能力，每次迭代都采用變鄰域搜索機制，從而達到減少計算量的同時生成質量更高的解。變鄰域搜索的本質在于通過鄰域的系統變化來搜索解空間。事實上，隨機選擇編碼進行逆序操作功能允許兩個領域結構中的每一個隔離自己的探索區域，而協作機制啟動多個搜索，隨機變化最佳解決方案信息，從而加速探索過程[21]。因此，設計幾個覆蓋整個解決方案空間的鄰域結構是必要的[22]。考慮到解決方案表示和特定問題的特征，本文在運用傳統的交換、插入鄰域結構的基礎上，又設計了兩種鄰域結構N2、N3，以實現鄰域搜索。

（1）鄰域結構N1：插入，在任意一個OS編碼段上隨機選擇兩個位置，將靠后位置的工件插入到靠前位置的工件前，前一位置之后的工件按順序向后順延，如圖8中（a）所示。

（2）鄰域結構N2：在任意一個OS 編碼段上隨機選擇x個位置，其中1 ＜x≤3 ，且x個位置上的編碼不完全相同，將x個編碼位置上的編碼順序進行逆序操作，生成鄰域解，如圖8（b）所示。

（3）鄰域結構N3：隨機在任意一個OS 編碼段內選擇一個編碼位置，判斷該位置編碼與前一相鄰位置的編碼是否相同，若相同，則將其與后鄰編碼交換，若不同則繼續判斷該位置的編碼與后一相鄰位置的編碼是否相同，若相同，則將其與前鄰編碼交換；若不同，則將其與前后相鄰位置的編碼進行隨機變化。變換機制如圖8（c）所示。

圖8 鄰域結構變換機制Fig.8 Transformation mechanism of neighborhood structure

3.7 接收準則

針對最大完成時間值大于當前解的生成解，給出了一個可接受準則，該接收準則與模擬退火中的準則相似，但在方程中消除了溫度參數，從而消除了調整參數的過程。這一操作通過在解空間中探索新的區域搜索有希望的解，以幫助改善種群多樣性，防止早期收斂[23]。建議的接受準則為：

其中Cmax是當前解的最大完工時間值，C′max是新解的最大完工時間值，rand表示[ ]0,1 中隨機生成的數字。將最大完工時間值的相對偏差作為驗收度量，偏差越小，接受具有更高最大完工時間值的新解的概率越高。

4 仿真實驗

本研究采用MATLAB 軟件實現，程序在處理器為Intel Core i5 處理器，2.11 GHz 主頻，16 GB 內存，操作系統為64位Windows10的計算機上運行。將提出的方法與文獻中的幾種算法在makespan和計算時間方面做了詳細比較。考慮參數值如表1所示。

表1 參數設置Table 1 Parameter setting

4.1 變鄰域搜索有效性驗證

為了驗證本文所提出方法的求解過程的有效性，將本文所提算法與無局部搜索的Jaya 算法，針對算例MK09進行仿真實驗，算法的收斂過程如圖9所示，圖中實線為NIJA，虛線為Jaya。可以注意到NIJA 在第142次迭代中收斂到最佳完工時間，而Jaya在181次迭代中收斂到最佳完工時間，收斂曲線表明，在搜索空間內執行提出的變鄰域搜索，由于搜索過程的加強，最大完工時間逐漸減小。

圖9 MK09算例收斂圖Fig.9 Convergence graph of MK09

4.2 算法有效性驗證

為進一步驗證本文所提出方法的求解過程的有效性，分別針對算例Kacem[24]和算例Brandimarte[25]進行驗證，運用新型混合Jaya算法獨立運行30次，并將取得的最優值Cmax與其他文獻中算法的最優值進行對比。

首先對Kacem的8×8、10×10、15×15的3個算例進行驗證比較，包括改進Jaya算法（IJA）[11]、改進變鄰域算法（IVNS）[26]、MBBO[27]、IACO[28]。通過表2可知，該算法所求得的Cmax值與其他算法最優解都沒有偏差，證明了該方法的有效性和穩定性，且在求解時間上，該算法明顯優于其他算法。算法求解結果的各甘特圖分別如圖10～12。

表2 Kacem算例對比結果Table 2 Comparison results of Kacem example

圖10 8×8甘特圖Fig.10 8×8 Gantt chart

圖11 8×10甘特圖Fig.11 8×8 Gantt chart

圖12 10×10甘特圖Fig.12 10×10 Gantt chart

表3 Brandimarte算例對比結果Table 3 Comparison results of Brandimarte example

5 結束語

Jaya算法是一種無參數算法，其優點是算法結構簡單，可應用性強，能夠在較少的求解次數下提供最優結果，但容易過早收斂并陷入局部最優。由于求解FJSP的復雜性，用單一的搜索算子很難有效地解決問題。該算法將初始化與基于Jaya 的更新機制、交叉算子、變鄰域搜索融合在一起，強調在尋優過程中種群的多樣性。為此，本文提出了一種新型改進Jaya算法。（1）對初始解的產生方式進行了改進，以保證初始種群的多樣性。（2）利用Jaya 算法的原理提出新的更新機制，找出優勢基因，進化種群，降低求解復雜性。（3）提出一種基于相似度的交叉操作，改善種群多樣性防止早期收斂。（4）結合變鄰域搜索算法設計了一種局部搜索機制，克服了Jaya算法的缺點，使搜索過程的廣度與深度得到平衡。

本文針對算例進行仿真并驗證了該算法在解決FJSP上能夠獲得較穩定的解，同時提高了求解效率。由于Jaya算法提出時間較晚，國內運用Jaya求解柔性作業車間調度問題的研究還較少，且運用Jaya求解大規模調度問題仍有很大的改進空間。未來研究中，將考慮與其他智能優化算法相結合，并應用其他類型的組合優化問題。