基于改進NSGA－II混合算法求解多目標柔性作業(yè)車間調度問題

陸科苗，何利力

（浙江理工大學 信息學院，杭州 310018）

0 引 言

傳統(tǒng)的作業(yè)車間調度問題（Job－shop scheduling problem，JSP）一直被大家廣泛關注，柔性作業(yè)車間調度問題（Flexible job－shop scheduling problem，F(xiàn)JSP）是此類問題的一種擴展。簡而言之，其是一類滿足任務配置需求和條件約束的組合優(yōu)化問題。求得符合各項要求的最優(yōu)解，可用于指導實際生產(chǎn)，所以對其研究具有重要的實際參考價值。

多年來，如啟發(fā)式算法、禁忌搜索（TS）、粒子群法（PSO）、遺傳算法（GA）和變鄰域搜索（VNS）等算法及混合優(yōu)化算法，都被廣泛用于求解該問題。Amjad通過研究發(fā)現(xiàn)，GA方法是解決FJSP最廣泛、有效的算法之一。但經(jīng)典GA中，不同的交叉概率和變異概率會極大影響算法行為和性能，進而影響其算法收斂性。侍守創(chuàng)等提出，將遺傳算法與量子粒子群優(yōu)化算法混合，改善單一算法收斂性不足的問題。吳秀麗等提出基于NSGA－II算法，來求解多目標調度問題。張超勇設計了一種改進的非支配排序遺傳算法，優(yōu)化了精英選擇策略。Sevkli等采用變鄰域搜索算法，設計了兩種不同的鄰域結構，組成鄰域結構集求解JSP。

從上述研究可以看出，單一算法因其搜索效率低以及進化速度慢，難以進化出較為優(yōu)質的個體，并存在局部搜索性不足的問題。故采用混合優(yōu)化算法取長補短求解FJSP，逐步改良求解過程，最終尋得最優(yōu)解。當前研究多為NSGA－II算法求解多目標優(yōu)化問題，雖然已經(jīng)表現(xiàn)了良好的求解能力，但在保持種群的多樣性和局部搜索方面仍存在不足。因此，本文結合改進的NSGA－II算法全局搜索性能較強和VNS算法鄰域搜索性能較強的特點，提出一種改進的NSGA－II算法和變鄰域搜索算法相結合的IVNSGA－II算法。通過與其它算法求解FJSP的實驗結果進行比較分析，驗證了算法的有效性和適用性。

1 FJSP模型

1.1 問題描述

FJSP可描述為個待加工的工件集合{，，…，J}在臺不同的設備集合{，，…，M}上加工。每個工件有若干道工序集合，每道工序有若干臺設備可以選擇，工序的加工時間也因設備的選擇而有所不同，且工序間有先后約束，給定各工序加工時間，確定設備所有工件的加工次序和加工時間。柔性作業(yè)車間調度問題的符號定義見表1。

表1 符號定義Tab.1 Symbol definition

在FJSP的調度過程中，應滿足以下約束條件：

（1）一道工序只能在一臺可選設備上加工；

（2）同一工藝路線上的兩個工序不能同時加工；

（3）同臺設備同一時刻只能加工一道工序；

（4）加工過程中不能中斷；

（5）不同工件具有相同的加工優(yōu)先級；

（6）同一工件的工序具有先后約束，不同工件之間沒有先后約束。

1.2 多目標優(yōu)化模型

本文以最大完工時間、生產(chǎn)總能耗、設備總負荷最小，作為FJSP的多目標優(yōu)化函數(shù)。其優(yōu)化模型為：

（1）最小化最大完工時間：最大完成時間是指所有部件同時進行加工，最后一個部件完成時所花費的時間。時間越短，表明方案越好。計算公式如下：

（2）最小化生產(chǎn)總能耗：在車間實際生產(chǎn)中，計算生產(chǎn)總能耗時需要考慮到設備加工和等待加工，兩種情況分別對應的單位能耗值是不同的。設備的能耗和車間生產(chǎn)總能耗公式如下：

（3）最小化設備總負荷：車間生產(chǎn)加工時，在滿足加工能耗與最大完工時間最小的同時，還要考慮到設備的總負荷。因此，工序在能耗相同的情況下，選擇加工時間短的設備，使其設備總負荷最小化。計算公式如下：

2 算法設計

2.1 編碼

在對FJSP進行編碼時，需要同時考慮到工序、設備的排序問題。因此，本文采用工序與設備融合并行雙鏈式編碼方式。第1層為基于工序的編碼層（Operation Sequence，OS），第2層為基于設備選擇的編碼層（Machine Sequence，MS）。融合兩種編碼方式，形成一條染色體，就可以得到面向FJSP的一個可行解。如圖1所示，層的數(shù)字表示工件號，工件號出現(xiàn)的次數(shù)即表示該工件的第幾道工序；層則按照工件工序順序排列并與之相對應，表示相應位置工序的設備選擇。層和層的長度相等。

圖1 并行雙鏈式編碼示例圖Fig.1 Example of parallel double－chain coding

圖1中表示的加工順序為：工件1的第一道工序在加工設備1上加工→工件3的第一道工序在加工設備2上加工→工件2的第一道工序在加工設備2上加工→工件3的第二道工序在加工設備為5上加工依次類推。這種編碼方式保證了后續(xù)操作所產(chǎn)生染色體解的可行性，且對工件的工序長度和工件數(shù)量無任何要求，避免了后續(xù)繁雜的修正操作，簡單靈活。此外，對其中一層的單獨操作不會影響到另一層，具有很強的并行性。

2.2 解碼

對和層分別進行解碼，目標是根據(jù)編碼層的形式獲得空間范圍內(nèi)優(yōu)質的解。然而在實際任務分配過程中，常常存在兩個相鄰工序間等待時間過長，所以可將后續(xù)符合相應約束條件的工序，提前插入到符合條件的時間區(qū)間中，進行“插隊”操作。因此，提出一種最優(yōu)插入法，實現(xiàn)對解的高效搜索。實現(xiàn)步驟如下：

判斷是否為此工件的首道工序，若是則將0作為空閑起點；反之，將上一道工序的完工時間作為空閑起點；

尋找空閑起點之后大于等于待加工工序加工時間的空閑時間段。若未找到，則按順序正常加工；

選擇滿足待加工工序加工時間且最短的空閑時間段插入；

重復Step1－3，直至所有工序安排完成；

計算最大完工時間。

最優(yōu)插入法的插入過程如圖2所示。工序O將在設備上加工，根據(jù)當前情況，3段可選空閑時間段均滿足O的加工時間所需條件。其中空閑1結束時間與工序O結束時間之差所求的空閑時間小于O的加工時間，不滿足約束條件舍去；空閑2、3都滿足插入條件，而空閑2的空閑時間更短，因此選擇空閑2插入。該策略能夠為后續(xù)工序的插入提供更多的選擇，以獲取更優(yōu)質的解。

圖2 最優(yōu)插入示意圖Fig.2 Schematic diagram of optimal insertion

2.3 種群初始化

NSGA－II算法中，初始化策略影響著解的質量與收斂速度，是重要的起步階段。考慮到算法復雜度和種群數(shù)量大小限制，在種群初始化階段，數(shù)量規(guī)?？刂圃谠N群數(shù)量的1.5倍。為保證種群多樣性，對于OS編碼層采用隨機選擇產(chǎn)生，隨機搜索時種群越大找到最優(yōu)解的概率也就越大；對于MS編碼層采用全局選擇、局部選擇和隨機選擇的方式初始化。

將隨機式初始化和混合式初始化方式相結合，相互取長補短，在保證收斂速度的同時增強全局搜索能力，經(jīng)過后續(xù)處理迭代，提高初始種群豐富度，減少隨機性，加大求得最優(yōu)解的概率。

2.4 選擇算子

本文以最大完工時間、生產(chǎn)總能耗、設備總負荷最小作為FJSP問題的目標，對個體的適應度進行評價，算法的適應度如下：

其中，、、分別為式（1）、式（3）、式（4）的最小化目標優(yōu)化函數(shù)。需要均衡3個適應度指標，根據(jù)計算后的適應度，對個體進行非支配排序，同時計算處于同一支配層級的個體擁擠度。種群中適應度最大的染色體直接復制到新種群，然后新種群中的其它個體采用動態(tài)擁擠度算法并結合精英解保留策略，選擇個體組成新父種群。

2.5 交叉操作

（1）OS交叉：采用基于工件順序的交叉（POX）如圖3所示。父代染色體與進行交叉，交換染色體中工序的位置得到子代。

圖3 OS交叉Fig.3 OS cross

（2）MS交叉：采用多點交叉如圖4所示。父代染色體和分別選擇隨機位置，將所選位置按順序插入子代，然后將剩余未選中位置插入到子代，同理操作。

圖4 MS交叉Fig.4 MS cross

2.6 變異操作

變異操作可以起到擴大隨機性的作用，增加算法的搜索能力，變異操作如圖5所示。在進化初始階段，需要較小的變化概率，并盡可能多的保留優(yōu)良基因；而在后期階段，需要適當增加變異概率產(chǎn)生基因的多樣性，以免“早熟”現(xiàn)象，所以在迭代過程中使用動態(tài)自適應變異概率。計算公式如下：

圖5 OS和MS的變異操作Fig.5 Mutation operations for OS and MS

其中，為初始變異概率值；為最大變化率；MAX為最大迭代次數(shù)；為當前迭代次數(shù)。

2.7 變鄰域搜索算法

雖然交叉、變異操作在一定程度上可以增加種群多樣性，但算法仍可能存在陷入局部最優(yōu)的情況。因此，引入變鄰域搜索算法，通過改變當前解染色體的某些基因位值，產(chǎn)生鄰域可行解，從而避免種群進化過程中產(chǎn)生的解陷入局部最優(yōu)。本文針對OS染色體段，結合改進的NSGA－II算法中各類算子，再引入4種（insert算子、inverse算子、swap算子、pairwise算子）不同的鄰域搜索結構，實現(xiàn)動態(tài)鄰域搜索，擴大局部搜索范圍，增強局部搜索能力。

（1）insert算子：隨機選擇2點工件所在工序對應的基因位置進行操作。例如位置2、6，則把6位置的基因插入2基因后的位置上，原來的3－5基因往后順延，具體的結構變換過程如圖6所示：

圖6 insert算子鄰域變換示例Fig.6 Insert operator neighborhood transformation example

（2）inverse算子：隨機選擇兩個位置，將位置之間的工序基因順序進行反轉。例如，選擇位置3、7，具體結構變換過程如圖7所示：

圖7 inverse算子鄰域變換示例Fig.7 Inverse operator neighborhood transformation example

（3）swap算子：隨機取兩個位置，執(zhí)行兩點交換操作。例如，選擇位置4、6，具體結構變換過程如圖8所示：

圖8 swap算子鄰域變換示例Fig.8 Swap operator neighborhood transformation example

（4）pairwise算子：將相鄰的兩個成對基因位置互換，即第一個和第二個基因互換位置，第三個和第四個基因互換位置，以此類推，最后若剩下單個工序則不變動。具體結構變換過程如圖9所示：

圖9 inverse算子鄰域變換示例Fig.9 Inverse operator neighborhood transformation example

2.8 IVNSGA－II算法

本文提出的IVNSGA－II算法，是以改進的NSGA－II算法為基礎，通過非支配排序、動態(tài)擁擠度算法和精英選擇策略得到新種群，再結合VNS變鄰域搜索算法構建鄰域結構集求解多目標柔性作業(yè)車間調度問題，算法流程如圖10所示。IVNSGA－II算法流程如圖10所示：

圖10 IVNSGA－II算法流程Fig.10 IVNSGA－II algorithm flow

3 實驗結果與分析

IVNSGA－II算法通過MATLAB編程實現(xiàn)，在win10系統(tǒng)，Intel（R）Core（TM）i7－8565U CPU＠1.80 GHz，內(nèi)存8 GB的計算機上實現(xiàn)。各項參數(shù)設置為：種群規(guī)模P＝150，最大迭代次數(shù)MAX＝100，交叉概率P＝0.8，變異概率0.05。

為驗證IVNSGA－II算法的可行性和有效性，分別進行單目標優(yōu)化和三目標優(yōu)化實驗。其中，單目標為最大完工時間。采用Brandimarte設計的5個典型FJSP數(shù)據(jù)集（mk01～mk05）進行測試對比，此數(shù)據(jù)集中包括不同的工件數(shù)、工序數(shù)、設備數(shù)以及加工時間。車間使用的加工設備功率相關數(shù)據(jù)見表2。

表2 設備功率表Tab.2 Equipment power table

3.1 單目標實驗

表3為GA、PSO、NSGA－II、IVNSGA－II算法在mk01～mk05中運行的結果。根據(jù)對比可以看出，IVNSGA－II均取得最優(yōu)解，證明了該算法具備良好的性能。

表3 算法運行時間結果對比Tab.3 Comparison of running time of different algorithm

以mk01為例，其收斂曲線如圖11所示。由圖可見，開始迭代時下降速度較快，說明開始采用的初始化策略加速了收斂速度，大概在40代時得到最優(yōu)解；之后的上下波動，證明IVNSGA－II算法避免了陷入局部最優(yōu)解。mk01的調度甘特圖如圖12所示。

圖11 IVNSGA－II迭代收斂圖Fig.11 IVNSGA－II iterative convergence graph

圖12 mk01調度甘特圖Fig.12 mk01 scheduling Gantt chart

3.2 三目標實驗

同等條件下在mk01數(shù)據(jù)集上進行實驗，結合設備功率表，針對最大完工時間、生產(chǎn)總能耗以及設備總負荷的三目標求解，得到完整的Pareto前端。不同于單目標的衡量指標，解的數(shù)量也是衡量多目標調度性能的重要指標之一。本文將IVNSGA－II與NSGA－II進行三目標性能對比，對比結果如圖13所示。

圖13 三目標Pareto前沿圖Fig.13 Three－target Pareto frontier map

從圖中可以看出，3個目標之間相互影響，IVNSGA－II所獲得解的范圍更大，解的個數(shù)更多，解集質量也更優(yōu)?？梢宰C明，IVNSGA－II具有良好的全局收斂性和局部搜索性。在實際調度生產(chǎn)中，企業(yè)可以根據(jù)實際情況選擇合適的解，然后獲得相應的甘特圖，用于指導實際生產(chǎn)。

4 結束語

本文針對FJSP問題，同時考慮多目標優(yōu)化的特點，以最大完工時間、生產(chǎn)總能耗、設備總負荷最小為優(yōu)化目標，提出一種IVNSGA－II算法，對多目標優(yōu)化問題求解。通過動態(tài)擁擠度和自適應變異算子，保證求解過程中解的多樣性；再結合VNS算法鄰域搜索能力，設計4中不同的鄰域結構進行變鄰域搜索。通過在Matlab平臺上實例的分析對比，表明該算法可有效解決FJSP問題，為車間生產(chǎn)者提供可參考的調度方案，且具有較好的穩(wěn)定性和尋優(yōu)能力，驗證了所提算法的有效性。