基于改進NSGA-Ⅲ的多目標柔性車間調(diào)度研究*

孫 浩，劉環(huán)宇，趙柏棟，張玉嘉，楊 振，王德權(quán)

(大連工業(yè)大學機械工程與自動化學院，大連 116034)

0 引言

柔性生產(chǎn)調(diào)度問題(flexible job shop scheduling problem,FJSP)是復雜的NP-hard問題[1]，打破了傳統(tǒng)剛性大批量生產(chǎn)對設(shè)備唯一性的約束，使車間調(diào)度變得更加復雜多變。從調(diào)度目標數(shù)量可將柔性作業(yè)車間調(diào)度分為：單目標和多目標調(diào)度。

相比于單目標調(diào)度問題[2-3]，多目標柔性作業(yè)車間調(diào)度問題更為復雜。首先，難以保證在調(diào)度過程中多個目標的優(yōu)化平衡。其次，多個目標的參數(shù)和量綱存在差異。現(xiàn)階段多目標調(diào)度的研究思路分為兩種，其一，通過權(quán)重將多目標轉(zhuǎn)化為單目標[4-5]；其二，非劣解生成法，利用帕累托原理生成最優(yōu)解集[6-8]，此方法廣泛應用于求解三目標及以上問題。在算法設(shè)計上需要對原始算法進行改進或者結(jié)合兩種不同算法的優(yōu)點，使算法能夠發(fā)揮更好的尋優(yōu)效果。DEB等[9]在NSGA基礎(chǔ)上提出了NSGA-Ⅱ算法，提高算法搜索效果和計算效率。CHEN等[10]提出混合算法MGSA- NSGA-Ⅲ，采取混沌變異策略，提高解空間分布的均勻性。LI等[11]在傳統(tǒng)NSGA-Ⅲ基礎(chǔ)上改進了參考點生成策略和算子選擇機制，提高了算法計算效率。求解高維多目標問題時，常見的全局智能算法均存在著種群多樣性低、搜索效率差、容易陷入局部最優(yōu)等缺陷。

綜上所述，文章提出了一種改進NSGA-Ⅲ算法，采取4種不同編碼方式共同生成初始化種群，并引入鄰域搜索策略，解決單一算法種群多樣性低、容易陷入局部最優(yōu)等問題。

1 多目標柔性作業(yè)車間調(diào)度模型建立

柔性作業(yè)車間的柔性表現(xiàn)在加工順序和設(shè)備選擇上的不確定性，使多目標調(diào)度問題更為復雜。假設(shè)，車間共有m臺設(shè)備和n個待加工工件，并且每個工件含有多道加工工序。工件必須按照工序的加工順序依次加工，工件的每道工序的加工設(shè)備選取須在指定的設(shè)備集中，可選設(shè)備集中的機器加工能力存在差異。因此，柔性車間調(diào)度的兩個主要任務：①確定工件的加工順序；②確定每道工序選擇的設(shè)備。參數(shù)符號含義如表1所示。

表1 參數(shù)符號含義

機器集合M={M1,M2,…,Mm}，共有m臺設(shè)備；工件集合P={P1,P2,…,Pn}，共有n個工件；工序集合J={J1,J2,…,Jn}，Ji={Ji1,Ji2,…,Jik}，Ji表示第i個工件加工的工序數(shù)。

(1)目標函數(shù)。

①最大完工時間最??；

CM=min(max1≤i≤n(Ci))

(1)

②總設(shè)備負荷最??；

(2)

③車間總能耗最小；

(3)

(2)約束條件。

柔性作業(yè)車間調(diào)度問題可描述成，n個工件在m臺設(shè)備上加工，且一個工件包含多道工序，每道工序可在一臺或多臺設(shè)備上加工，加工設(shè)備選擇不同，加工時間及加工功率不同。

①所有設(shè)備初始化均為待加工狀態(tài)。

(4)

②一個工件某一時刻只能加工一道工序。

(5)

式中，k′、k表示對應加工設(shè)備編號

③一個工件的某一時刻只能在一臺設(shè)備上進行加工。

Li,j,t1≠Li,j,t2→t1≠t2

(6)

式中，Li,j,t1為t1時刻執(zhí)行Oi,j的設(shè)備編號；Li,j,t2為t2時刻執(zhí)行Oi,j的設(shè)備編號。

④任意工件只要選定設(shè)備開始加工，則過程中不能中斷。

(7)

⑤每個工件的每道工序需在特定的設(shè)備集中選取。

mi,j∈Mi,j

(8)

2 改進NSGA-Ⅲ算法設(shè)計

遺傳算法在求解調(diào)度優(yōu)化問題時具備魯棒性強特點。求解多目標問題時，NSGA-Ⅱ[12]和NSGA-Ⅲ被廣泛使用，為了進一步提高算法的效率，避免陷入局部最優(yōu)，對NSGA-Ⅲ算法做出如下改進。算法流程如圖1所示。

圖1 改進NSGA-Ⅲ算法流程圖

基本步驟如下：

(1)種群初始化階段，為保證種群分布均勻并且縮小搜索的解空間大小。采取4種不同編碼的種群初始化方式；

(2)混合NSGA-Ⅱ基于擁擠度選擇和錦標賽的方式，對初始化種群進行篩選，使具有良好基因的個體參與到進化當中；

(3)利用NSGA-Ⅲ的全局搜索能力，對種群進行搜索，選擇出下一代優(yōu)良個體；

(4)結(jié)合基于部分解的隨機鄰域搜索策略，對(3)選擇出的優(yōu)良個體進行鄰域搜索，避免丟失更優(yōu)的個體；

(5)判斷算法是否終止，即算法是否迭代到指定代數(shù)，是則算法終止，否則繼續(xù)迭代。

2.1 染色體編碼設(shè)計

工件的加工工序順序和每道工序的設(shè)備分配是柔性作業(yè)車間調(diào)度中最基本的兩個方面。因此，在此類問題上采取兩部分編碼方式。第一部分基于工序編碼，選取工件編號作為工序部分基因，第二部分基于設(shè)備編碼，選取設(shè)備集中的設(shè)備順序號作為基因。圖2以3個工件在3臺設(shè)備上加工為例來編碼。

圖2 染色體編碼

工序編碼表示為三個工件的加工順序，第一個1出現(xiàn)表示O1,1工序，第二個1出現(xiàn)表示O1,2工序。設(shè)備編碼表示完成某工序可用設(shè)備集中所選擇設(shè)備的順序號，例如，設(shè)備編碼中第一個2表示為完成O1,1工序，在m1,1中選擇第2個設(shè)備M2。

2.2 種群初始化設(shè)計

種群空間的均勻性是影響算法性能好壞的重要指標。越是均勻的種群空間，算法的搜索結(jié)果往往更優(yōu)，不容易陷入局部最優(yōu)等問題。因此，為使種群空間具有均勻性，采用4種不同的編碼方式共同生成初始化種群。

(1)采取最長路徑(即加工工序最多)加工時間最短原則編碼。

(2)采取隨機加工工序的加工時間最短原則編碼。

(3)采取最長路徑加工功率最小原則編碼。

(4)采取隨機加工工序的加工功率最小原則編碼。

2.3 初始化種群個體的選擇

錦標賽選擇的方式是常見的選擇手段之一，而在解決高維多目標問題時，單一的選擇方式很難達到理想效果，需要更多的指標來保證選取的合理性。綜合考慮算法的計算效率和選取結(jié)果的最優(yōu)程度，提出結(jié)合NSGA-Ⅱ中的快速非支配等級和基于擁擠度的選擇方式。

(1)計算種群個體的非支配等級和擁擠度大小。

(2)設(shè)置錦標賽參賽數(shù)量，選擇出參賽的個體，再依據(jù)非支配排序等級，選出等級較高的個體。

(3)當選擇的個體非支配排序等級一致時，選擇擁擠度較大的個體。

2.4 交叉與變異

(1)交叉操作。采用模擬二進制交叉方式，分別對工序和設(shè)備進行交叉。工序交叉如圖3所示，設(shè)備交叉如圖4所示。

圖3 工序交叉示意圖

將P1中工序2位置保留，再將P2中不屬于工序2 的位置順序插入到P1中得到子代個體C1,同理，得到C2。

圖4 設(shè)備交叉示意圖

確定父代個體中設(shè)備交叉位置，進行交叉生成子代個體。再依據(jù)工序染色體對交叉后的設(shè)備染色體產(chǎn)生的非法基因按照設(shè)備加工時間最短原則進行修正。

(2)變異操作。變異操作采取基于工序交叉和設(shè)備交叉的變異方式，利用隨機函數(shù)產(chǎn)生工序交叉位置，同時保證位置上點數(shù)值不同。交叉完成后，工序基因?qū)牟缓侠碓O(shè)備基因，按照工序加工時間最短原則進行修正，設(shè)備交叉與工序交叉同理。工序交叉變異過程如圖5所示。

圖5 基于工序交叉的變異圖

2.5 基于部分解的隨機鄰域搜索策略

NSGA-Ⅲ具有良好的全局搜索能力，但其對局部的搜索能力較差，因此算法在迭代過程中往往會出現(xiàn)局部最優(yōu)的問題?；诖耍扇∴徲蛩阉鳈C制[13]與NSGA-Ⅲ算法混合的方式。

(1)首先，設(shè)置大小為K的鄰域搜索空間。

(2)選擇鄰域搜索個體，并在該個體中隨機選擇兩個工件的工序作為關(guān)鍵工序，對工件1中所有工序的設(shè)備進行重新選擇：①當最短加工時間設(shè)備唯一，選擇該設(shè)備加工。②當最短加工時間設(shè)備不唯一，選擇所有設(shè)備中加工功率最小的設(shè)備。對工件2中所有工序的設(shè)備重新隨機選擇。

(3)滿足初始設(shè)定的K值時，結(jié)束鄰域搜索。

3 仿真驗證

首先，驗證改進算法目標迭代的收斂情況，再將所提出的改進NSGA-Ⅲ算法與原始NSGA-Ⅲ 算法進行對比驗證，觀察兩個算法在相同實例下所得到的初始解空間的均勻性、大小和非支配解的數(shù)量。

算法基本參數(shù)如表2所示。

表2 算法基本參數(shù)

(1)初始化種群分布和最優(yōu)解的分布對比。對比NSGA-Ⅲ算法與所提出的改進NSGA-Ⅲ算法在求解MK01算例時初始化種群的分布情況和最優(yōu)解分布情況，如圖6～圖8所示。

圖6 NSGA-Ⅲ初始 化種群分布圖7 改進NSGA-Ⅲ 初始化種群分布

圖8 兩種算法最優(yōu)解的分布圖

由上述分布圖可知，改進NSGA-Ⅲ算法的初始化種群分布更均勻，搜索的解空間更小，且搜索到的最優(yōu)解收斂更好，求解結(jié)果更優(yōu)。

(2)非支配解對比驗證。對于非支配解的驗證，采用10個BRdate[14]實例進行仿真。兩種算法在10個BRdate實例上搜索到非支配解情況匯總?cè)缦拢浩渲蠳SD表示兩個算法搜索到的非支配解總數(shù)；～表示沒有搜到非支配解；n1|n2中n1代表對應算法搜索到的非支配解數(shù)量，n2代表兩個算法搜索的非支配解總數(shù)。具體非支配解信息匯總?cè)绫?所示。

表3 兩種算法的非支配解

由上表可知，改進NSGA-Ⅲ在10組BRdate算例中搜索到非支配解數(shù)占76%，而NSGA-Ⅲ搜索到非支配解數(shù)占24%，改進NSGA-Ⅲ有效性得以驗證。

4 總結(jié)

針對柔性作業(yè)車間調(diào)度問題，建立以最小化完工時間，設(shè)備總負荷和車間總能耗為目標的多目標調(diào)度模型，并對求解多目標問題具有良好魯棒性的NSGA-Ⅲ算法做出改進。首先，采取4種不同編碼方式的種群初始化策略，使得種群分布均勻的同時，縮小搜索的解空間大小。在進化階段，混合了NSGA-Ⅱ基于擁擠度的父代種群選擇和基于部分解的鄰域搜索策略，防止算法在實現(xiàn)全局搜索時，陷入局部最優(yōu)。

最終，通過10個BRdate標準算例對所提出的改進NSGA-Ⅲ算法與原始NSGA-Ⅲ算法進行對比驗證。依據(jù)初始化種群的均勻性、搜索解空間的大小和非支配解的數(shù)量等指標來判斷算法的優(yōu)劣，證明所提出算法的有效性。