吳樹(shù)景，游有鵬，羅福源

南京航空航天大學(xué) 機(jī)電學(xué)院，南京210016

1 引言

柔性作業(yè)車(chē)間調(diào)度問(wèn)題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）是當(dāng)前智能制造及工業(yè)自動(dòng)化領(lǐng)域研究的熱點(diǎn)問(wèn)題，在離散制造業(yè)、流程工業(yè)中應(yīng)用廣泛。FJSP 是典型的NP-hard 問(wèn)題，工藝約束較多，每個(gè)工件的每道工序都可在可選擇的有限臺(tái)機(jī)器上加工，計(jì)算復(fù)雜性高。目前求解FJSP常用的智能優(yōu)化算法包括遺傳算法、蟻群算法、粒子群算法、模擬退火算法、禁忌搜索算法等。

遺傳算法（Genetic Algorithm，GA）是一種模擬自然進(jìn)化機(jī)制的全局優(yōu)化算法[1]，優(yōu)化過(guò)程不受限制性條件的約束，全局搜索能力很強(qiáng)，但存在穩(wěn)定性差、爬山能力弱、易陷入局部最優(yōu)等缺點(diǎn)。周頔[2]融合了遺傳策略和蟻群策略，有效提升了擇優(yōu)能力和求解精度。宋存利[3]采用貪婪策略對(duì)GA 算子進(jìn)行改進(jìn)，增強(qiáng)了局部尋優(yōu)能力。

變鄰域搜索（Variable Neighborhood Search，VNS）算法是一種高效的局部?jī)?yōu)化算法[4]，它旨在通過(guò)不同鄰域的遞進(jìn)式排查，在反復(fù)迭代中使當(dāng)前的局部最優(yōu)解向最優(yōu)解進(jìn)一步靠攏，局部搜索能力很強(qiáng)。VNS算法在深入搜索的過(guò)程中采用多個(gè)而非單個(gè)鄰域結(jié)構(gòu)，因此可獲得比固定鄰域局部搜索算法更強(qiáng)的尋優(yōu)能力和搜索效率[5]。崔琪等[6]提出了改進(jìn)混合變鄰域搜索的遺傳算法，設(shè)計(jì)了“兩點(diǎn)交換”“反轉(zhuǎn)逆序”“打亂互換”等五種鄰域結(jié)構(gòu)，提升了解集質(zhì)量。王丹敬等[7]設(shè)計(jì)了自適應(yīng)變鄰域搜索算法，利用“2-insertion”等鄰域快速獲得高質(zhì)量的近優(yōu)解。

目前大部分優(yōu)化算法的盲目性和隨機(jī)性較強(qiáng)，與FJSP的特點(diǎn)聯(lián)系弱，穩(wěn)定性差。由上述文獻(xiàn)分析可知，GA 與VNS 算法構(gòu)成極好互補(bǔ)，二者融合可有效增強(qiáng)FJSP 求解性能。而國(guó)內(nèi)此方面的研究較為匱乏，主要體現(xiàn)有：遺傳算子跳坑能力不足，自適應(yīng)性弱；缺乏優(yōu)良個(gè)體保護(hù)機(jī)制；很多鄰域本質(zhì)為枚舉，當(dāng)問(wèn)題規(guī)模變大時(shí)待試探的可行解集規(guī)模也會(huì)呈指數(shù)上升，尋優(yōu)效率極大降低。故遺傳算子優(yōu)化及鄰域設(shè)計(jì)方面仍有很大提升空間。

本文結(jié)合GA 全局搜索能力強(qiáng)和VNS 算法局部?jī)?yōu)化效果好的特點(diǎn)，將GA與VNS算法相結(jié)合以平衡尋優(yōu)的廣度與深度。同時(shí)，對(duì)GA 算子進(jìn)行改進(jìn)，并引入保優(yōu)記憶庫(kù)策略對(duì)精英個(gè)體進(jìn)行保護(hù)。其次，針對(duì)FJSP的特點(diǎn)設(shè)計(jì)了三種基于關(guān)鍵工序進(jìn)行調(diào)整的鄰域結(jié)構(gòu)，給出了改進(jìn)的關(guān)鍵工序?qū)ふ曳▌t和甘特圖向編碼映射的工序調(diào)整方案。最后，通過(guò)算法測(cè)試與數(shù)值實(shí)驗(yàn)，采用基準(zhǔn)算例與其他現(xiàn)有算法進(jìn)行橫向測(cè)評(píng)，證明所提算法的可行性與有效性。

2 FJSP數(shù)學(xué)模型

n 個(gè)工件(J1,J2,…,Jn)要在m 臺(tái)機(jī)器(M1,M2,…,Mm)上加工；每個(gè)工件包含一道至多道工序；每道工序可在多臺(tái)不同機(jī)器上加工；不同機(jī)器加工各道工序的時(shí)間不同。由此，F(xiàn)JSP問(wèn)題本質(zhì)上由兩個(gè)子問(wèn)題組成：機(jī)器選擇和工序排序。

本文選取“最大完工時(shí)間Cmax最小”作為優(yōu)化目標(biāo)，如式（1）所示：

式中，Cj為第j 個(gè)工件最后一道工序的完成時(shí)間，Cmax為全部工件中最大的完工時(shí)間即最大完工時(shí)間（makespan）。優(yōu)化目標(biāo)的約束條件如下：

其中：

式中，cik和cjk分別為工件i 和j 在機(jī)器k 上的完成時(shí)間，cih為工件i 在機(jī)器h 上的完成時(shí)間，tik和tjk分別為工件i 和j 在機(jī)器k 上的加工時(shí)間；M 是一個(gè)足夠大的正數(shù)；aihk為決定工序先后順序的決策變量，xijk為工序分配機(jī)器的決策變量。

式（2）表示順序約束條件，保證每個(gè)工件的加工順序滿足預(yù)先的要求。

式（3）表示資源約束條件，即機(jī)器加工各工件的先后順序，限定每臺(tái)機(jī)器一次只能加工一個(gè)工件。

3 變鄰域保優(yōu)遺傳算法

本文綜合遺傳算法的全局搜索優(yōu)勢(shì)與變鄰域搜索算法的局部搜索優(yōu)勢(shì)，加入改進(jìn)的保優(yōu)記憶庫(kù)策略，提出了基于操作編碼的變鄰域保優(yōu)遺傳算法。

3.1 整體流程框架

整體算法流程框架如圖1所示。

圖1 整體算法流程框架圖

算法具體步驟如下：

步驟1 使用GLR機(jī)器選擇法[8]對(duì)種群進(jìn)行初始化，生成質(zhì)量?jī)?yōu)秀的初始解集。

步驟2 判斷當(dāng)前迭代次數(shù)N 是否已達(dá)最大迭代次數(shù)MAXGEN 。若是，則輸出最優(yōu)解或近似最優(yōu)解；否則，繼續(xù)執(zhí)行步驟3。

步驟3 執(zhí)行遍及賭輪選擇操作，生成子代種群。

步驟4 根據(jù)交叉概率Pc選取進(jìn)行交叉的個(gè)體，再根據(jù)交叉方式選擇概率Pv采用以下兩種方式中的一種執(zhí)行交叉操作：子代種群中個(gè)體兩兩進(jìn)行交叉，子代種群和外部保優(yōu)記憶庫(kù)中各選一枚個(gè)體進(jìn)行交叉。

步驟5 根據(jù)變異概率Pm選取進(jìn)行變異的個(gè)體，執(zhí)行變異操作。

步驟6 對(duì)全部個(gè)體執(zhí)行變鄰域搜索，用優(yōu)良解替代劣解。

步驟7 執(zhí)行精英保留策略，選取當(dāng)前代新種群中的較優(yōu)個(gè)體更新保優(yōu)記憶庫(kù)，對(duì)精英個(gè)體進(jìn)行保護(hù)。

步驟8 每隔Nd迭代次數(shù)對(duì)種群進(jìn)行一次擾動(dòng)，以隨機(jī)選擇的方式生成擾動(dòng)比例Pd乘以種群規(guī)模數(shù)量的新個(gè)體，并替換當(dāng)前代種群中同數(shù)目的較差個(gè)體，以此增強(qiáng)種群的活躍性和豐富度，防止陷入局部最優(yōu)解。

3.2 染色體編碼與解碼

本文采用MSOS染色體編碼方案[9]，如圖2所示，編碼由兩部分組成：機(jī)器選擇部分（Machines Selection，MS）和工序排序部分（Operations Sequencing，OS）。機(jī)器選擇部分各基因位依次按照工件及工件工序的順序排列，基因位的值表示該工序選擇的加工機(jī)器在可選機(jī)器集中的序號(hào)；工序排序部分各基因位值為工件號(hào)，某一位置上工件號(hào)已出現(xiàn)的次數(shù)代表屬于該工件的工序號(hào)。

圖2 FJSP染色體編碼示例圖

解碼時(shí)采用文獻(xiàn)[8]給出的前沿貪心方式解碼成活動(dòng)調(diào)度，目的是盡量將工序安排至對(duì)應(yīng)機(jī)器的最早可行加工時(shí)刻，將整體調(diào)度的最大完工時(shí)間縮至最短。

3.3 遺傳算法

3.3.1 種群初始化

本文采用GLR機(jī)器選擇初始化的方式[8]，包含全局選擇（Global Selection，GS）、局部選擇（Local Selection，LS）和隨機(jī)選擇（Random Selection，RS）。GS旨在從全局的角度保證所有加工機(jī)器負(fù)載均衡；LS 旨在從各工件獨(dú)立的角度保證所有加工機(jī)器負(fù)載均衡，以提高機(jī)器的利用率；RS 旨在使初始種群盡量地分布于整個(gè)解空間，提高種群多樣性。三者按各自比例均勻作用于初始種群中的個(gè)體，可顯著提高初始種群中的染色體在MS部分的質(zhì)量。

3.3.2 選擇算子

本文對(duì)傳統(tǒng)的輪盤(pán)賭選擇算子進(jìn)行了優(yōu)化，改進(jìn)為遍及賭輪選擇算子，如圖3所示。給定參數(shù)GGAP為子代和父代種群大小差異的代溝比例，為賭盤(pán)均勻設(shè)置數(shù)目等同于子代所需個(gè)體數(shù)的多個(gè)取樣指針，旋轉(zhuǎn)一次即可根據(jù)適應(yīng)度值篩選得出整個(gè)子代種群，在保證選擇結(jié)果分布均勻的前提下有效提升選擇效率。

圖3 遍及賭輪選擇

3.3.3 交叉算子

本文在選擇交叉操作執(zhí)行的個(gè)體時(shí)，根據(jù)式（7）所示的交叉方式選擇概率Pv,N 為當(dāng)前迭代次數(shù)，MAXGEN 為總迭代次數(shù)，P 為隨機(jī)生成概率。分別選用兩種交叉方式：P ＞Pv時(shí)，子代種群中個(gè)體兩兩進(jìn)行交叉；P ＜Pv時(shí)，子代種群和外部保優(yōu)記憶庫(kù)中各選一枚個(gè)體進(jìn)行交叉。

Pv隨N 變化的曲線如圖4 所示，可看出：前期Pv較大，多采用第二種交叉方式，以此快速尋找到較優(yōu)解，提升收斂速度；后期Pv較小，多采用第一種交叉方式，以此增加新個(gè)體產(chǎn)生的機(jī)會(huì)，避免陷入早熟的陷阱。

圖4 交叉方式選擇概率Pv 圖形

詳細(xì)交叉策略如下：

機(jī)器選擇（MS）部分采用均勻交叉操作，如圖5 所示，交換兩父代染色體n 個(gè)隨機(jī)位置點(diǎn)處的基因片段。

工序排序（OS）部分采用改進(jìn)的POX 交叉方法[10]，如圖6 所示，劃分工件集為兩個(gè)非空集合，其中一集合中工件工序的基因在兩父代染色體中保持不變，順序交換兩父代染色體另一集合中的基因。

圖5 均勻交叉

圖6 改進(jìn)POX交叉

3.3.4 變異算子

機(jī)器選擇（MS）部分采用隨機(jī)分配可選機(jī)器的操作[11]，如圖7所示，隨機(jī)選擇n 個(gè)基因位（n 不大于MS部分編碼長(zhǎng)度的1/4），用其對(duì)應(yīng)可選加工機(jī)器替換。

圖7 MS部分變異

工序排序（OS）部分采用插入變異的方式執(zhí)行變異操作，如圖8 所示，在工序編碼中隨機(jī)選取一個(gè)基因并將其插入至OS部分的一個(gè)隨機(jī)位置上。

圖8 OS部分變異

3.3.5 保優(yōu)記憶庫(kù)策略

傳統(tǒng)遺傳算法中交叉算子的作用個(gè)體全部來(lái)自于子代種群，此機(jī)制有兩個(gè)明顯的缺點(diǎn)：一是每輪迭代產(chǎn)生的優(yōu)秀個(gè)體因得不到及時(shí)保護(hù)而易在下一輪迭代中被破壞；二是算法易過(guò)早收斂于局部最優(yōu)解而導(dǎo)致早熟。本文針對(duì)該弊端提出一種改良的保優(yōu)記憶庫(kù)機(jī)制，將搜索過(guò)程中的精英個(gè)體加入庫(kù)中進(jìn)行保護(hù)，留待供下一輪迭代進(jìn)行交叉操作。

為使保優(yōu)記憶庫(kù)中的精英個(gè)體盡可能分布均勻且種類(lèi)豐富，引入“海明距離”的概念：兩個(gè)染色體編碼中相異的基因位的個(gè)數(shù)稱作海明距離，簡(jiǎn)稱H 。

將精英個(gè)體更新至保優(yōu)記憶庫(kù)的算法流程如圖9所示，其中Ht為待插入個(gè)體的海明距離，Hn為保優(yōu)庫(kù)中第n 個(gè)個(gè)體的海明距離。

3.4 變鄰域搜索算法

圖9 保優(yōu)記憶庫(kù)更新流程圖

本文以關(guān)鍵工序?yàn)檎{(diào)整對(duì)象，機(jī)器空閑時(shí)間為突破點(diǎn)縮減最大完工時(shí)間的思想構(gòu)建鄰域，在趙詩(shī)奎[12]、王磊[13]等學(xué)者的研究基礎(chǔ)上進(jìn)一步改進(jìn)：優(yōu)化了關(guān)鍵工序的提取效率，拓展了空閑時(shí)間的搜索范圍，提出了甘特圖向編碼映射的工序調(diào)整方案，融合了單工序與雙工序的調(diào)整策略。由此提出三種鄰域結(jié)構(gòu)：同機(jī)器工序調(diào)整鄰域、變機(jī)器工序調(diào)整鄰域和雙工序調(diào)整鄰域。

3.4.1 變鄰域搜索流程

變鄰域搜索流程如圖10所示，先進(jìn)行單工序調(diào)整，隨機(jī)選擇“同機(jī)器工序調(diào)整”和“變機(jī)器工序調(diào)整”中的一個(gè)鄰域先執(zhí)行，再執(zhí)行另一個(gè)；然后執(zhí)行雙工序調(diào)整。根據(jù)鄰域搜索操作執(zhí)行后個(gè)體的目標(biāo)函數(shù)值進(jìn)行取舍：若執(zhí)行后的個(gè)體目標(biāo)函數(shù)值優(yōu)于原個(gè)體直接替換，差于原個(gè)體不替換，相等則以50%概率進(jìn)行替換。

圖10 變鄰域搜索流程

3.4.2 關(guān)鍵工序提取改進(jìn)方案

析取圖中從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑為關(guān)鍵路徑，對(duì)應(yīng)于甘特圖中工序間無(wú)時(shí)間間隔的最長(zhǎng)路徑，組成關(guān)鍵路徑的工序?yàn)殛P(guān)鍵工序，其直接決定調(diào)度方案的最大完工時(shí)間。因此在鄰域中對(duì)關(guān)鍵工序而非任意工序進(jìn)行調(diào)整可減少搜索的盲目性，極大提高找到更優(yōu)解的概率。由于每個(gè)個(gè)體進(jìn)行變鄰域搜索前都需對(duì)關(guān)鍵工序進(jìn)行提取，故高效的提取方案對(duì)于整體算法快速求解尤為重要。

反向查找[13]是較為常用的關(guān)鍵路徑提取方案，如圖11所示，其原理是：從最后完工的某一工序開(kāi)始向前執(zhí)行地毯式試探，同時(shí)遇到其工件前續(xù)工序和機(jī)器前續(xù)工序時(shí)取其工件前續(xù)工序，直到完整拼湊出緊密連接的最長(zhǎng)路徑。此方法在規(guī)模較小的算例下效率較好，但隨著問(wèn)題規(guī)模增大，可試探的路徑數(shù)量呈指數(shù)增加，搜尋效率和穩(wěn)定性均會(huì)急劇下降。

圖11 關(guān)鍵路徑反向查找法

圖12 關(guān)鍵工序鎖定特性

如圖12 所示，在工序安排順序和最大完工時(shí)間不變的前提下，受到屬于同一工件/機(jī)器的前/后工序的最早/晚開(kāi)工/完工時(shí)間約束，關(guān)鍵工序會(huì)被鎖定，而非關(guān)鍵工序可在一定區(qū)間內(nèi)自由移動(dòng)。根據(jù)這一特性，本文提出一種較大規(guī)模算例下搜索速度和質(zhì)量均較好的關(guān)鍵工序提取方案，相關(guān)符號(hào)變量說(shuō)明如下：sE(h)為工序Oh的最早開(kāi)工時(shí)間，sL(h)為工序Oh的最晚開(kāi)工時(shí)間，cE(h)為工序Oh的最早完工時(shí)間，cL(h)為工序Oh的最晚完工時(shí)間；PJ(h)為工序Oh屬于同一工件的前道工序，SJ(h)為工序Oh屬于同一工件的后道工序，PM(h)為工序Oh屬于同一機(jī)器的前道工序，SM(h)為工序Oh屬于同一機(jī)器的后道工序；p(h)為工序Oh在當(dāng)前機(jī)器的加工時(shí)間。提取過(guò)程如下：

（1）采用文獻(xiàn)[8]給出的前沿貪心方式將染色體解碼成調(diào)度甘特圖，工序Oh在圖上的開(kāi)始加工時(shí)間記為該道工序的sE(h)。

（2）按式（8）計(jì)算得出工序Oh的cL(h),SJ(h)或SM(h)不存在則用∞代替，cL(h)不可超過(guò)整體調(diào)度的最大完工時(shí)間。從后向前對(duì)各工序進(jìn)行迭代計(jì)算，迭代過(guò)程中對(duì)已計(jì)算的變量進(jìn)行記錄，防止重復(fù)計(jì)算以提高效率。

（3）以式（9）為基準(zhǔn)進(jìn)行判斷，若滿足則判定該道工序?yàn)殛P(guān)鍵工序。

3.4.3 同機(jī)器工序調(diào)整鄰域

同機(jī)器工序調(diào)整鄰域通過(guò)遍歷調(diào)度方案中的每個(gè)關(guān)鍵工序，嘗試將關(guān)鍵工序Oh調(diào)整至屬于其同一加工機(jī)器的其他工序間的空閑時(shí)間以最大限度地壓縮最大完工時(shí)間。先按圖13所示方法找出全部可縮減最大完工時(shí)間的調(diào)整方案，再按圖14 所示方法調(diào)整染色體編碼，最終保留調(diào)整后進(jìn)化程度最大的調(diào)整方案。

圖13 同機(jī)器工序調(diào)整鄰域結(jié)構(gòu)示意圖

圖14 甘特圖向編碼映射的工序調(diào)整方案

鄰域結(jié)構(gòu)示意圖如圖13所示。橫向雙箭頭表示從0到Cmax區(qū)間內(nèi)所有可供試探的空閑時(shí)間間隔。以“嘗試將Oh移動(dòng)至工序b 和c 間的空閑時(shí)間間隔”為例說(shuō)明調(diào)整方式：對(duì)Oh的最大可調(diào)時(shí)間段[cE[PJ(h)],sL[SJ(h)]]與工序b 和c 之間的最大可能空閑時(shí)間段[cE(b),sL(c)]求交集，交集不為空時(shí)得到可利用區(qū)間t ，其左邊界tL為max{cE[PJ(h)],cE(b)},右邊界tR為min{sL[SJ(h)],sL(c)},若tR-tL＞0 則代表該移動(dòng)可減少最大完工時(shí)間。

染色體編碼的調(diào)整方式如圖14 所示，同機(jī)器調(diào)整只需對(duì)編碼的OS部分操作：將Oh對(duì)應(yīng)的基因插入至工序c 對(duì)應(yīng)的基因之前，在前沿貪心式主動(dòng)調(diào)度的影響下，此番調(diào)整后甘特圖上Oh也將以最緊湊的方式插入至工序c 之前。

3.4.4 變機(jī)器工序調(diào)整鄰域

變機(jī)器工序調(diào)整鄰域與同機(jī)器工序調(diào)整鄰域的不同之處在于：前者嘗試?yán)玫氖荗h當(dāng)前加工機(jī)器之外的其他可選機(jī)器上工序間的空閑時(shí)間。甘特圖搜尋方案和染色體編碼調(diào)整方式分別如圖15和圖16所示。

圖15 變機(jī)器工序調(diào)整鄰域結(jié)構(gòu)示意圖

圖16 甘特圖向編碼映射的工序調(diào)整方案

鄰域結(jié)構(gòu)示意圖如圖15所示，遍歷Oh當(dāng)前加工機(jī)器之外的其他可選機(jī)器上0 到Cmax區(qū)間內(nèi)的空閑時(shí)間間隔進(jìn)行試探，以“嘗試將Oh移動(dòng)至另一臺(tái)加工機(jī)器上工序a 和b 間的空閑時(shí)間間隔”為例說(shuō)明調(diào)整方式：對(duì)Oh的最大可調(diào)時(shí)間段[cE[PJ(h)],sL[SJ(h)]]與工序a 和b 之間的最大可能空閑時(shí)間段[cE(a),sL(b)]求交集，交集不為空時(shí)得到可利用區(qū)間t，其左邊界tL為max{cE[PJ(h)],cE(a)},右邊界tR為min{sL[SJ(h)],sL(b)} ，若tR-tL＞p(h)則代表該移動(dòng)將Oh從原加工機(jī)器隊(duì)列中抽出的同時(shí)，既不影響加入的機(jī)器隊(duì)列中其他工序的原本狀態(tài)，也不會(huì)產(chǎn)生新的關(guān)鍵路徑，故可能減少最大完工時(shí)間。

染色體編碼的調(diào)整方式如圖16 所示，由于是變機(jī)器調(diào)整，先將編碼的MS 部分Oh對(duì)應(yīng)基因改為調(diào)整后的可選機(jī)器編號(hào)。再對(duì)編碼的OS部分操作：若Oh基因在工序b 基因之后，將Oh基因插入至工序b 基因之前；否則無(wú)需調(diào)整OS部分編碼。

3.4.5 雙工序調(diào)整鄰域

雙工序調(diào)整鄰域旨在對(duì)關(guān)鍵塊（即關(guān)鍵路徑上屬于同一加工機(jī)器的相鄰工序）內(nèi)工序進(jìn)行移動(dòng)，且僅調(diào)整OS 部分。鄰域結(jié)構(gòu)示意圖如圖17 所示。該鄰域基于Van Laarhoven 等[14]提出的鄰域改進(jìn)而來(lái)，刪減了多處無(wú)效移動(dòng)以縮小鄰域規(guī)模，提升局部搜索效率的同時(shí)保證鄰域結(jié)構(gòu)的多樣性。

圖17 雙工序調(diào)整鄰域結(jié)構(gòu)示意圖

移動(dòng)過(guò)程如下：

（1）若首塊包含兩道及以上工序，交換塊尾相連的兩道工序；若尾塊包含兩道及以上工序，交換塊首相連的兩道工序。

（2）除首塊和尾塊外的關(guān)鍵塊，交換塊首和倒數(shù)第二道工序，交換塊尾和第二道工序。

4 算法測(cè)試與數(shù)值實(shí)驗(yàn)

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

上述變鄰域保優(yōu)遺傳算法采用Visual Studio 下C#語(yǔ)言編程，程序在處理器為Intel Core i7 四核CPU、主頻為2.60 GHz、內(nèi)存為8 GB、操作系統(tǒng)為64位Windows10的個(gè)人計(jì)算機(jī)上運(yùn)行。

算法具體參數(shù)設(shè)置如下：

整體：種群規(guī)模Size=100，最大迭代次數(shù)MAXGEN=200，擾動(dòng)間隔代數(shù)Nd=20，擾動(dòng)比例Pd=30%；種群初始化：GS、LS、RS 的比例分別為0.6，0.3，0.1；選擇算子：代溝比例GGAP=0.9；交叉和變異算子：交叉概率Pc=0.8，變異概率Pm=0.05；保優(yōu)記憶庫(kù)：庫(kù)最大容量KMAX=10。

4.2 實(shí)驗(yàn)用例

（1）Kacem 8×8、10×10、15×10三個(gè)實(shí)例[15]。

（2）Brandimarte十組實(shí)例（BRdata）[16]。

4.3 變鄰域搜索策略對(duì)比實(shí)驗(yàn)

為證明本文所設(shè)計(jì)的三個(gè)鄰域拓展搜索深度的能力，使用Brandimarte十組實(shí)例（BRdata）中的MK01進(jìn)行實(shí)驗(yàn)，分別采用添加變鄰域搜索策略的遺傳算法和去除變鄰域搜索策略的遺傳算法進(jìn)行求解，重復(fù)50次，分別記錄這兩種算法求得解集中的最優(yōu)個(gè)體目標(biāo)函數(shù)值。

實(shí)驗(yàn)結(jié)果如圖18所示，50次實(shí)驗(yàn)中，融合了變鄰域搜索策略的遺傳算法得到的最優(yōu)個(gè)體Cmax主要集中在最優(yōu)解40 上；而去除變鄰域搜索策略的遺傳算法得到的最優(yōu)個(gè)體Cmax大部分集中在次優(yōu)解42 和41 上。經(jīng)對(duì)比可證明，在求解穩(wěn)定性和搜索深度上，融合了變鄰域搜索策略的遺傳算法明顯優(yōu)于去除了變鄰域搜索策略的遺傳算法，當(dāng)問(wèn)題規(guī)模增大、解空間拓?fù)浣Y(jié)構(gòu)復(fù)雜時(shí)，本文設(shè)計(jì)的變鄰域搜索算法可在遺傳算法全局優(yōu)化的基礎(chǔ)上快速穩(wěn)定地深入尋找到更優(yōu)解。

圖18 算例MK01（10×6）50次求解結(jié)果

表1 各種算法對(duì)Kacem算例求解結(jié)果對(duì)比分析

表2 各種算法對(duì)Brandimarte算例求解結(jié)果對(duì)比分析

4.4 標(biāo)準(zhǔn)算例測(cè)試實(shí)驗(yàn)

為客觀檢驗(yàn)變鄰域保優(yōu)遺傳算法求解FJSP問(wèn)題的整體性能，進(jìn)行基準(zhǔn)算例測(cè)試，每個(gè)算例求解20 次，記錄最優(yōu)值和平均值。

首先，對(duì)Kacem三個(gè)中小型實(shí)例進(jìn)行測(cè)試，并與董蓉的GA+ACO[17]、Nouiri的MAPSO1[18]、Ziaee的Heuristic[19]、Rhamati 的BBO[20]、Gao 的TABC[21]、Wang 的IACO[22]進(jìn)行對(duì)比，結(jié)果如表1所示，其中Cmax為最優(yōu)解，Aver 為平均值。對(duì)比顯示，在搜索深度上，本文算法所求得的最優(yōu)值均已達(dá)到參考文獻(xiàn)中的最好解，其余算法中僅GA+ACO、TABC和IACO算法可與本文算法持平；在搜索穩(wěn)定性上，本文算法所求得的平均值優(yōu)于GA+ACO算法。由此驗(yàn)證了本文算法應(yīng)對(duì)中小型FJSP問(wèn)題時(shí)深入且穩(wěn)定的優(yōu)勢(shì)。

然后，對(duì)Brandimarte十個(gè)大中型實(shí)例進(jìn)行測(cè)試，并與Ho 的LEGA[23]、劉 瓊 的IGA[24]、Ziaee 的Heuristic[19]、Rhamati的BBO[20]、Gao的TABC[21]、Shao的hDPSO算法[25]進(jìn)行對(duì)比，結(jié)果如表2和表3所示。對(duì)比顯示，在求解深度上，除MK10 算例外，本文算法的求解結(jié)果均取得了所列算法的最好解；在整體求解質(zhì)量上，本文算法的優(yōu)于解與差于解數(shù)目和TABC算法持平，而與其他五種算法相比優(yōu)于解數(shù)目明顯多于差于解數(shù)目。在搜索穩(wěn)定性上，本文算法所求得的平均值均優(yōu)于LEGA和IGA算法，且對(duì)于MK09大型算例的求解均值有明顯改善。由此驗(yàn)證了本文算法應(yīng)對(duì)大中型FJSP 問(wèn)題時(shí)，在保證搜索深度的前提下，進(jìn)一步提升了尋優(yōu)的穩(wěn)定性和全面性。

表3 Brandimarte算例優(yōu)于解和差于解數(shù)目對(duì)比分析

擇取MK09實(shí)例進(jìn)行完整記錄，Cmax平均值和最優(yōu)值收斂曲線如圖19所示?？梢?jiàn)，在擾動(dòng)策略的作用下，平均值收斂曲線每迭代20 次會(huì)產(chǎn)生一次躍變，而最優(yōu)值收斂曲線由次優(yōu)解跳向更優(yōu)解的行為也發(fā)生在躍變點(diǎn)附近，證明新元素的補(bǔ)充可適當(dāng)增強(qiáng)種群的活躍度，配合變鄰域搜索的局部?jī)?yōu)化能力可提高算法的跳坑能力。同時(shí)，在本文所設(shè)計(jì)保優(yōu)記憶庫(kù)策略作用下，平均值收斂曲線的躍變會(huì)快速回歸平穩(wěn)，且不會(huì)影響種群解的最優(yōu)值。圖20為該算例求得的最優(yōu)調(diào)度甘特圖。

圖19 算例MK09（20×10）收斂曲線

5 結(jié)束語(yǔ)

本文針對(duì)最小化最大完工時(shí)間的單目標(biāo)FJSP，提出融合了遺傳算法與變鄰域搜索的混合算法，合理平衡了搜索過(guò)程的廣度與深度，通過(guò)對(duì)Brandimarte 等算例的測(cè)試驗(yàn)證了該算法的可行性與有效性。設(shè)計(jì)了一種保優(yōu)記憶庫(kù)策略，在有效保護(hù)精英個(gè)體的基礎(chǔ)上進(jìn)一步提升精英群體的豐富度。提出了高效穩(wěn)定的關(guān)鍵工序搜尋方法，改進(jìn)并設(shè)計(jì)了三種基于關(guān)鍵工序調(diào)整的鄰域結(jié)構(gòu)，并驗(yàn)證了其深化局部搜索能力、拓展尋優(yōu)深度的良好效果。未來(lái)的研究中，將考慮與其他智能優(yōu)化算法進(jìn)行融合，并對(duì)多目標(biāo)FJSP 和動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行深入探索，使求解作業(yè)車(chē)間調(diào)度問(wèn)題的算法更加高效和完善，且具有更強(qiáng)的適應(yīng)性。此外還考慮將本調(diào)度算法應(yīng)用于制造車(chē)間的MES 系統(tǒng)中，以應(yīng)對(duì)實(shí)際加工過(guò)程中的任務(wù)訂單調(diào)度需求。

圖20 算例MK09（20×10）最優(yōu)調(diào)度甘特圖