吳樹景，游有鵬，羅福源

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

1 引言

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

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

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

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

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

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

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

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

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

其中：

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

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

式（3）表示資源約束條件，即機器加工各工件的先后順序，限定每臺機器一次只能加工一個工件。

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

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

3.1 整體流程框架

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

圖1 整體算法流程框架圖

算法具體步驟如下：

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

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

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

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

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

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

步驟7 執(zhí)行精英保留策略，選取當前代新種群中的較優(yōu)個體更新保優(yōu)記憶庫，對精英個體進行保護。

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

3.2 染色體編碼與解碼

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

圖2 FJSP染色體編碼示例圖

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

3.3 遺傳算法

3.3.1 種群初始化

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

3.3.2 選擇算子

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

圖3 遍及賭輪選擇

3.3.3 交叉算子

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

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

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

詳細交叉策略如下：

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

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

圖5 均勻交叉

圖6 改進POX交叉

3.3.4 變異算子

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

圖7 MS部分變異

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

圖8 OS部分變異

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

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

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

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

3.4 變鄰域搜索算法

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

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

3.4.1 變鄰域搜索流程

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

圖10 變鄰域搜索流程

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

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

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

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

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

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

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

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

（3）以式（9）為基準進行判斷，若滿足則判定該道工序為關(guān)鍵工序。

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

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

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

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

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

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

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

變機器工序調(diào)整鄰域與同機器工序調(diào)整鄰域的不同之處在于：前者嘗試利用的是Oh當前加工機器之外的其他可選機器上工序間的空閑時間。甘特圖搜尋方案和染色體編碼調(diào)整方式分別如圖15和圖16所示。

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

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

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

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

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

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

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

移動過程如下：

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

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

4 算法測試與數(shù)值實驗

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

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

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

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

4.2 實驗用例

（1）Kacem 8×8、10×10、15×10三個實例[15]。

（2）Brandimarte十組實例（BRdata）[16]。

4.3 變鄰域搜索策略對比實驗

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

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

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

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

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

4.4 標準算例測試實驗

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

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

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

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

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

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

5 結(jié)束語

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

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