基于改進NSGA-Ⅱ的多目標綠色作業(yè)車間調(diào)度問題研究

文笑雨，孫海強，李浩，喬東平，肖艷秋，曹陽

(鄭州輕工業(yè)大學 河南省機械裝備智能制造重點實驗室，河南 鄭州 450002)

0 引 言

目前，中國工業(yè)化與現(xiàn)代化快速發(fā)展，溫室氣體排放量迅速增長[1]。環(huán)境問題已成為世界各國關(guān)注的熱點，并列入世界議事日程。《中國制造2025》明確提出，全面推行綠色制造，實施綠色制造工程[2]。綠色車間調(diào)度是面向綠色制造的車間調(diào)度問題[3]，是影響生產(chǎn)質(zhì)量、效率、成本等因素的關(guān)鍵，對加工過程中的能耗產(chǎn)生重要影響[4]。通過資源分配、操作排序和運作模式的合理優(yōu)化，可實現(xiàn)增效、節(jié)能、減排、降耗，提高經(jīng)濟效益，同時實現(xiàn)制造過程的綠色化[5]。

綠色車間調(diào)度問題是傳統(tǒng)車間調(diào)度問題的擴展[3]，其中作業(yè)車間調(diào)度(job shop scheduling,JSP)應(yīng)用領(lǐng)域極其廣泛，綠色作業(yè)車間調(diào)度問題(green job shop scheduling,GJSP)需同時考慮綠色生產(chǎn)指標和經(jīng)濟指標，比傳統(tǒng)的JSP問題更復雜，求解難度更大。近年來，越來越多的學者對GJSP進行了研究。G.May等[6]分析了4種車間調(diào)度策略對作業(yè)車間調(diào)度完工時間和總能耗的影響，提出一種對多個優(yōu)化目標進行評估的綠色遺傳算法；A.Miguel等[7]研究了GJSP中能耗、完工時間和魯棒性之間的相互關(guān)系，指出魯棒性與能耗存在著明顯的制約關(guān)系；ZHANG R等[8]將機器產(chǎn)出速率作為變量建立了面向能耗的作業(yè)車間調(diào)度模型，提出一種多目標遺傳算法求解該模型；LIU Y等[9]研究了作業(yè)車間調(diào)度環(huán)境下能量的消耗情況，建立了非加工階段能量消耗和總加權(quán)延遲時間的多優(yōu)化目標模型，采用非支配排序遺傳算法求得Pareto最優(yōu)前端。

綜上所述，GJSP問題的研究尚處于起步階段，亟需建立更加貼合實際生產(chǎn)的多目標綠色作業(yè)車間調(diào)度問題模型，并結(jié)合問題特性設(shè)計更加有效的求解方法。本文針對多目標GJSP問題開展研究，建立兼顧最大完工時間指標、低碳指標和最大總拖期時間指標的多目標GJSP模型，低碳指標中增加了工件更換裝夾方式時機器調(diào)整狀態(tài)的碳排放量；提出改進的NSGA-Ⅱ進行優(yōu)化求解，設(shè)計基于N5鄰域結(jié)構(gòu)和非支配關(guān)系的種群個體局部搜索策略；構(gòu)造15組不同規(guī)模的多目標GJSP問題實例進行驗證，計算結(jié)果證明了模型和算法的有效性。

1 多目標綠色作業(yè)車間調(diào)度問題模型

1.1 問題描述

本文求解的多目標GJSP可描述為：n個工件在m臺機器上加工，已知每個工件包含的所有工序及工序的加工順序，每道工序的加工機器、加工時長和加工時冷卻液消耗量，通過合理安排每臺機器上工件的加工順序，尋找出一組兼顧綠色指標、效率指標及其他性能指標的均衡解。

多目標GJSP的目標是確定表1中每臺機器(M1，M2，M3)上各工件(J1，J2，J3)的加工順序及每道工序的開始時間，以同時兼顧多種性能指標。

表1 3個工件的加工信息

1.2 混合整數(shù)規(guī)劃模型

本文求解的多目標GJSP同時優(yōu)化以下3個目標：最小化最大完工時間(Cmax)、最小化總碳排放量(Catotal)、最小化總拖期時間(Tatotal)，并滿足以下假設(shè)條件：

(1)同一工件的加工工序所使用的刀具是固定不變的。

(2)每臺機器上使用的冷卻液、潤滑油均采用同一類型。

(3)同一機器加工任意工序時運行功率不變。

(4)同一機器同一時間只能加工一個工件。

(5)同一個工件同一個時刻只能在一臺機器上加工。

(6)每一道工序一旦開始便不能中斷。

基于上述假設(shè)條件，目標函數(shù)定義如下。

(1)最小化最大完工時間f1

MinCmax={maxCi，i=1，…，n},

(1)

式中，Ci為工件Ji的完工時間。

(2)最小化總碳排放量f2

MinCatotal=Cproc+Cidle+Cfit+Ccold+Coil=

(2)

機器運轉(zhuǎn)消耗電能引起的碳排放由機器的啟動、預(yù)熱、加工、空轉(zhuǎn)、停止這5個階段組成[10]，本文在此基礎(chǔ)之上增加了工件更換裝夾方式時機器調(diào)整狀態(tài)的碳排放量。對于多目標GJSP問題，考慮到機器的啟動、預(yù)熱、停止3個階段的能耗僅與機器的啟動次數(shù)有關(guān)，可視為常量不予考慮。因此，在零件制造過程中碳排放量影響因素包含機器負載運轉(zhuǎn)消耗電能引起的碳排放Cproc、機器空轉(zhuǎn)的能耗碳排放Cidle、更換裝夾方式時機器調(diào)整能耗碳排放Cfit、冷卻液消耗引起的碳排放Ccold、潤滑油損耗引起的碳排放Coil。

式(2)中使用的符號說明如表2所示。

(3)最小化總拖期時間f3

表2 式(2)符號含義

(3)

式中，di為第i個工件的交貨期。

對于多目標GJSP需滿足以下約束條件：

(1)CTi，j-PTi，j+M(1-Yi(h，j))≥CTi，h，i∈{1，2，…，n};j，h∈{1，2，…，m}。

(2)CTi，j-CTq，j-tfq，i+M(1-Xj(i，q))≥PTi，j，i，q∈{1，2，…，n};j∈{1，2，…，m}。

(3)CTi，j≥STi，j+PTi，j，i∈{1，2，…，n};j∈{1，2，…，m}。

(4)STJk，j≥CTJk-1，j+tfJk-1，j，j∈(1，2，…，m)。

上述約束條件中：CTi，j為工件i在機器j上的完工時間；CTq，j為工件q在機器j上的完工時間；CTJk-1，j為機器j上第k-1個加工任務(wù)的完工時間；CTi，h為工件i在機器h上的完工時間；STi，j為工件i在機器j上的開始加工時間；STJk，j為機器j上第k個加工任務(wù)的開始加工時間；PTi，j為工件i在機器j上的加工時長；tfq，i為工件q與工件i之間機器調(diào)整時間；M是一個足夠大的正數(shù)；Yi(h，j)，Xj(i，q)為決策變量，其含義為

2 用改進的NSGA-Ⅱ求解多目標GJSP

本文在基本NSGA-Ⅱ框架下，結(jié)合多目標GJSP特性，設(shè)計了基于N5鄰域結(jié)構(gòu)和非支配排序的局部搜索策略[11]，提出改進的NSGA-Ⅱ?qū)Χ嗄繕薌JSP進行求解。

2.1 編碼與解碼

本文采用基于工序的編碼方法[12]對種群中個體進行編碼。解碼是將染色體還原成一個可行調(diào)度的過程，本文應(yīng)用插入式貪婪解碼算法[7]進行解碼，獲得主動調(diào)度解。

2.2 種群初始化及適應(yīng)度評價方法

種群中每個個體代表著一種可行的調(diào)度解，在對個體初始化時按照編碼方法隨機調(diào)整染色體中基因的排列順序，對排序后的染色體進行主動解碼操作，最后根據(jù)式(1)～(3)計算個體的各目標函數(shù)值。

本文設(shè)計的算法采用了NSGA-Ⅱ中的快速非支配排序、擁擠距離作為評價方法比較種群個體的優(yōu)劣。種群中非支配等級低的個體的適應(yīng)度優(yōu)于非支配等級高的個體，對于同一等級中的個體，擁擠距離大的個體具有更好的適應(yīng)度值。

2.3 種群個體的選擇、交叉與變異操作

進行選擇操作時，對種群中的個體采用錦標賽的方法選擇，優(yōu)先選擇非支配等級低的個體染色體，相同等級下選擇擁擠距離大的個體。

交叉操作決定了算法的全局搜索能力，它要求盡量保留父代個體的優(yōu)良基因，本文采用文獻[12]中交叉算子(precedence operation crossover，POX)，變異操作是將染色體基因序列上的某些基因位上數(shù)值進行變動的過程，本文采用交換變異法變異，相互交換不同基因位上的數(shù)值。

2.4 基于N5鄰域結(jié)構(gòu)及非支配關(guān)系的個體局部搜索策略

為了增強算法局部搜索能力，本文在算法中設(shè)計基于N5鄰域結(jié)構(gòu)及非支配排序的個體局部搜索策略。如圖1所示，鄰域結(jié)構(gòu)N5是通過交換關(guān)鍵路徑上的關(guān)鍵工序塊產(chǎn)生新的鄰域解[13]。

圖1 N5鄰域結(jié)構(gòu)

基于N5鄰域結(jié)構(gòu)及非支配關(guān)系的個體局部搜索策略流程如圖2所示，具體流程描述如下。

步驟1 統(tǒng)計當前種群個體的總數(shù)目pu，令i=1，i為當前選擇的個體。

步驟2 對當前個體i采用N5鄰域結(jié)構(gòu)的第一步移動操作產(chǎn)生鄰域個體Ti。

步驟3 對鄰域個體Ti進行解碼操作，計算鄰域個體Ti的各個目標函數(shù)值(Cmax,Ctotal,Catotal)，如果個體Ti的各目標函數(shù)值均小于當前個體i的相應(yīng)目標函數(shù)值即fj(Ti)

圖2 基于N5鄰域結(jié)構(gòu)及非支配關(guān)系的個體局部搜索策略

步驟4 對當前個體i采用N5鄰域結(jié)構(gòu)的第二步移動操作產(chǎn)生鄰域個體Ti。

步驟5 對鄰域個體Ti進行解碼操作，計算鄰域個體Ti的目標函數(shù)值(Cmax，Tatotal，Catotal)，如果個體Ti支配個體i(Tii)，則將個體Ti替換個體i；否則保留當前個體i順序執(zhí)行。

步驟6 令i=i+1，判斷i是否大于pu，當i大于pu時，結(jié)束循環(huán)，否則跳轉(zhuǎn)到步驟2。

2.5 用INSGA-Ⅱ求解多目標GJSP的總流程

結(jié)合上述算法關(guān)鍵步驟的描述，用INSGA-Ⅱ(improved，INSGA-Ⅱ)求解多目標GJSP的總流程如圖3所示。

步驟1 設(shè)定INSGA-Ⅱ算法的參數(shù)：算法迭代次數(shù)Genmax，種群數(shù)目N，選擇概率Ps，交叉概率Pc，變異概率Pm，Pareto解集最大數(shù)目MaxSize。

步驟2 初始化N個種群個體，定義該種群為父代種群P；令Gen=0。

步驟3 對種群P中的個體應(yīng)用插入式貪婪算法解碼，得到每個個體的主動調(diào)度解。

圖3 INSGA-Ⅱ求解流程圖

步驟4 計算解碼后個體的目標函數(shù)值，根據(jù)種群個體的各個目標函數(shù)值，對種群P進行快速非支配排序，確定每個個體當前的非支配等級。

步驟5 更新Pareto解集。

步驟5.1 如果當前Pareto解集為空時，將當前種群中非支配等級為1的個體(irank=1)存入Pareto解集；如果當前種群P中irank=1個體數(shù)目大于MaxSize，計算當前非支配等級個體的擁擠距離，按照擁擠距離從大到小依次填入Pareto解集中。

步驟5.2 如果當前Pareto解集不為空時，剔除種群P中與當前Pareto解集中相同的個體，種群P中irank=1個體和Pareto解集中的個體存入種群Ptemp中，對種群Ptemp進行快速非支配排序及擁擠距離計算，如果種群Ptemp中irank=1的個體數(shù)目大于Pareto解集MaxSize，按照擁擠距離依次填入Pareto解集中，否則直接將irank=1個體存入Pareto解集。

步驟6 對種群P中的個體進行選擇、交叉及變異，生成子代種群Q。

步驟7 剔除種群P和種群Q中相同的個體，合并種群P和種群Q為種群PN。

步驟8 根據(jù)種群PN中個體的非支配等級，構(gòu)建非支配等級曲面{F1，F(xiàn)2，…,Fn}。

步驟9 在種群PN中選擇N個個體形成種群P。

步驟10 根據(jù)2.4節(jié)中基于N5鄰域結(jié)構(gòu)及非支配關(guān)系的個體局部搜索策略，更新種群P中個體。

步驟11 令Gen=Gen+1，如果Gen>Genmax，輸出Pareto解集，否則跳轉(zhuǎn)到步驟3。

3 算例驗證

由于缺乏多目標GJSP基準測試實例，本文設(shè)計15組算例進行測試，并與基本的NSGA-Ⅱ算法進行對比，驗證本文提出改進算法的有效性。

3.1 算例信息

根據(jù)表3～5的工件加工信息制定表6～8的5組基準測試實例。

表3 10個工件在6臺機器上的加工信息

續(xù)表3

表4 10個工件在10臺機器上的加工信息

表5 10個工件在20臺機器上的加工信息

表6 6臺機器加工的GJSP實例

表7 10臺機器加工的GJSP實例

表8 20臺機器加工的GJSP實例

以表6為例，表9為該實例各機器在不同生產(chǎn)階段的運行功率、冷卻液和潤滑油消耗量。同一機器加工不同工件時需要一定的調(diào)整時間更換工件，表10為加工不同工件時機器的調(diào)整時間(min)及交貨期(min)。

表9 各機器的相關(guān)參數(shù)

表10 加工不同工件時機器的調(diào)整時間

電能碳排放因子αe取全國碳排放因子的平均值0.6747 kg CO2/(kWh)，冷卻液的碳排放因子、潤滑油碳排放因子等參考香港中小企業(yè)碳審計工具箱[14]，處理廢液的碳排放因子2.75 kg CO2/L，冷卻液使用碳排放因子0.3 kg CO2/L，取兩者之和3.05 kg CO2/L作為冷卻液的碳排放因子αcold，潤滑油碳排放因子αoil為2.85 kg CO2/L。

使用Visual C++編程，進行優(yōu)化求解，運行程序的計算機為Intel(R)Core(TM)i5-7400 CPU@3.00 GHz，4.00 GB運行內(nèi)存。算法的實驗參數(shù)如表11所示。

表11 算法實驗主要參數(shù)

3.2 計算結(jié)果及分析

分別使用INSGA-Ⅱ算法和NSGA-Ⅱ?qū)ι鲜?5組測試實例進行計算，針對每組實例，獨立運行程序30次，分別統(tǒng)計30次獨立實驗中INSGA-Ⅱ和NSGA-Ⅱ算法求得的Pareto解，兩種算法獲得Pareto解的數(shù)目如表12所示。

表12 兩種算法計算獲得Pareto解的數(shù)目

針對表12中的每組問題實例，將兩種算法求得的所有Pareto解集進行合并，并統(tǒng)計合并解集中的非支配解，兩種算法合并解集的非支配解的數(shù)目如表13所示，同時給出了合并解集中的非支配解的數(shù)目。

表13 合并解集的非支配解數(shù)目

表13的計算結(jié)果顯示，排序后的非支配解主要來源于INSGA-Ⅱ求得的解，NSGA-Ⅱ求得的解多數(shù)被INSGA-Ⅱ的解支配，INSGA-Ⅱ找到的Pareto解的非支配等級更高，初步驗證了INSGA-Ⅱ算法優(yōu)于NSGA-Ⅱ算法。

為了形象地對比INSGA-Ⅱ和NSGA-Ⅱ各自的優(yōu)化效果，本文在表12中隨機抽取出了問題10×6、問題15×10及問題30×20實例進行詳細結(jié)果對比。

圖4 問題10×6的Pareto解分布對比Fig.4 Comparisons of Pareto solutions distribution for problem 10×6

圖4為表12中問題10×6的求解結(jié)果，通過對比分析，發(fā)現(xiàn)兩組解中部分解之間存在一些支配關(guān)系，對兩組解進行等級排序后，得到表13中問題10×6的計算結(jié)果，發(fā)現(xiàn)在兩組解中總共可以找到68個非支配解，其中 INSGA-Ⅱ找到了67個，NSGA-Ⅱ找到了1個，因此，在該組實例問題的求解中，INSGA-Ⅱ算法優(yōu)于NSGA-Ⅱ。再將問題的規(guī)劃擴大到問題15×10、問題30×20上時，兩者的優(yōu)化效果如圖5～6所示。

圖5 問題15×10的Pareto解分布對比

圖6 問題30×20的Pareto解分布對比

從圖5～6 中可以清晰地發(fā)現(xiàn)，藍點(NSGA-Ⅱ的Pareto解)基本上全部在紅點(INSGA-Ⅱ的Pareto解)的右上方，大部分的藍點被紅點支配。再將問題規(guī)模擴展到問題30× 20上時INSGA-Ⅱ算法表現(xiàn)更加優(yōu)秀，找到的95個非支配解均來源于INSGA-Ⅱ算法求得的Pareto解，驗證了INSGA-Ⅱ算法優(yōu)化效果好于NSGA-Ⅱ。

為了測試出INSGA-Ⅱ算法和NSGA-Ⅱ算法對于單個目標函數(shù)的優(yōu)化情況，本文根據(jù)統(tǒng)計的實驗數(shù)據(jù)將兩種算法求得各優(yōu)化目標(總碳排放量、完工時間和總拖期時間)的最小值進行對比，得出表14的計算結(jié)果。

表14 Pareto解中各優(yōu)化目標的最小值對比

從最大完工時間看，9組實例的INSGA-Ⅱ算法擁有與NSGA-Ⅱ算法相同的完工時間，另外6組實例INSGA-Ⅱ算法找到了更小的最大完工時間；從總碳排放量看，INSGA-Ⅱ上找到了更低的總碳排放量；從總拖期時間看，INSGA-Ⅱ也找到了更小的總拖期時間。對于單個目標函數(shù)，INSGA-Ⅱ算法優(yōu)化效果同樣好于NSGA-Ⅱ算法。

INSGA-Ⅱ算法是在NSGA-Ⅱ算法基礎(chǔ)上進行了基于N5鄰域結(jié)構(gòu)和非支配排序關(guān)系的局部搜索，通過移動個體關(guān)鍵路徑上關(guān)鍵工序塊，對個體進一步優(yōu)化，部分工件間的空轉(zhuǎn)時間、調(diào)整時間發(fā)生了變化，因此，能夠找到多個優(yōu)化目標相對更小的非支配解，從而支配了NSGA-Ⅱ求得的解，本文提出的INSGA-Ⅱ在求解MOGJSP問題時比基本的NSGA-Ⅱ性能更優(yōu)。圖7為問題30×20單個目標總碳排放量最小的甘特圖。

圖7 問題30×20總碳排放量最小解的甘特圖

4 結(jié)語與展望

針對多目標GJSP,建立以最小化最大完工時間、最小化總碳排放量、最小化最大總拖期時間為優(yōu)化目標的多目標混合整數(shù)規(guī)劃模型，模型中的低碳指標增加了工件更換裝夾方式時機器調(diào)整狀態(tài)的碳排放量，提出了改進的NSGA-Ⅱ算法求解多目標GJSP，主要的改進內(nèi)容是設(shè)計了基于N5鄰域結(jié)構(gòu)及非支配關(guān)系的個體局部搜索策略，設(shè)計了INSGA-Ⅱ算法的求解。計算結(jié)果顯示INSGA-Ⅱ算法具有更好的優(yōu)化性能。

在今后的工作中，將進一步研究綠色制造模式下的工藝規(guī)劃與車間調(diào)度集成優(yōu)化問題，并考慮引入NSGA-Ⅲ的一些機制設(shè)計出更有效的多目標優(yōu)化方法。