基于強繁殖NSGA-Ⅱ算法的柔性車間調(diào)度多目標優(yōu)化*

朱旭東

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

0 引言

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

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

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

1 柔性車間調(diào)度問題描述與建模

1.1 問題描述

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

柔性車間調(diào)度問題需滿足的約束條件包括：

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

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

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

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

1.2 柔性車間調(diào)度優(yōu)化模型

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

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

(1)

式中，Ci為工件Ji的完工時間，f1為車間完工時間優(yōu)化的目標函數(shù)。

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

(2)

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

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

(3)

(4)

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

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

1.3 編碼與甘特圖解碼方法

在柔性車間調(diào)度問題中有兩個問題需要解決，一是確定各工序的生產(chǎn)順序，二是確定各工序的加工機器。為了同時解決這兩個問題，本文使用雙基因鏈編碼方式，基因鏈中的基因長度與工件的所有工序數(shù)量一致。第一條基因鏈用于確定工序加工順序，第二條基因鏈用于確定各工序?qū)臋C器。

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

圖1 染色體編碼方式

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

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

圖2 圖1對應的甘特圖

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

2 強繁殖NSGA-Ⅱ求解算法

2.1 強繁殖NSGA-Ⅱ算法構(gòu)造思路

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

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

2.2 染色體繁殖能力

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

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

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

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

2.3 種群分割與遺傳操作

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

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

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

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

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

(a) 改進POX交叉操作

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

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

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

(a) 均勻交叉操作

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

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

2.4 強繁殖NSGA-Ⅱ算法步驟

根據(jù)強繁殖NSGA-Ⅱ算法的構(gòu)造思路，得到強繁殖NSGA-Ⅱ算法步驟如下：

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

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

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

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

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

3 柔性車間調(diào)度實驗

3.1 柔性車間調(diào)度設置

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

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

續(xù)表

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

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

3.2 調(diào)度結(jié)果與分析

強繁殖NSGA-Ⅱ算法的參數(shù)設置為：染色體規(guī)模為100，最大迭代次數(shù)為100，交叉概率設置為0.5，變異概率設置為0.1。為了進行對比，同時使用傳統(tǒng)NSGA-Ⅱ算法進行柔性車間調(diào)度優(yōu)化，算法參數(shù)設置與強繁殖NSGA-Ⅱ算法一致。兩種算法的車間調(diào)度結(jié)果如圖5所示。

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

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

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

圖6 兩種算法解的甘特圖

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

表3 兩個解的調(diào)度統(tǒng)計參數(shù)

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

4 結(jié)論

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

(1)與傳統(tǒng)NSGA-Ⅱ算法相比，強繁殖NSGA-Ⅱ算法的解集質(zhì)量更高，優(yōu)化能力更好；

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