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

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

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

0 引 言

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

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

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

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

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)，并滿足以下假設條件：

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

機器運轉消耗電能引起的碳排放由機器的啟動、預熱、加工、空轉、停止這5個階段組成[10]，本文在此基礎之上增加了工件更換裝夾方式時機器調整狀態(tài)的碳排放量。對于多目標GJSP問題，考慮到機器的啟動、預熱、停止3個階段的能耗僅與機器的啟動次數(shù)有關，可視為常量不予考慮。因此，在零件制造過程中碳排放量影響因素包含機器負載運轉消耗電能引起的碳排放Cproc、機器空轉的能耗碳排放Cidle、更換裝夾方式時機器調整能耗碳排放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個加工任務的完工時間；CTi，h為工件i在機器h上的完工時間；STi，j為工件i在機器j上的開始加工時間；STJk，j為機器j上第k個加工任務的開始加工時間；PTi，j為工件i在機器j上的加工時長；tfq，i為工件q與工件i之間機器調整時間；M是一個足夠大的正數(shù)；Yi(h，j)，Xj(i，q)為決策變量，其含義為

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

本文在基本NSGA-Ⅱ框架下，結合多目標GJSP特性，設計了基于N5鄰域結構和非支配排序的局部搜索策略[11]，提出改進的NSGA-Ⅱ對多目標GJSP進行求解。

2.1 編碼與解碼

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

2.2 種群初始化及適應度評價方法

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

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

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

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

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

2.4 基于N5鄰域結構及非支配關系的個體局部搜索策略

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

圖1 N5鄰域結構

基于N5鄰域結構及非支配關系的個體局部搜索策略流程如圖2所示，具體流程描述如下。

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

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

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

圖2 基于N5鄰域結構及非支配關系的個體局部搜索策略

步驟4 對當前個體i采用N5鄰域結構的第二步移動操作產(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時，結束循環(huán)，否則跳轉到步驟2。

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

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

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

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

步驟3 對種群P中的個體應用插入式貪婪算法解碼，得到每個個體的主動調度解。

圖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中個體的非支配等級，構建非支配等級曲面{F1，F(xiàn)2，…,Fn}。

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

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

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

3 算例驗證

由于缺乏多目標GJSP基準測試實例，本文設計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)階段的運行功率、冷卻液和潤滑油消耗量。同一機器加工不同工件時需要一定的調整時間更換工件，表10為加工不同工件時機器的調整時間(min)及交貨期(min)。

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

表10 加工不同工件時機器的調整時間

電能碳排放因子α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運行內存。算法的實驗參數(shù)如表11所示。

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

3.2 計算結果及分析

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

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

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

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

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

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

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

圖4為表12中問題10×6的求解結果，通過對比分析，發(fā)現(xiàn)兩組解中部分解之間存在一些支配關系，對兩組解進行等級排序后，得到表13中問題10×6的計算結果，發(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的計算結果。

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

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

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

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

4 結語與展望

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

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