連裕翔，張超勇+，孟磊磊，薛燕社，詹欣隆，呂 暢

(1.華中科技大學 數(shù)字制造裝備與技術國家重點實驗室，湖北 武漢 430074；2.聊城大學 計算機學院，山東 聊城 252059)

0 引言

自改革開放以來，我國制造業(yè)蒸蒸日上，同時也暴露了許多資源協(xié)調(diào)利用、信息管理方面的缺陷，顯示出我國與國外在制造業(yè)水平之間的巨大差距，隨著中國制造2025的提出，這些問題更加突出，為提高制造企業(yè)的精細化、自動化科學管理能力，以在激烈的全球競爭中立于不敗之地，必須最大限度地利用現(xiàn)有資源，提高資源利用率，提升產(chǎn)品質量并縮短加工周期，在該過程中，生產(chǎn)調(diào)度顯得十分重要。在制造企業(yè)生產(chǎn)中，科學合理的調(diào)度可以提高制造過程的生產(chǎn)率和生產(chǎn)設備利用率，縮短產(chǎn)品的生產(chǎn)周期，減少資源浪費。經(jīng)典的作業(yè)車間調(diào)度問題(Job shop Scheduling Problem, JSP)是一種復雜的NP-hard組合優(yōu)化問題，其中每個工件的工藝路線不同，每個工序在指定的機器上加工，每個機器只能處理一種操作類型。然而，在實際制造企業(yè)的生產(chǎn)過程中，一道工序的加工往往有多個機器可以選擇，而且不同機器加工同一道工序的時間一般不同，該類問題屬于擴展的JSP，即柔性作業(yè)車間調(diào)度問題(Flexible Job shop Scheduling Problem, FJSP)。與JSP相比，F(xiàn)JSP減少了加工機器選擇約束，提高了工件加工的柔性，增大了搜索空間，是比JSP更復雜的NP-hard問題。

BRUCKER等[1]于1990年首先提出FJSP，并采用多項式圖形算法解決該問題。目前，求解FJSP的方法主要分為精確算法和近似算法兩類。精確算法包括數(shù)學建模、分支定界和整數(shù)規(guī)劃法等，例如，GOMES等[2]提出一種用于FJSP的新的整數(shù)線性規(guī)劃模型，并采用商業(yè)混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming, MILP)軟件解決該問題；ROSHANAEI等[3]為FJSP開發(fā)了兩種新穎的MILP模型。精確算法雖然能夠得到實例的最優(yōu)解，但是無法在短時間得到中、大規(guī)模FJSP實例的解，因此研究者開始越來越關注近似算法，特別是元啟發(fā)式算法，來求解FJSP。

元啟發(fā)式算法分為群體智能算法和局部搜索算法，群體智能算法包括蟻群優(yōu)化(Ant Colony Optimization, ACO)算法、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法和人工蜂群(Artificial Bee Colony, ABC)算法等；局部搜索算法包括禁忌搜索(Tabu Search, TS)、模擬退火(Simulated Annealing, SA)、可變鄰域搜索(Variable Neighborhood Search,VNS)等。WANG[4]提出一個有效的ACO算法解決FJSP，其中包括改進的信息素引導搜索和更新機制，以實現(xiàn)最優(yōu)的全局搜索；LI等[5]為多目標FJSP提出基于Pareto的ABC算法；GAO等[6]提出一種具有新工作插入的FJSP兩階段ABC算法；NOUIRI等[7]研究了考慮機器故障約束的FJSP，提出兩階段PSO解決以制造期和穩(wěn)定性為優(yōu)化目標的問題；ZHANG等[8]提出一種改進的FJSP遺傳算法，并取得良好的效果；DRISS等[9]提出一種遺傳算法，該算法采用新的染色體表示形式以及一些不同的FJSP交叉和突變策略；LI等[10]提出一種混合算法求解FJSP，采用GA進行全局搜索，TS進行局部搜索，對基準案例獲取了新解；NOURI[11]提出一種完整的多智能體模型，該模型集成了基于鄰域的遺傳算法和局部搜索技術，以提高解決方案的質量；趙詩奎[12]提出一種新的鄰域結構，在同機器工序移動N7鄰域的基礎上擴大鄰域，采用遺傳算法作為全局搜索，通過基準實例驗證算法的有效性。通過上述研究可以看出，群體智能算法通常具有強大的全局搜索能力，但是局部搜索能力有限；相反，局部搜索算法具有很強的單點搜索能力。因此，融合群體智能算法與局部搜索算法各自優(yōu)勢的混合優(yōu)化算法，通常具有更強的搜索能力。

Jaya算法由RAO[13]于2016年提出，是一種連續(xù)優(yōu)化問題的解決方法，與經(jīng)典的遺傳算法、PSO算法相同，都屬于群體智能算法。該算法通過公式使解遠離差解、靠近優(yōu)秀解來獲取新解，在過去幾年已應用于各種優(yōu)化問題，如微電網(wǎng)調(diào)度問題[14]、置換流水車間調(diào)度問題[15]、城市交通信號控制問題[16]和柔性流水車間調(diào)度問題[17]。GAO等[18]采用Jaya算法求解考慮工件插入的動態(tài)FJSP，并與其他啟發(fā)式方法進行比較，實驗結果證明了該算法的優(yōu)越性；Rylan等[19]提出一種基于Jaya的混合算法求解FJSP最小化最大完工時間問題，創(chuàng)造性地提出一種針對FJSP的Jaya算法離散化方法，并對FJSP基準案例獲得了較好解。Jaya算法的優(yōu)點是無需調(diào)整算法參數(shù)，只需根據(jù)具體問題設計相應的迭代操作，被認為是求解組合優(yōu)化問題的一種魯棒、有效的算法。同遺傳、PSO等經(jīng)典群體智能算法一樣，Jaya算法的局部搜索能力較弱，需要引入針對問題特性的局部搜索算法。

本文針對FJSP的特點，融合Jaya算法與TS算法，提出一種改進Jaya算法求解FJSP。在提出的改進Jaya算法中，設計了一種改進的離散Jaya算法操作機制來迭代候選解解集，并基于相似度和適應度的解評價方法來提高Jaya算法的搜索能力；同時，設計了一種結合N7鄰域結構[20]和M.G.鄰域結構[21]的TS算法，以提高混合算法在全局和局部搜索的能力。采用所提算法求解著名的FJSP基準實例，驗證了算法的優(yōu)越性。

1 FJSP描述

傳統(tǒng)FJSP描述為：n個工件J={J1,J2,…,Jn}在m臺機器M={M1,M2,…,Mm}上加工；不同工件Ji包含ni道工序{Oi,1,Oi,2,…,Oi,ni}，一個工件上所有工序按照一定的加工順序進行加工；每道工序有可選加工機器集合Mi,j，Mi,j={Mi,j,1,Mi,j,2,…,Mi,j,k}，Mi,j?M；調(diào)度的目標是確定全部工序的加工次序和所選用的機器，使最大完工時間等指標最優(yōu)。本文以最大完工時間Cmax(makespan)最小為指標，設Ci為工件Ji的完工時間，則Cmax最小的目標函數(shù)為

Cmax=min{max(Ci)},i=1,2,…,n。

(1)

加工過程需要滿足如下約束條件：①每個機器同一時間只能加工一個工序；②每個工件同一時刻只能在一臺機器上加工；③每個工件具有相同的優(yōu)先級；④每道工序一旦開始就不能中斷；⑤同一工件的工序存在先后約束，不同工件的工序不存在先后約束；⑥每一個工件在零時刻都可以加工。

由以上約束可以看出，作為JSP中衍生出來的拓展問題，F(xiàn)JSP既集成了JSP的部分特點，也具有自己本身的特點。其中FJSP與JSP相似，都需要確定工件在各個機器上的加工順序，即工序排序問題；與JSP不同的是，F(xiàn)JSP存在機器柔性，允許一道工序選擇多個機器進行加工，同時其存在循環(huán)排列的特性，一個工件的多道工序可以被同一臺機器加工多次。傳統(tǒng)的JSP已經(jīng)被證明為NP-hard問題，F(xiàn)JSP在JSP的基礎上增加了機器柔性，減少了工序與機器之間的約束，大大提升了求解的空間。一個工件數(shù)(n)為3和機器數(shù)(M)為4的FJSP實例如表1所示。

表1 3×4的FJSP問題實例

2 改進Jaya算法求解FJSP

2.1 傳統(tǒng)Jaya算法

傳統(tǒng)Jaya算法是RAO等[13]提出的一種元啟發(fā)式算法，其基于持續(xù)改進的原理，將個體向優(yōu)秀個體靠攏的同時不斷遠離差的個體，從而提高解的質量。傳統(tǒng)Jaya算法通過方程式(2)迭代進化獲取新解，不像其他進化算法需要許多參數(shù)，該算法只需針對特定問題調(diào)整迭代過程的參數(shù)(如rbest，rworst)，避免了因調(diào)整參數(shù)過多而使測試不易實施的問題。與其他元啟發(fā)式算法相比，Jaya算法更容易理解和實現(xiàn)。

rworst,i,j,t(Xworst,j,t-|Xi,j,t|)。

(2)

式中：i表示種群中的第i個個體，i=1,…,n；j表示個體的第j維變量，j=1,…,m；t表示當前迭代的代數(shù)；X，X′分別為第t代第i個個體在第j維上更新前和經(jīng)過Jaya公式迭代計算后的值；rbest，rworst是[0,1]之間的隨機數(shù)，通過調(diào)整這兩個參數(shù)大小，調(diào)整算法逼近最優(yōu)解的能力；Xbest,j,t，Xworst,j,t分別為第t代最優(yōu)最差個體在第j維上的值；rbest,i,j,t(Xbest,j,t-|Xi,j,t|)將當前個體朝當代最優(yōu)解的方向進化，-rworst,i,j,t(Xworst,j,t-|Xi,j,t|)將當前個體朝遠離當代最差解的方向進化。如果采用式(2)生成的新個體的適應度比原始個體優(yōu)秀，則用新個體代替原始個體，否則不替換，然后對下一個個體進行Jaya迭代，直到遍歷完所有個體。然而FJSP是一個離散問題，不能直接采用傳統(tǒng)Jaya的迭代方式，如果將Jaya算法應用于求解FJSP，則必須對其進行離散化操作。

本文提出改進Jaya算法求解FJSP：①為了將傳統(tǒng)Jaya算法應用于FJSP，本文采用文獻[23]提出的離散化方法；②根據(jù)文獻[23]出的離散化公式，結合FJSP的編碼特點(兩層編碼)，提出4種Jaya迭代過程；③針對最小完工時間容易出現(xiàn)局部最優(yōu)的問題，結合Jaya靠近最好解、遠離差解的思想，提出一種相似度接受準則；④針對FJSP中具有機器柔性的特點，即一個工序的移動可以在所處機器上完成，也可以在多個機器上完成，將在JSP中效果優(yōu)異的N7鄰域結構與已證明在FJSP表現(xiàn)優(yōu)秀的M.G.鄰域結構結合[20-21]，并采用TS算法求解。改進Jaya算法包括編碼與解碼、種群初始化、Jaya解集生成與解的選擇、TS算法和改進算法框架等。

2.2 編碼與解碼

編碼是解的基因表達，編碼的優(yōu)劣直接影響算法解的質量。FJSP編碼需要確定給定加工工序的排序，并給工序分配相應的加工機器，因此編碼包括工序編碼和機器編碼兩部分。

一個3工件在4臺機床加工的編碼如圖1所示。工序編碼和機器編碼的長度為各工件加工步之和。加工序列表示為(O2,1,O3,1,O1,1,O2,2,O1,2,O1,3,O3,2,O3,3)，Oi,j表示第i個工件的第j道工序。對于機器序列，按照工件1、工件2、工件3的順序，可以解釋為工序O1,1,O1,2,O1,3對應機器M1,M1,M4，工序O2,1,O2,2對應機器M3,M1，工序O3,1,O3,2,O3,3對應機器M2,M2,M4。

解碼方法為：首先按照工序序列順序，將工序一個個添加到對應的機器分組上；然后，再次遍歷工序序列，根據(jù)工件最大開始時間(即前工序結束時間與機器前工序結束時間之間的最大值)將工件分配到機器上；最后，采用插入式貪婪解碼獲取主動調(diào)度解。

2.3 種群初始化

種群初始化對算法解的質量有重要影響，一個優(yōu)秀的種群初始化算法對種群多樣性、種群子代解有積極的影響。因此，在混合算法初始解的機器選擇上，80%的個體采用KACEM等[22]于2002年提出的根據(jù)全局加工時間最短選擇機器的方法，20%個體的機器采用隨機選擇的方式產(chǎn)生；工序序列采用完全隨機的方式生成。

2.4 Jaya迭代

傳統(tǒng)Jaya算法適用于解決連續(xù)優(yōu)化問題，而FJSP是一種典型的離散優(yōu)化問題。因此，本文在文獻[23]的離散化Jaya迭代方程基礎上，提出一種擴展的離散Jaya算法求解FJSP。文獻[23]的離散化Jaya迭代方程為

i=1,2,…,Npop;

(3)

從式(3)可知，r2Xbest,t使當前解靠近最優(yōu)解，r3Xworst,t使當前解遠離最差解，r4Xrandom,t可以提升迭代過程中尋優(yōu)的可能。因此本文在式(3)的基礎上，充分利用r2Xbest,t，r3Xworst,t，r4Xrandom,t對迭代個體的影響，提出一種應用于FJSP的離散Jaya迭代方式。該迭代方式包括4個迭代過程，迭代過程生成的解組合成為候選解解集，通過一定篩選排序，從解集中獲取最優(yōu)秀的解X′。該迭代方法可以在保證可行性的同時實現(xiàn)Jaya迭代中的“靠近”與“遠離”。

根據(jù)式(3)，解集Seti由以下4種方式生成：

(1)根據(jù)文獻[19]，刪除當前解中與差解相同的序列，用最好解替換，如圖2和圖3所示。具體步驟如下：

步驟1找出Xi,t與Xworst,t中工序序列相同的點，以及Xi,t與Xworst,t中機器序列相同的序列。

步驟2刪除Xi,t中工序序列相同的點和機器序列相同的點，保存在Xi,t,new中。

步驟3對于Xi,t,new中空缺的點，用與Xbest,t相對應的點進行替換。

步驟4將Xi,t,new放入Set{}，得到Set{…Xi,t,new}。

(2)刪除好解與差解相同的序列，用當前解替換，如圖4和圖5所示。具體步驟如下：

步驟1找出Xbest,t與Xworst,t中工序序列相同的序列，以及Xbest,t與Xworst,t中機器序列相同的序列。

步驟2刪除工序序列相同的序列和機器序列相同的序列，其余保存在Xi,t,new。

步驟3對于Xi,t,new中空缺的序列，用與Xi,t相對應的序列進行替換。

步驟4將Xi,t,new放入Set{}，得到Set{…Xi,t,new}。

(3)將好解與當前解進行交叉操作：

采用改進的優(yōu)先操作交叉(Improved Precedence Operation Crossover, IPOX)進行工序交換，如圖6所示，具體步驟如下：

步驟1將工件集J={J1,J2,…,Jn}隨機分成兩個集合B1和B2。

步驟2將Xbest,t中工序編碼屬于集合B1的序列替換到Xi,t,new的工序序列上。

步驟3將Xi,t中工序編碼屬于集合B2的序列按順序依次替換到Xi,t,new工序序列的空白處。

采用多父輩交叉(Multi-Parent Crossover,MPX)操作進行機器交換，如圖7所示，具體步驟如下：

步驟1產(chǎn)生一系列由0和1組成的隨機數(shù)數(shù)組R，數(shù)組長度與編碼長度相同。

步驟2選出Xbest,t和Xi,t中與數(shù)組R元素1位置相同的元素，將其互換，獲得Xi,t的機器序列即為Xi,t,new的機器序列。

(4)將當前解與其他解(非最好解和最差解)進行交叉操作，與方式(3)類似。

在解集生成方式(1)和方式(2)中，會遇到兩種極端情況，即兩個個體完全相似和兩個個體完全不相似，這兩種情況會生成一個重復的個體，這個解可能是Xi,t，也可能是Xbest,t或Xworst,t。如果不及時處理所生成的重復解，則有可能使種群出現(xiàn)大量重復解，從而陷入局部最優(yōu)。對于完全相似的情況，本文采用丟棄策略，采用重新初始化策略生成一個新的個體；對于完全不相似的情況，本文采用方式(3)，在保證不陷入局部最優(yōu)的同時豐富種群多樣性。

2.5 接受準則

Jaya算法具有自身的局限性，當采用某種單一目標時(如最小化完工時間)，雖然能引導個體靠近目前最優(yōu)個體，但是該最優(yōu)個體不一定是全局最優(yōu)，從而陷入局部最優(yōu)。因此本文采用一種新的個體選擇方式保證種群的多樣性，以提高算法的搜索能力。本文的選擇策略結合最大相似度和最小加工時間兩種方法，即90%的概率選擇最小加工時間，10%的概率選擇最大相似度。相似度計算方法如下：

考慮到Jaya迭代方程的目的是獲取一個靠近優(yōu)解、遠離差解的新解，如何評價“靠近”與“遠離”尤為重要。此前研究大多采用優(yōu)化的目標值，即通過目標值與最優(yōu)解的靠近程度來評價靠近與遠離的程度，這種方法雖然可以在適應值上靠近優(yōu)解，但是適應值相近并不代表解的形式靠近優(yōu)解，或是攜帶優(yōu)秀解的成分，因此本文引入一種新的評價靠近程度的方法，即相似度。闡述相似度計算之前，先介紹如何計算兩個解的距離。本文將兩個解X1與X2之間的距離用海明距離(Hamming distance)表示，即D(X1,X2)，

(4)

xd(i,j)=

(5)

式中x1(i,j)和x2(i,j)分別表示X1和X2在第j臺機器上第i個加工的工件號。

為了達到靠近優(yōu)解、遠離差解的目的，提出相似度計算公式

DSimilar=D(Xi,Xworst)-D(Xi,Xbest)。

(6)

式中：D(Xi,Xbest)表示Xi與Xbest的距離，D(Xi,Xworst)表示Xi與Xworst的距離，D(Xi,Xbest)越小越好，D(Xi,Xworst)越大越好。本文的相似度計算過程如圖8所示。

2.6 局部搜索算法

為了進一步提高算法的求解能力，本算法采用TS算法對個體進行局部搜索。TS算法是求解調(diào)度問題非常有效的一種局部搜索方法，其通過對已經(jīng)搜索過的鄰域解進行一定時長禁忌來減少對無效解的搜索，并通過特赦準則跳出局部最優(yōu)。TS算法主要包括禁忌對象、禁忌表、禁忌長度、特赦準則、終止準則、鄰域結構，其中鄰域結構的優(yōu)劣直接影響TS算法的搜索能力。

為了令TS算法更充分地發(fā)揮作用，本文結合FJSP具有機器柔性的特點將搜索分為變機器鄰域和同機器鄰域兩部分，TS算法中對這兩種鄰域分別采用不同的鄰域結構和禁忌表。針對變機器鄰域，采用文獻[21]提出的鄰域結構與快速評價策略，該鄰域結構可以極大縮少解的空間，且具有連通性。變機器鄰域搜索步驟如下：

步驟1計算每個工序的最早開始時間StartTime(O)和最短尾時間TailTime(O)。

步驟2選取關鍵工序v，并將工序v的加工時間置為0。

步驟3重新計算每個工序的最早開始時間_StartTime(O)和最短尾時間_TailTime(O)。

步驟4從v的可選機器集合M(J,O)中選擇其他機器k，設Qk為機器k上所有加工工序的集合，并計算Qk上的兩個集合Rk和Lk：

Rk={x∈Qk|StartTime(x)+px≥

StartTime(PJ(v))+pPJ(v)}；

(7)

Lk={x∈Qk|TailTime(x)+px≥

TailTime(SJ(v))+pSJ(v)}。

(8)

式中：PJ(v)為工序v的工序緊前工序；SJ(v)為工序v的工序緊后工序。

本文變機器采用的鄰域即為以上最優(yōu)插入的集合，快速評價策略在文獻[21]中有詳細說明。禁忌對象采用(v,k)表示，其中v為被移動的工序，k為工序被移動之前的加工機器。針對同機器鄰域，采用文獻[20]提出的N7鄰域和快速評價策略，禁忌對象采用工序序列(u,…,w,…,v)及其在機器上的位置(pu,…,pw,…,pv)，在給定的禁忌長度內(nèi)禁止，具體請參見文獻[20]。

禁忌長度的設置與迭代代數(shù)有關，基本長度為10，禁忌長度TabuLength=10+rand((iterMax-iter)/NM)，其中NM為工件數(shù)與機器數(shù)之積。從禁忌長度的公式可以看出，隨著迭代次數(shù)的增大，禁忌表的長度變小，跳出局部最優(yōu)的能力得到提高。當?shù)玫降男陆鈨?yōu)于當前最優(yōu)解時滿足特赦準則，如果不滿足特赦準則，則在未被禁忌的解中選擇最優(yōu)解。當所有解均被禁忌時，采用文獻[21]的選擇策略。當TS算法迭代次數(shù)到達最大迭代次數(shù)時，算法終止。本文設計的TS算法流程如圖9所示。

2.7 混合Jaya算法流程

本文針對FJSP的特點，提出一種融合TS算法的改進Jaya算法(Improved Jaya Algorithm and Tabu Search, IJA-TS)，其中Jaya算法負責全局搜索，TS算法對部分優(yōu)秀個體進行局部搜索?；旌纤惴鞒虉D如圖10所示?；旌纤惴ú襟E如下：

步驟1設置種群參數(shù)、終止條件、工件數(shù)量、機器數(shù)量、加工時間等。

步驟2對種群進行初始化。

步驟3計算種群每個個體的適應值，將適應值最高的個體標記為Xbest，將適應值最低的個體標記為Xworst。

步驟4用改進的Jaya迭代公式求解，為每個個體生成相應的迭代候選解解集Seti。

步驟5如果解集中存在Xnew適應值比Xi大，則將Xnew替換到Xi+1，轉步驟9，否則執(zhí)行步驟6。

步驟6生成一個0～1的隨機數(shù)Random，如果Random≤0.9，則執(zhí)行步驟7，否則轉步驟8。

步驟7將解集Seti中適應值最大的Xnew替換到Xi+1，轉步驟9。

步驟8計算解集Seti中的相似度，將相似度最大的Xnew替換到Xi+1，然后執(zhí)行步驟9。

步驟9對種群中前10%的個體進行禁忌搜索。

步驟10判斷是否到達終止條件，是則執(zhí)行步驟11，否則轉步驟4。

步驟11輸出結果。

3 實驗結果與分析

本文所提改進Jaya算法采用VS2017 C++語言編程，運行環(huán)境為Intel I7四代CPU，主頻2.6 GHz，內(nèi)存16 G，操作系統(tǒng)為Window 8.1專業(yè)版。為了驗證所提創(chuàng)新點，本文進行兩組試驗：①驗證接受準則的有效性；②驗證局部搜索的有效性。為了驗證所提算法的性能，本文選擇BRdata[24]，DPdata[25]，BCdata[26]基準問題對算法進行測試。為了顯示所提算法的優(yōu)越性，本文選取其他各類具有代表性的算法進行比較，包括提出禁忌搜索求解FJSP的M.G.的TS[21]以及混合算法中的HA[10]，hA-INS[12]，CROTS[27]。本文算法是對文獻[19]Jaya算法迭代方程的改進，因此與該文獻的結果進行比較。為了衡量算法性能，采用相對百分比偏差RE的平均值MRE描述算法能力，RE=(Cmax-LB)/LB×100%，其中LB是實例的下界。

3.1 接受準則有效性驗證

為了驗證所提接受準則的有效性，本文將對無局部搜索的改進Jaya算法與無局部搜索、最小完工時間接受準則的改進Jaya算法進行比較。這兩個算法采用相同的算法框架，差別在于接受準則，IJA-WTS表示本文所提的接受準則接受新解(無局部搜索)，IJS-WTS-MA表示采用最小加工時間接受新解(無局部搜索)。設置種群為50，迭代代數(shù)為500，每個案例求解10次，將兩個算法應用在BRdata中，得到結果如表2所示。表中：AVG為10次所得解的平均值；MRE為相對百分比偏差RE的平均值。

表2 接受準則的比較

由表2中各個案例的均值可見，采用所提接受準則的IJA-WTS結果優(yōu)于采用最小完工時間接受準則IJA-WTS-MA的結果，IJA-WTS的MRE=0.049，IJA-WTS-MA的MRE=0.054，驗證了所提接受準則的有效性。原因是最小加工時間接受準則容易過早陷入局部最優(yōu)，而將相似度接受準則與最小加工時間接受準則混合能夠增加種群的多樣性，幫助算法跳出局部最優(yōu)。

3.2 局部搜索有效性驗證

為了驗證所提局部搜索的有效性，本文對改進Jaya算法(IJA-TS)與無局部搜索改進Jaya算法(IJA-WTS)進行比較。這兩個算法均采用相同的算法框架，差別在于有無局部搜索。算法設置種群為50，迭代代數(shù)為500，每個案例求解10次，將兩個算法應用在BRdata中，得到結果如表3所示。

表3 有無局部搜索的比較

續(xù)表3

從表3可見，有局部搜索與無局部搜索對算法的影響非常大，添加了局部搜索后，所提算法的求解質量與結果有了很大提升，其中IJA-WTS僅有4個案例的均值達到下界，IJA-TS有8個均值達到下界。因為本文的局部搜索采用了變機器鄰域中比較有效的M.G.鄰域，在同機器鄰域中采用在JSP應用十分有效的N7鄰域，充分發(fā)揮了TS算法的局部尋優(yōu)能力。

3.3 算法性能測試與分析

3.3.1 參數(shù)設置

改進Jaya算法中的參數(shù)比較少，主要有迭代種群、禁忌搜索迭代代數(shù)、禁忌基準長度。根據(jù)多次實驗，本文設置迭代種群為50，禁忌搜索迭代代數(shù)為1 000，禁忌基準長度為10，每個算例求解10次，迭代次數(shù)為500代。

3.3.2 計算結果與分析

本文對BRdata[24]，DPdata[25]，BCdata[26]算例的計算結果分別如表4～表6所示。HA，hA-INS，IJA，CROTS分別為文獻[10，12，19，27]的混合算法，TS為文獻[21]的TS算法；Cmax為算例求解10次得到的最大完工時間的最優(yōu)值；AVG為算例求解10次得到的平均值；CPUtime為迭代過程中運行500代的平均時間(如果獲得下界值則為獲得下界值的時間)；表中“*”表示獲得實例的最優(yōu)解。表7所示為不同算法針對不同測試實例的MRE值。因為不同文獻中算法測試時的硬件環(huán)境、算法停止條件等不同，有些文章并未給出算法時間，所以本文不對求解時間進行對比。

表4 BRdata基準實例集測試結果比較

表5 DPdata基準實例集測試結果比較

續(xù)表5

表6 BCdata基準實例集測試結果比較

表7 各算法計算不同實例集的MRE比較

由表4～表6可見，針對BRdata和BCdata實例，本文算法可以求得所有實例的當前最好解，明顯優(yōu)于其他算法。與當前最新文獻的IJA算法相比，在BRdata實例中，本文算法獲得9個實例的下界，IJA算法只獲得8個實例的下界；針對DPdata實例，本文算法有9個實例的結果好于IJA算法；針對BCdata算例，本文算法的結果與IJA算法持平。由表5可見，本文算法測試3個基準問題實例集的MRE值最小，為0.54，HA算法的MRE=0.63，TS算法的MRE=0.74，IJA算法的MRE=0.67，這是因為本文算法對Jaya的迭代過程進行改進，添加了迭代候選解解集，增加了迭代過程產(chǎn)生較優(yōu)解的可能，改進了評價近優(yōu)解的方法，提高了種群多樣性，從而能夠避免陷入局部最優(yōu)，使Jaya算法迭代效果更好。所提算法與M.G.和HA算法比較，在BRdata，DPdata，BCdata 3個基準實例集中，本文算法獲得的結果均優(yōu)于或等于M.G.和HA算法。圖11～圖13所示分別為實例Mk06，Mk10，Seti5×××最好解的甘特圖。

4 結束語

本文針對FJSP提出一種融合TS算法的改進Jaya算法，并給出改進Jaya算法的框架。Jaya算法具有簡單、快速的特點，但容易陷入局部最優(yōu)，本文基于離散Jaya算法公式，擴展Jaya迭代解的生成方式，設計了Jaya迭代候選解集，以及一種相似度和最大完工時間結合的評價方式，在保證種群多樣性的同時進一步提了高Jaya算法的求解能力；在TS算法中，對同機器采用張超勇的鄰域結構[20]，對變機器采用M.G.的鄰域結構[21]，以進一步提高算法的局部搜索能力，使混合算法在分散搜索和集中搜索之間達到平衡。通過用基準問題實例測試所提算法，并與其他算法的結果比較，證明了混合算法的有效性和優(yōu)越性。

未來研究可以通過擴展Jaya算法迭代獲取新解的方式，改進評價“靠近”與“遠離”的方法，融合更有效的鄰域搜索，來進一步提高算法的求解性能，同時解決其他擴展類型調(diào)度問題。