基于改進Jaya算法的置換流水車間調(diào)度問題研究

劉夢伊，薛燕社，馬思奕，張超勇

(1.河海大學(xué) 商學(xué)院，江蘇 南京 211100；2.華中科技大學(xué) 機械科學(xué)與工程學(xué)院，湖北 武漢 430074)

置換流水車間調(diào)度問題（permutation flow shops scheduling problem,PFSP）在流程和離散制造企業(yè)廣泛存在。傳統(tǒng)PFSP可以描述為n個工件依次在m臺設(shè)備上加工的過程，n個工件在m臺設(shè)備上各加工一次，并且每個工件以相同加工的順序在設(shè)備上進行加工，每臺機器上所有任務(wù)的執(zhí)行順序都必須相同，通過優(yōu)化每臺機器上加工順序，使得最大完工時間最小。

針對上述傳統(tǒng)置換流水車間調(diào)度問題，許多學(xué)者進行了研究。例如Ruiz等[1]在求解最小化最大完工時間為目標(biāo)的PFSP時，設(shè)計了一種簡單有效的迭代貪婪算法。Govindan等 [2]在求解最小化最大完工時間為目標(biāo)的PFSP時，提出一種混合算法。湯可宗等 [3]提出一種多策略粒子群優(yōu)化方法，用以求解最小化最大完工時間為目標(biāo)的PFSP。該方法根據(jù)萬有引力值劃分的子區(qū)間，通過信息熵方式度量粒子群的多樣性；同時基于螞蟻路徑選擇，綜合考慮粒子間的距離和慣性質(zhì)量選出全局最優(yōu)粒子，為增強群體的全局搜索能力，另行設(shè)計了一種新穎的集合變異方式引導(dǎo)群體跳出局部最優(yōu)。Chen等[4]提出一種改進的離散粒子群優(yōu)化算法，用以求解最小化最大完工時間為目標(biāo)的PFSP。該算法提出新的粒子群學(xué)習(xí)策略，研究如何更加合理地應(yīng)用全局最優(yōu)解、局部最優(yōu)解來指導(dǎo)算法的搜索過程，為了防止搜索過程過早收斂，提出一種新的過濾局部搜索方法，對已審查的解區(qū)域進行過濾，并將搜索引導(dǎo)到新的解區(qū)域。張敏等[5]提出一種基于改進區(qū)塊鏈算法用于求解最小化最大完工時間的PFSP。Fernando等[6]在求解以總流程時間為目標(biāo)的PFSP時，提出一種有效的構(gòu)建式啟發(fā)算法。Karabulut等[7]在求解以最小化總延遲時間為目標(biāo)的PFSP時，提出一種混合IG算法。

Jaya算法由印度學(xué)者Rao[8]于2016年提出，其本質(zhì)是在求解過程中使所獲得的解不斷向最好解方向移動，并且遠(yuǎn)離最差解。與其他智能優(yōu)化算法相比，它的優(yōu)勢在于需設(shè)置的參數(shù)較少，原理簡單易懂，并且具有較強的尋優(yōu)能力。針對置換流水車間問題的特點，本文提出一種改進的Jaya算法來對PFSP進行求解，詳細(xì)介紹改進Jaya算法的實現(xiàn)過程，采用提出的改進Jaya算法對標(biāo)準(zhǔn)實例進行測試，并與其他算法進行對比，驗證該算法的有效性。

1 PFSP數(shù)學(xué)模型

在PFSP問題中，研究最多的目標(biāo)為最小化最大完工時間，其求解表達式如式(1)～(5)所示。

式中，n為工件總數(shù)；m為設(shè)備總數(shù)；FTi,j為工件i在設(shè)備j上的完工時間；PTi,j為工件i在設(shè)備j上的加工時間；f1為最大完工時間。

2 改進Jaya算法

2.1 離散化方式

置換流水車間實質(zhì)上是對n個加工工件序列進行排序。因此相對于標(biāo)準(zhǔn)Jaya算法無需考慮變量j，只考慮個體k和迭代次數(shù)i即可，改進Jaya算法（improved jaya algorithm,IJA）的迭代表達式可由式（6）表示。式中，k和i分別為個體和迭代次數(shù)；Gk,i+1為第k個個體在i+1代時所對應(yīng)的工序序列；Gk,i為第k個個體在i代時所對應(yīng)的工序序列；Gbest,i為種群在i代時所對應(yīng)的最佳工序序列；Gworst,i為種群在i代時所對應(yīng)的最差工序序列；r1和r2分別為Gk,i與Gbest,i和Gworst,i的相似度，當(dāng)Gk,i與Gbest,i或Gworst,i在相同的序列位置有相同的工件時r1=1，r2=1，沒有相同工件時r1=0，r2=0。

2.2 種群初始化

初始種群通常對算法對優(yōu)化結(jié)果有較明顯影響。一個好的初始種群往往可以使算法更快收斂到最優(yōu)解或近優(yōu)解，進而提升算法的效率。為保證初始種群同時滿足具有相對較優(yōu)解和和解廣泛分布性這兩個條件，本文采用啟發(fā)式算法和隨機生成的方式形成個體，并且要求初始種群中的個體各不相同。目前求解置換流水車間的啟發(fā)式算法有幾十種，其中NEH算法是求解FJSP最好啟發(fā)式算法之一。因此本文采用NEH算法作為初始種群中的啟發(fā)式算法。

為保證初始種群同時滿足具有相對較優(yōu)解和和解分布的廣泛性這兩個條件，第1代中的Gbest,i由NEH算法產(chǎn)生，Gworst,i為Gbest,i個體工件序列的逆序，其余個體則隨機產(chǎn)生。

NEH算法主要流程如下。

Step 1計算每個工件在所有設(shè)備上的總加工時間；

Step 2將工件1,2,...,n按照總加工時間遞減的順序進行排列，得到初始序列G0，其中，n為工件總數(shù)，設(shè)i=3；

Step 3選擇G0中的第1個工件，用第2個工件插入到第1個工件的前后兩個位置，分別計算各自的最大完工時間，然后選擇最大完工時間較小的序列，將其前后順序固定，保存到序列Gt中；

Step 4取G0中第i個工件插入到Gt中所有可能的位置，找到最大完工時間最小的序列并保存得到新的Gt序列；

Step 5i=i+1。若i≤n，轉(zhuǎn)到Step 3，否則，算法終止。

2.3 編碼與解碼

在PFSP中，所有工件以相同的加工順序依次在不同的設(shè)備上進行加工。根據(jù)這一特性，改進Jaya算法采用排列編碼的方式進行編碼，即將所有工件序號的排列當(dāng)作一個個體。例如，個體Gk={gk1,gk2,gk3,···,gkn}，其表達的含義為個體Gk中對應(yīng)的工件排序為 1,2,3,···,n。然后每個個體按照個體中工件的排列順序依次在設(shè)備1,2,3,···,m上進行加工。其中，1,2,3,···,m為設(shè)備的序號；m為總共有m臺設(shè)備。本文采用的解碼方式為排列解碼，按照先到先加工的的規(guī)則，依次為各個工件安排加工設(shè)備，重復(fù)操縱直到工件序列中最后一個工件完成在最后一臺設(shè)備上的加工。

2.4 個體更新方案

為確保Jaya算法趨近最優(yōu)解，遠(yuǎn)離最差解的核心思想不變，本文采用4種方式對除最優(yōu)、最差個體之外的個體進行更新，可以簡單概括為先刪除后插入、先保留后補全，具體表達式和步驟如方式1、方式2和方式3所示。最優(yōu)個體通過迭代貪婪算法進行更新，其步驟如方式4所示。

方式1先刪除Gk,i與Gworst,i相同序列位置相同的工件即r2=1；若Gk,i與Gworst,i相同序列位置無相同的工件即r2=0，則隨機刪除Gk,i中的j個工件，j為大于1小于工件總數(shù)1/2之間的隨機整數(shù)；最后將Gbest,i中對應(yīng)工件插入到Gk,i中的空缺位置，并且更新前后Gk,i不得完全相同。式(7)為表達式，其中，r1∈{0,1}。示意圖如圖1所示。

圖1 個體更新方式1Figure 1 Individual renewal mode 1

式中，Gks,i+1表示由第i代中的個體k更新后產(chǎn)生的新個體；表示刪除Gk,i與Gworst,i相同序列位置相同的工件；表示將Gbest,i中對應(yīng)的工件插入到Gk,i中的空缺位置，具體步驟如下。

Step 1尋找Gk,i與Gworst,i相同序列位置相同的工件，若有轉(zhuǎn)Step 2，若無轉(zhuǎn)Step 3。

Step 2刪除Gk,i與Gworst,i相同序列位置相同的工件，并將刪除工件后的Gk,i保存在Gkt,i（臨時個體）中，轉(zhuǎn)Step 4。

Step 3隨機刪除Gk,i中的j個工件，并將刪除工件后的Gk,i保存在Gkt,i中，轉(zhuǎn)Step 4。

Step 4用Gbest,i中的工件將Gkt,i中缺少的工件補全，迭代為新的個體Gks,i+1。

方式2首先保留Gk,i與Gbest,i相同序列位置相同工件即r1=1；若Gk,i與Gbest,i相同序列位置無相同的工件即r1=0，則隨機保留Gk,i中的j個工件，j為大于1小于工件總數(shù)1/2之間的隨機整數(shù)。再將Gworst,i中對應(yīng)工件按不同于Gworst,i中的順序插入到此時Gk,i的空缺位置中，并且Gk,i在更新前后不得完全相同。式（8）為表達式。其中，r2∈{0,1}。示意圖如圖2所示。

圖2 個體更新方式2Figure 2 Individual renewal mode 2

式中，Gks,i+1表示由第i代中的個體k更新后產(chǎn)生的新個體；表示Gk,i中保留Gk,i與Gbest,i中相同序列位置相同的工件；表示將Gworst,i中對應(yīng)工件按不同于Gworst,i中的順序插入到此時Gk,i的空缺位置中。具體步驟如下。

Step 1尋找Gk,i與Gbest,i相同序列位置相同的工件，若有轉(zhuǎn)Step 2，若無轉(zhuǎn)Step 3。

Step 2保留Gk,i與Gbest,i相同序列位置相同的工件，并將保留工件后的Gk,i保存在Gkt,i中，轉(zhuǎn)Step 4。

Step 3隨機保留Gk,i中的2個工件，并將保留工件后的Gk,i保存在Gkt,i中，轉(zhuǎn)Step 4。

Step 4用Gworst,i中的工件將Gkt,i中缺少的工件補全，迭代為新的個體Gks,i+1。

方式3為進一步增強種群間個體交流，將方式2中的Gworst,i變?yōu)镚rand,i，其中，Grand,i為第i代個體中除最優(yōu)、最差和自身個體外的一個隨機個體，其余操作和步驟與方式2相同。

方式4對當(dāng)代最優(yōu)個體行迭代貪婪搜索，其步驟如下。

Step 1從Gbest,i中隨機去除p個工件，形成，將刪除的工件按刪除順序組成，設(shè)置q=1；

Step 2從中取出第q個工件，插入到中任意位置，取目標(biāo)函數(shù)值最小的插入序列作為新的；

Step 3如果q＜p,q=q+1，轉(zhuǎn)到Step 2，否則終止操作，生成Gbest,i+1。

在迭代過程中可能會出現(xiàn)兩個極端情況，分別為Gk與Gbest完全相同或Gk與Gworst完全相同，會導(dǎo)致個體中出現(xiàn)重復(fù)個體，如果不能及時解決上述問題，可能會使迭代提前陷入局部最優(yōu)，不利于尋找最優(yōu)解。本文采取的措施是隨機交換Gk中兩個工件的位置，這樣不僅可以避免個體重復(fù)，還增加了種群的多樣性。

2.5 局部搜索

本文的局部搜索分為兩個階段，第1階段針對所有個體，第2階段僅針對最優(yōu)個體。

1）第1階段。

所有個體均采用4種鄰域結(jié)構(gòu)進行局部搜索，4種方式分別為向前插入、向后插入、隨機交換和中心反轉(zhuǎn)，如圖3所示。

圖3 4種鄰域結(jié)構(gòu)Figure 3 Four neighborhood structures

向前插入：隨機選擇兩個不同的工件，將工序中靠后的工件插入到另一個工件的前面。

向后插入：隨機選擇兩個不同的工件，將工序中靠前的工件插入到另一個工件的后面。

隨機交換：隨機選擇兩個不同的工件，將它們在工序中的位置進行前后交換。

中心反轉(zhuǎn)：隨機選擇兩個不同的工件，將這兩個工件的中心位置作為反轉(zhuǎn)的對稱軸，依次將對稱軸兩側(cè)包含這兩個工件以及這兩個工件之間的工件進行反轉(zhuǎn)。

第1階段的步驟如下。

Step 1令i=1，記個體為Gi，通過4種鄰域結(jié)構(gòu)分別對Gi進行局部搜索；

Step 2計算Gi的4種鄰域解的目標(biāo)值，選擇最好的鄰域解記為；

Step 3如果優(yōu)于Gi，則令替換Gi，否則Gi保持不變，令i=i+1；

Step 4若i＜n+1，則轉(zhuǎn)Step 1，否則結(jié)束局部搜索，其中，n表示種群中的個體總數(shù)。

2）第2階段。

對當(dāng)前種群中的最優(yōu)個體進行迭代貪婪搜索，通過其毀壞操作和構(gòu)造操作來對最優(yōu)個體進行進一步搜索，增大尋找到最優(yōu)解的概率。其步驟如下。

Step 1設(shè)定需要去除的工件個數(shù)p。

Step 2從Gbest中隨機去除p個工件，形成，將刪除的工件按刪除順序組成，設(shè)q=0；

Step 3從中取出第q個工件，插入到中所有可能的位置，取目標(biāo)函數(shù)值最小的插入序列作為新的；

Step 4如果q＜p,q=q+1，轉(zhuǎn)到Step 2，否則終止操作，生成G*best；

Step 5如果G*best的目標(biāo)函數(shù)值優(yōu)于Gbest，則令Gbest=G*best，否則Gbest保持不變。

2.6 多樣性控制策略

隨著種群中個體的不斷進化，每個個體將會變得越來越相似，這也意味著種群間的多樣性變得越來越差，進而導(dǎo)致搜索停滯，造成算法早熟。這里所稱相似度是指種群所有個體中同一工件出現(xiàn)在工件序列相同位置的情況。為避免這一現(xiàn)象的發(fā)生，本文采用算法重啟機制來增加種群中個體的多樣性。當(dāng)種群內(nèi)部的多樣性指標(biāo)低于某一門檻值β時，就在當(dāng)前種群的基礎(chǔ)上產(chǎn)生一個新種群，進而使算法在新種群的基礎(chǔ)上繼續(xù)進行搜索。這樣，就有可能增大算法跳出局部最優(yōu)的概率，從而開辟一個新的搜索空間。在新種群中，50%的個體由當(dāng)前種群中較好的前50%個體組成，另外50%的個體隨機產(chǎn)生。為評價種群的多樣性，本文使用的評價指標(biāo)為文獻[9]中提到的基于工件位置的矩陣表達式評價方法。

2.7 算法流程

本文求解最小化最大完工時間的流程如圖4所示。

圖4 改進Jaya算法流程Figure 4 Flow chart of improved Jaya algorithm

Step 1設(shè)置種群規(guī)模、終止條件等參數(shù)。

Step 2生成初始種群Pt，通過本文中提到的NEH算法和隨機的方式生成個體。

Step 3以最大完工時間最小為目標(biāo)值確定最優(yōu)和最差個體。

Step 4根據(jù)改進的Jaya迭代公式更新個體。除最優(yōu)和最差個體外，每個個體均采用方式1、2、3共3種方式來更新個體，更新后個體組成的種群為P't，將Pt和P't合并形成Qt。

Step 5以最大完工時間最小為目標(biāo)將Qt中的所有個體進行排序，取前n個個體組成新的種群NPt，其中，n為種群規(guī)模。

Step 6對NPt中所有個體采用4種鄰域結(jié)構(gòu)進行局部搜索，并進行個體更新，具體見第1階段局部搜索。

Step 7確定此時種群中新的最優(yōu)個體，并對該個體進行迭代貪婪搜索，更新最優(yōu)個體，具體見第2階段局部搜索。

Step 8如果div < 0.5，根據(jù)多樣性控制策略生成新的種群，如果div≥0.5，則保留現(xiàn)有種群。

Step 9在滿足終止條件前，循環(huán)執(zhí)行步驟Step 3～6，否則輸出結(jié)果。

3 實驗結(jié)果與分析

3.1 參數(shù)設(shè)置

改進的Jaya算法以C++為編程語言，在Visual Studio 2015開發(fā)環(huán)境中運行。所有實例在神州K650D上運行，筆記本參數(shù)為i7 4710MQ 2.50GHz四核CPU、12G內(nèi)存。通過對實例的大量測試，最終選擇初始種群大小為51，局部搜索的次數(shù)為Nmax=5，多樣性評價指標(biāo)的值div=0.5。

本文采用Car、Rec和Taillard實例[1]對算法進行測試，其中，8組Car實例、21組Rec實例和110個Taillard實例。算法的最長運行時間均設(shè)為0.3×n×m(s)，其中，n代表加工的工件個數(shù)；m代表所用到的設(shè)備數(shù)。每個實例均獨立運行10次。

3.2 結(jié)果分析

首先對Car實例和Rec實例用改進Jaya算法進行測試，其中8組Car實例均為小規(guī)模問題；21組Rec實例的規(guī)模從小到大分為7組，各組的實例規(guī)模相同。對比算法為文獻[10]提出的PSOVNS，文獻[11]提出的PSOMA和文獻[12]提出的L-HDE。采用最優(yōu)百分比偏差BRE和平均百分比偏差A(yù)RE對測試結(jié)果進行評價。計算公式為

其中，Si表示各算法在求解實例時得到的最好解；Sav表示算法在實例的10次運算過程中取得的平均解；UB表示實例的已知上界。從式（9）和式（10）的計算方式可得，當(dāng)各算法求解的BRE和ARE的值越小，說明算法的性能越好。測試結(jié)果統(tǒng)計如表1所示，表1中，n|m為實例的規(guī)模；平均值為各算法對29組實例求解結(jié)果和的均值。

從表1中可知，在29組實例中，IJA算法得到20個實例的上界，另外3種算法求解到實例上界的個數(shù)分別為11、16和18，IJA算法的平均BRE為0.20，另外3種算法的平均BRE分別為1.01、0.50和0.36，表明IJA算法在求解最優(yōu)解的性能上優(yōu)于另外3種算法，具有更強的尋優(yōu)能力。在29組實例中，IJA算法求得的ARE僅在Rec23和Rec25上略差于L-HDE算法，其余26組實例的ARE均優(yōu)于另外3種算法，IJA的平均ARE為0.33，另外3種算法的平均ARE分別為1.44、0.95 和0.55，表明IJA算法具有更好的穩(wěn)定性。

表1 基于Car和Rec實例的算法性能比較Table 1 Comparison of algorithm performance based on Car and Rec instances

為進一步測試算法的性能，本文還對110個Taillard實例進行了測試。Taillard實例中每10個實例為一組，每組內(nèi)的實例規(guī)模相同，實例規(guī)模從小到大依次遞增，最大實例規(guī)模為200工件和20設(shè)備。對比算法為文獻[13]提出的HMSA、文獻[14]提出的Proppsed和文獻[15]提出的PSOENT。測試結(jié)果如表2和3所示。表2中，Sbest為各算法求得對應(yīng)實例的最優(yōu)解，加粗的結(jié)果表示算法求解到了實例的上界，UB和BRE與表1中的含義相同。表3中的最優(yōu)解個數(shù)表示各算法在求解110個Taillard實例時求解到上界的個數(shù)，平均值表示在11組規(guī)模不同案例的ARE和的均值。

從表2可知，在110個Taillard實例中IJA求得了49個實例的上界，HMSA、Proppsed和PSOENT分別求得了0、23和31個實例的上界，表明IJA算法在求解最優(yōu)解的性能上優(yōu)于另外3種算法，具有比另外3種算法更強的尋優(yōu)能力。從表3中可知，無論是每組相同規(guī)模的平均BRE，還是全部11組共110個實例的平均BRE，IJA算法均優(yōu)于另外3種算法，表明IJA算法具有更好的魯棒性。

表2 基于Taillard實例的算法測試結(jié)果比較Table 2 Comparison of algorithm test results based on Tailard instances

續(xù)表

續(xù)表

表3 基于Taillard實例的算法穩(wěn)定性比較Table 3 Comparison of algorithm stability based on Tailard instaces

4 結(jié)論

本文針對以最小化最大完工時間為目標(biāo)的PFSP，提出一種改進的Jaya算法。改進Jaya算法通過NEH和隨機的方式產(chǎn)生初始種群，基于Jaya算法趨近最優(yōu)解、遠(yuǎn)離最差解的核心思想采用4種方式對個體進行更新，為進一步提高算法的局部搜索能力，采用4種鄰域結(jié)構(gòu)對所有個體進行局部搜索，同時還對每代個體中的最優(yōu)個體進行迭代貪婪搜索，使算法跳出局部最優(yōu)。為保證種群的多樣性，還加入了種群多樣性控制策略。最后通過對Car實例、Rec實例和Taillard實例進行測試，并與其他算法進行對比，證明本文所提算法在求解以最小化最大完工時間為目標(biāo)的PFSP時的有效性和魯棒性。