基于強繁殖NSGA-Ⅱ算法的柔性車間調度多目標優化*

朱旭東

(無錫工藝職業技術學院，江蘇 宜興 214200)

0 引言

根據市場的多變性和客戶的多樣性需求，產品的多樣化和小批量生產成了生產制造行業的主流模式，傳統單一品種大批量生產的剛性車間已經無法滿足市場需求，使得柔性制造車間不斷涌現。對于柔性作業車間，產品的每道工序可由多個機器加工而成，因此存在產品的加工順序和工序的機器分配等諸多調度問題[1]。不同的調度方案對應的完工時間、機器能耗、機器負荷也不同，因此研究車間調度問題具有重要的實際意義。

根據優化目標的數量，可以將柔性車間調度問題分為單目標調度問題和多目標調度問題。單目標調度研究主要集中在最小化完工時間這一目標上，文獻[2]在差分進化算法中引入了一種新的轉化方法，使其能夠有效求解柔性車間調度問題，實現了對柔性車間完工時間的優化。文獻[3]以最小化完工時間為車間優化目標，在算法中引入了反向學習策略和Metropolis準則，實驗驗證了該方法在車間調度中的優越性。多目標優化處理的多個目標間一般存在沖突問題，一般包括先驗法和后驗法兩類。先驗法是指根據先驗知識為每個目標線性加權得到單個目標，文獻[4]針對柔性車間多目標調度問題，提出了混合TS算法的求解方法。文獻[5]針對質檢引起的完工時間延遲和耗能升高問題，提出了改進頭腦風暴的求解方法，在保證交付時間約束下降低了車間能耗。先驗法中精準確定每個目標的權重非常困難，需要大量經驗的積累，而且基于聚合的方法無法解決Pareto解集非凸的問題，因此后驗法成為了解決柔性車間多目標優化的熱點方法。文獻[6]設計了新的適應度分配策略，有效解決了柔性車間完工時間、機器負荷等目標的優化。文獻[7]在粒子群算法中引入了鄰域搜索算法和無需半徑共享的小生境技術，實驗驗證了該方法在完工時間、車間總負荷、均負荷等多目標優化中的優越性。基于后驗法的柔性車間調度方法很多，但是多數在全局搜索和局部開發上存在矛盾，因此兩者的平衡是當前研究的一個重要方向。

針對柔性車間調度的多目標優化問題，建立了以減小完工時間、機器總負荷和車間能耗為目標的多目標優化模型，提出了強繁殖NSGA-Ⅱ算法的模型求解方法，實現了減小完工時間、機器負荷、車間能耗的優化目標。

1 柔性車間調度問題描述與建模

1.1 問題描述

柔性車間調度問題描述如下：車間需加工N個工件，記為{J1,J2,…,JN}；每個工件由若干個工序加工而成，以工件Ji為例其加工工序可記為Ji={Oi1,Oi2,…,Oij}，式中Oij為工件Ji的第j道工序；車間可提供的機器設備為K個，記為{M1,M2,…,MK}，每道工序Oij對應一個可選機器集合，記為Mij。需解決的問題是，為各道工序選擇合適的加工設備、合理的加工時間，在滿足生產工藝約束的前提下，實現完工時間最小、機器總負荷最小、總能耗最低等目標。

柔性車間調度問題需滿足的約束條件包括：

(1)在同一時刻，每個機器最多加工一道工序；

(2)工件之間的加工順序完全獨立，但是同一零件的工序間必須滿足順序要求；

(3)各工序開始加工后，不允許中斷。

柔性車間可以分為完全柔性車間和部分柔性車間[8]，完全柔性車間是指每道工序都可由車間內任意機器加工，部分柔性車間是指每道工序只能由車間內部分機器加工，其中部分柔性車間更加普遍，因此本文研究的是部分柔性車間調度問題。

1.2 柔性車間調度優化模型

本文針對柔性車間的調度問題，設置3個優化目標，分別為完工時間最短、機器總負荷最小、車間總能耗最少。

(1)完工時間最短。工件的完工時間是指工件最后一道工序的完工時間，而車間的完工時間是指所有工件中最晚的完工時間，為：

(1)

式中，Ci為工件Ji的完工時間，f1為車間完工時間優化的目標函數。

(2)機器總負荷最小。車間內機器負荷隨調度方案的變化而變化，減小車間內機器總負荷可以有效提高機器的使用壽命，因此以減小車間內機器總負荷為一個優化目標，即：

(2)

式中，f2為車間機器總負荷最小化目標函數，hi為工件Ji的工序數量，tijk為工序Oij在機器Mk上的加工時間，xijk為工序Oij在機器Mk上的加工標識，即：

(3)車間能耗最少。柔性生產車間的能耗包括加工能耗、空載能耗、轉運能耗和固定能耗等，為：

(3)

(4)

式中，sij為工序Oij的開始時間，Ci為工件Ji的完工時間，cij為工序Oij的結束時間，Cmax=maxCi為車間完工時間。

式(4)中第1式表示工序Oij的結束時間應小于工件Ji的完工時間，第2式表示工序Oij的結束時間應小于工序Oi(j+1)的開始時間，第3式表示工序Oij只需加工一次，第4式表示工序Oij的開始時間和結束時間均應為正值。

1.3 編碼與甘特圖解碼方法

在柔性車間調度問題中有兩個問題需要解決，一是確定各工序的生產順序，二是確定各工序的加工機器。為了同時解決這兩個問題，本文使用雙基因鏈編碼方式，基因鏈中的基因長度與工件的所有工序數量一致。第一條基因鏈用于確定工序加工順序，第二條基因鏈用于確定各工序對應的機器。

以3個工件加工為例，每個工件具有3道加工工序，可使用的生產設備具有3臺，分別記為M1、M2、M3。假設某染色體編碼方式如圖1所示。

圖1 染色體編碼方式

圖1中第一條基因鏈確定了工序的加工順序，工件2具有3道工序，因此在第一條基因鏈中出現了3次，第1次出現表示工件2的第1道工序。按照這種規定，第一條基因鏈對應的工序順序為：O21O31O11O22O32O12O23O13O33，對應的機器為M2M1M3M3M2M1M1M3M2。

甘特圖可以對以上編碼和解碼結果進行更加直觀的表達，圖1中的染色體使用甘特圖可表示如圖2所示。

圖2 圖1對應的甘特圖

由圖2可以直觀看出各工序的加工順序、各工序使用的加工機器、各工序的加工耗時、總完工時間等。因此，柔性車間的調度結果一般使用甘特圖給出。

2 強繁殖NSGA-Ⅱ求解算法

2.1 強繁殖NSGA-Ⅱ算法構造思路

NSGA-Ⅱ算法原理可參考文獻[9-10]，這里不再贅述。由于NSGA-Ⅱ算法沿襲了遺傳算法中的交叉、變異、自然選擇等操作思路，因此遺傳算法存在的算法收斂性與個體多樣性之間的矛盾，NSGA-Ⅱ算法也必然存在[11]。為了克服算法的這一缺陷，有效平衡NSGA-Ⅱ算法的多樣性和收斂性，本文提出了具有強繁殖能力的NSGA-Ⅱ算法。

強繁殖NSGA-Ⅱ算法的構造思路為，首先定義染色體的繁殖能力，根據繁殖能力將染色體分為強繁殖個體和普通個體。將強繁殖個體(繁殖能力大于均值)劃為一個子群，將普通個體劃分為一個子群。其中強繁殖子群具有較強的繁殖能力，使用傳統的交叉變異方式即可；普通子群的繁殖能力較弱，使用染色體變化較大的改進交叉變異方法。兩個子群每進化5代進行一次混合，并重新劃分子群。

2.2 染色體繁殖能力

染色體的繁殖能力以其遺傳操作后的繁殖能力為標準進行衡量。將染色體規模記為N，以染色體n為例對繁殖能力度量方法進行介紹。

步驟2：將測試染色體逐個與染色體n進行交叉操作，交叉操作使用傳統交叉方式，傳統交叉方法在后文中明確；

步驟3：染色體n交叉后，若2個子代個體中存在支配染色體n的個體，說明實現了染色體進化，此時染色體n的繁殖能力+1；若2個子代個體均無法支配染色體n，說明染色體未進化，此時染色體n的繁殖能力維持不變；

步驟4：當染色體n與所有測試染色體完成交叉測試后，計算染色體n的繁殖能力，迭代過程結束。

2.3 種群分割與遺傳操作

將所有染色體分為兩個種群，繁殖能力大于均值的個體屬于強繁殖能力種群；繁殖能力低于均值的屬于普通種群。下面依據兩個種群的特點，為兩個種群施加不同的遺傳操作。

(1)強繁殖能力種群的遺傳操作。強繁殖能力種群的染色體繁殖能力較強，使用傳統的交叉變異方式就能夠保持種群的全局優勢。柔性車間調度問題的遺傳操作分為工序遺傳操作和機器遺傳操作。工序遺傳操作使用傳統的POX交叉和插入變異方法[12]。機器遺傳操作使用單點交叉和單點變異。

(2)普通種群的遺傳操作。普通種群繁殖能力相對較弱，因此設置遺傳操作時，采用使染色體變化較大的操作方法，強制性提高染色體的繁殖能力。

普通種群工序排序使用的交叉方式為改進POX交叉方式，如圖3a所示。改進POX交叉的執行方法為：將工件按照大致等量的原則分為兩組，圖3a中將4個工件分為兩組，其中{2，3}為一組，{1，4}為一組。父代1的1、4基因保持不變遺傳給子代2，父代2的2、3基按照順序左移一個基因位并嵌入到子代2的空位中。父代2的2、3基因位保持不變遺傳給子代1，父代1的1、4基因按照順序左移一個基因位嵌入到子代1的空位中。

工序排序的變異方式為基因串逆序變異方式，如圖3b所示。具體操作方法為：隨機產生兩個基因位，將兩個基因位之間的基因進行逆序排列。圖3b中隨機產生的基因位為4和9，將兩個基因位之間的基因逆序排列后放入到染色體中，即實現了基因串逆序變異。

(a) 改進POX交叉操作

(b) 基因逆序變異操作圖3 工序的遺傳操作

機器基因鏈的交叉操作使用均勻交叉方法，如圖4a所示。具體執行方法為：隨機選擇若干個基因位，父代1和父代2被選基因位的基因保持不變，其余基因位的基因按照對應關系進行交叉，即可得到子代1和子代2。

機器基因鏈的變異操作使用定向變異方法，如圖4b所示。首先隨機選擇兩個基因位，圖4b中隨機選擇了基因位4和9。而后從兩個基因位的可選機器集種隨機選擇一個機器，并替換到原基因，圖4b中的基因位4，使用機器2替換原機器5，基因位9，使用機器6替換機器1。

(a) 均勻交叉操作

(b) 定向變異操作圖4 機器的遺傳操作

在普通種群中，設置一個隨機數p∈(0,1)，再設置一個隨機數閾值p0，當p>p0時針對工序基因鏈施加遺傳操作，當p≤p0時針對機器基因鏈施加遺傳操作。強繁殖子群與普通子群之間的交流方式為融合交流，也即每迭代5次，將強繁殖子群和普通子群進行混合，再次計算各染色體的繁殖能力，并進行種群的重新劃分。

2.4 強繁殖NSGA-Ⅱ算法步驟

根據強繁殖NSGA-Ⅱ算法的構造思路，得到強繁殖NSGA-Ⅱ算法步驟如下：

步驟1：設置算法參數，即染色體規模、交叉概率、變異概率、最大迭代次數等；

步驟2：染色體以隨機方式進行初始化；

步驟3：計算各染色體的繁殖能力，并依據繁殖能力將染色體劃分為強繁殖子群和普通子群；

步驟4：強繁殖子群和普通子群按照各自的方式進行交叉變異和選擇，每迭代一次則迭代次數+1；

步驟5：判斷迭代次數是否達到最大值，若否則判斷迭代次數是否為5的倍數，若為5的倍數則轉至步驟3，若不為5的倍數則轉至步驟4；若迭代次數達到了上限，則算法結束。

3 柔性車間調度實驗

3.1 柔性車間調度設置

本文研究的車間調度算例中需生產的工件為8個，車間可提供的生產設備為8臺，各工件的加工工序不等，不同工序在各生產設備上的加工時間如表1所示。

表1 工序加工時間表 (h)

續表

表1中數字表示工序在對應機器上的加工時間，單位為小時，“--”表示工序無法在相應機器上加工。各機器加工功率和空載功率如表2所示。

表2 機器的加工功率與空載功率

3.2 調度結果與分析

強繁殖NSGA-Ⅱ算法的參數設置為：染色體規模為100，最大迭代次數為100，交叉概率設置為0.5，變異概率設置為0.1。為了進行對比，同時使用傳統NSGA-Ⅱ算法進行柔性車間調度優化，算法參數設置與強繁殖NSGA-Ⅱ算法一致。兩種算法的車間調度結果如圖5所示。

圖5 兩種遺傳算法得到的Pareto解集

本文的3個優化目標均為最小化優化目標，對應到圖5所示的3維空間中，圖中藍色“☆”位置為本文的優化方向，因此強繁殖NSGA-Ⅱ算法的Pareto解集明顯優于傳統NSGA-Ⅱ算法的Pareto解集。這是因為強繁殖NSGA-Ⅱ算法中按照染色液的繁殖能力，將染色體劃分為2個種群，兩個種群按照各自的特點設置遺傳操作，有效提高了算法繁殖能力和進化能力，因此解集優于傳統NSGA-Ⅱ算法的Pareto解集。

按照各優化目標重要度折中的原則，從兩個Pareto解集中選擇居中的兩個解進行對比，被選擇的解為圖5中圓圈圈出的解。兩個解對應的生產甘特圖如圖6所示。

圖6 兩種算法解的甘特圖

統計圖6兩個解的完工時間、機器總負荷、車間能耗，結果如表3所示。

表3 兩個解的調度統計參數

結合圖6和表3可以看出，從傳統NSGA-Ⅱ算法和強繁殖NSGA-Ⅱ算法中選擇的折中解，傳統NSGA-Ⅱ算法解的完工時間為81 h，機器總負荷為378 h，車間能耗為6460 kW；強繁殖NSGA-Ⅱ算法解的完工時間為70 h，機器總負荷為364 h，車間能耗為6380 kW，以上參數均小于傳統NSGA-Ⅱ解的參數。從表象上看，圖6中強繁殖NSGA-Ⅱ解對應甘特圖中機器工作量分配更加平均，而傳統NSGA-Ⅱ解的甘特圖中機器工作量分配相對集中，因此強繁殖NSGA-Ⅱ解的調度結果更優。從算法原理角度講，強繁殖NSGA-Ⅱ算法按照染色液的繁殖能力，將染色體劃分為2個種群，兩個種群按照各自的特點設置遺傳操作，有效提高了算法繁殖能力和進化能力。以上柔性車間的調度結果和分析驗證了強繁殖NSGA-Ⅱ算法在柔性車間調度中的有效性和優越性。

4 結論

本文研究了柔性車間的調度優化問題，建立了車間調度的多目標優化模型，在傳統NSGA-Ⅱ算法中引入了強繁殖度量、多種群遺傳等操作，有效改善了算法的優化能力，經驗證得出以下結論：

(1)與傳統NSGA-Ⅱ算法相比，強繁殖NSGA-Ⅱ算法的解集質量更高，優化能力更好；

(2)強繁殖能力NSGA-Ⅱ算法應用于柔性車間調度多目標優化是有效的，可以有效減少完工時間、機器總負荷和車間能耗。