基于NSGA-Ⅲ算法的多目標集成工藝規(guī)劃與調(diào)度問題研究

張偉偉，李旭光，文笑雨，張靜，史文雋，張衛(wèi)正

(鄭州輕工業(yè)大學 計算機與通信工程學院,河南 鄭州 450002)

0 引 言

工藝規(guī)劃和車間調(diào)度是制造系統(tǒng)中非常重要的兩個子系統(tǒng)[1]，影響著制造系統(tǒng)的效率，將兩個系統(tǒng)集成并進行優(yōu)化，可以大幅度提高生產(chǎn)效率[2]。此外，企業(yè)在生產(chǎn)過程中往往需要考慮成本、效率、能耗等多個優(yōu)化目標，對多目標集成工藝規(guī)劃與調(diào)度(integrated process planning and scheduling，IPPS)的求解方法進行研究，不僅能提高制造產(chǎn)業(yè)效率，而且有利于減少生產(chǎn)過程的碳排放，因此，研究多目標IPPS具有非常重要的應用價值。

多目標IPPS問題存在多種柔性特征，問題的解空間很大，求解非常困難，是一個典型的NP難問題，傳統(tǒng)的數(shù)學方法很難解決該問題[3]。近幾十年，進化算法飛速發(fā)展，越來越多的學者使用進化算法解決多目標IPPS問題，如NSGA-Ⅱ算法[4]、人工蜂群算法[5-6]、聚類差分進化算法[7]、免疫自適應遺傳算法[8]等。使用進化算法求解多目標IPPS問題已成為近年來研究的熱點，截至目前，國內(nèi)針對多目標IPPS問題的研究主要以機器負載指標和時間指標為主，很少考慮能耗、碳排放等綠色指標，且研究以單目標、兩目標為主。隨著氣候變化加快，環(huán)境問題引起全球關(guān)注，以節(jié)能減排為目標的IPPS問題逐步受到廣大學者的重視，但研究主要以模型建立為主[9-11]，對求解方法的研究較少。因此，本文從減少工業(yè)制造過程的碳排放出發(fā)，建立以碳排放、完工時間和總拖期為優(yōu)化目標的IPPS問題，針對多目標IPPS問題求解方法研究的不足，提出一種集成變鄰域搜索的NSGA-Ⅲ算法，對多目標IPPS問題進行優(yōu)化求解，并通過實例對算法進行測試，測試結(jié)果驗證了所提算法的優(yōu)越性能。

1 IPPS問題描述與模型建立

1.1 IPPS問題描述

多目標IPPS問題的定義[13]：n個工件在m臺機器上加工，從工件的可選擇工藝、制造資源中確定工件在機器之間的傳遞序列、開工時間和完工時間，最終生成滿足各個目標的調(diào)度方案。

多目標IPPS問題需要解決3個問題：(1)在工藝規(guī)劃階段，確定每個工件的加工順序；(2)在工序的可選擇機器中確定加工機器，生成一條明確的工藝路線；(3)在車間調(diào)度階段，確定所有工件的全部工序在機器上的開始時間和結(jié)束時間。本文研究的多目標IPPS問題，調(diào)度方式為作業(yè)車間調(diào)度。柔性工藝規(guī)劃通過某工件的加工信息(表1)進行說明。該工件有5個加工特征(F1～F5)，在5臺機器上進行加工(M1～M5)，不同特征有不同的可選加工工藝。如特征F3有兩個可選工藝(O4～O5,O6～O7),每種工藝都需要兩道工序才能完成。每道加工工序有多臺可選加工機器，例如工序O1有2臺可選機器(M1,M2)。特征約束中，特征1必須在其他特征前加工，特征2必須在特征4前加工。

表1 某工件的加工信息Tab.1 Processing informations of a job

1.2 IPPS模型建立

本文在研究多目標IPPS問題時，作如下假設[5,11]：(1)工件間沒有優(yōu)先級關(guān)系，且每個工件同一時刻只能在一臺機器上加工；(2)每臺機器同一時刻只能加工一個工件，且完工前不能被打斷；(3)工序的加工時間包含該工序在機器上的準備時間；(4)考慮工件在機器間的傳輸時間，傳輸過程產(chǎn)生的碳排放僅與電動叉車的使用時間相關(guān)；(5)考慮機器上不同工件的轉(zhuǎn)換時間；(6)機床在一次調(diào)度中只啟動、關(guān)閉一次，且機床啟動、預熱和關(guān)閉產(chǎn)生的碳排放為常量；(7)機器上加工任意工件運行功率相同；(8)機器上使用同一類型的冷卻液?；谝陨霞僭O，本文研究以生產(chǎn)過程碳排放最小、最大完工時間最小和總拖期最小3個目標的優(yōu)化問題，其多目標優(yōu)化模型如式(1)～(4)所示[5,11]。

minf=[f1,f2,f3]T，

(1)

f1=Ctime=maxci，i∈[1,n],

(2)

(3)

(4)

式中：n為待加工工件總數(shù)；m為機器數(shù)目；ci為工件i的完工時間；di為工件i的交貨期；αe為電能碳排放因子；Econ為機床一次啟動、預熱和結(jié)束的系統(tǒng)能耗；Plr為機床l加工第r道工序的運行功率；PTrl為第r道工序在機床l上的加工時間；Ll為機床l在加工過程中冷卻液的消耗量；Tl為機床l上冷卻液的使用周期；αc為冷卻液的碳排放因子；Pcv為電動叉車的傳送功率。

式(1)為3目標優(yōu)化模型，式(2)為最大完工時間，式(3)為總拖期，式(4)為總碳排放。式(4)中：第一項為機床碳排放，包括機床加工時的能耗，機床一次啟動、預熱和結(jié)束的能耗；第二項為冷卻液消耗產(chǎn)生的碳排放；第三項為電動叉車運行產(chǎn)生的碳排放。模型約束條件參見文獻[5，11]。

2 基于NSGA-Ⅲ的多目標IPPS問題求解方法

2.1 多目標優(yōu)化問題定義

相對于單目標問題而言，多目標問題(multi-objective optimization problem,MOP)存在多個相互沖突的目標函數(shù)。一個多目標優(yōu)化問題可以用式(1)表示，其中f1,f2,f3為3個目標函數(shù)。由于多目標問題不同目標之間相互沖突，不能通過比較函數(shù)值的大小評估解的質(zhì)量，因此，在解決多目標問題時，通常根據(jù)解之間的“Pareto支配”關(guān)系[12]區(qū)別解的質(zhì)量好壞。最小化多目標問題的Pareto支配定義為

?i∈{1,…,m},fi(X)≤fi(X′)；?i∈{1,…,m},fi(X)

(5)

對于最小化多目標問題中的兩個解X和X′，X和Xv的任意目標函數(shù)值滿足fi(X)≤fi(X′)，且在目標空間中至少存在一個目標函數(shù)使得fi(X)

2.2 算法框架

目前，解決多目標IPPS問題的進化算法在選擇階段大多是基于非支配排序的方法，根據(jù)種群中個體的非支配等級選擇下一代種群。多目標IPPS問題非常復雜，解空間很大，隨著目標數(shù)增多，會出現(xiàn)大量的非支配解，導致個體選擇時計算量非常大，且不能有效保證種群的多樣性。在NSGA-Ⅱ基礎上，NSGA-Ⅲ算法提出一種基于空間參考點的選擇方式,有效地保持了種群的多樣性，并且提高了選擇過程的效率，適合解決多目標IPPS問題。

NSGA-Ⅲ算法是針對多目標連續(xù)優(yōu)化問題提出的，而IPPS問題是組合優(yōu)化問題，NSGA-Ⅲ算法不能直接解決該問題。本文在NSGA-Ⅲ算法的基礎上進行改進，提出3個關(guān)鍵策略求解多目標IPPS問題：(1)使用簡單、高效的編碼方式對種群進行初始化，初始化的每個個體都是一條可行的加工路線；(2)根據(jù)種群編碼方式，使用高效的交叉、變異方式，使算法在搜索過程中可以覆蓋整個目標空間，有利于保持種群的多樣性；(3)算法中的集成變鄰域搜索方法，使用不同的鄰域方法，以不同搜索方式加強算法的局部搜索能力。算法框架如表2所示。

表2 算法框架Tab.2 Algorithm framework

2.3 NSGA-Ⅲ算法改進

2.3.1 編碼與解碼

編碼和解碼方式會直接影響整個算法的效率，高效的編碼和解碼方式能使算法的各個部分更容易實現(xiàn)，提高算法的整體效率。本文在工藝規(guī)劃階段和調(diào)度階段采用不同的編碼方式。在工藝規(guī)劃階段采用文獻[5]的三段式編碼方式，該方法中，每條染色體包含三段不同序列，分別為特征順序序列、可選工序序列和可選機器序列。該編碼方式解碼時非常簡單，特征順序即特征加工順序，只需從可選工藝中確定特征相應的加工工藝，再根據(jù)工藝選擇相應的加工機器。在調(diào)度階段，采用基于工序的編碼方式[15]，該方法是車間調(diào)度問題研究中最常用的編碼方式，簡單高效。在解碼過程中，使用文獻[16]中貪婪解碼方法將編碼方案解碼為活動調(diào)度類型。

2.3.2 交叉和變異操作

在進行交叉和變異操作時，由于工藝規(guī)劃階段和調(diào)度階段使用不同的編碼方式，所以在兩個階段分別使用不同的交叉和變異方式：在工藝規(guī)劃階段，根據(jù)該階段采用的三段式編碼方式，繼續(xù)采用文獻[5]中的方法進行相應的交叉和變異操作；在調(diào)度階段，選用文獻[16]提出的POX(precedence operation crossover)交叉算子，對新產(chǎn)生的子代種群進行交叉操作；在變異階段，繼續(xù)，并沿用該文獻中使用的鄰域搜索變異算子，對新產(chǎn)生的子代種群進行變異操作。

2.3.3 種群選擇

從合并種群中選擇新的父代種群時，采用快速非支配排序方法[14]，根據(jù)種群中個體的非支配等級將合并種群進行分層，主要步驟如下。

步驟1根據(jù)支配的定義判斷種群中所有個體的支配關(guān)系。

步驟2根據(jù)支配關(guān)系，將種群中所有非支配個體保存在集合F1中，其余個體放入集合S中，對S中的個體進行非支配排序，并將其中的非支配解放入集合F2中。

步驟3重復上述步驟，直到所有個體都被分層。

將合并種群分層后，采用NSGA-Ⅲ[12]算法的選擇方式，從合并種群中挑選新的父代種群。假設種群初始化個數(shù)為N，父代種群個數(shù)為Pt，交叉、變異產(chǎn)生的新解個數(shù)為Qt，合并種群個數(shù)為Rt=Pt+Qt，并設St為一個空集。選擇過程簡述如下。

(2)根據(jù)目標數(shù)生成均勻的空間參考點，將Fl中個體做歸一化處理，計算Fl中每個個體到各個參考點的歐式距離，F(xiàn)l中的個體與距離最近的參考點建立聯(lián)系。

(3)計算各個參考點聯(lián)系的個體數(shù)，根據(jù)參考點聯(lián)系個體數(shù)的多少，從各個參考點關(guān)聯(lián)的個體中均勻選擇K個個體加入下一代，其中K=N-Pt+1。

2.3.4 變鄰域搜索

變鄰域搜索是一種非常有效的局部搜索方法，也是當前解決車間調(diào)度問題常用的一種方法。為加強算法的局部搜索能力，在NSGA-Ⅲ算法中集成變鄰域搜索方法。本文使用的變鄰域搜索方法包含3個不同的鄰域方法[17]，具體如下。

(1)N1為隨機全鄰域法。在子代個體中隨機選擇3個不同位置的基因,采用全排列生成5個新個體,從中挑選最好的1個取代原來的個體。

(2)N2為兩點交叉鄰域法。在子代個體中隨機選擇2個不同位置的基因，將其互換。

(3)N3為N5鄰域法。對于關(guān)鍵路徑上的關(guān)鍵塊,首塊只交換最后2個加工工序,相應的尾塊只交換前2個加工工序,所有的中間塊分別交換前2個加工工序和最后2個加工工序。

對于產(chǎn)生的子代種群，依次使用3個鄰域搜索方法，每種搜索方法重復使用，該方法不能再提高個體質(zhì)量時，換下一種搜索方法，直到3個搜索方法全部搜索完畢，鄰域搜索操作完成。主要步驟如下。

步驟1對子代種群中一個個體x，定義不同的鄰域搜索方法Nk，k=1,2,3。

步驟2設置k=1，重復以下步驟直到k=3。

步驟2.1根據(jù)鄰域搜索方法Nk產(chǎn)生鄰域解x′。

步驟2.2從鄰域解x′中找出最優(yōu)的個體x″。

步驟2.3判斷x″是否優(yōu)于x，如果好于x，則x=x″，k=1；否則令k=k+1。

2.3.5 Pareto解集更新方法

調(diào)度階段結(jié)束后，產(chǎn)生新的非支配解。判斷Pareto解集是否為空，解集為空時，將新產(chǎn)生的非支配解全部放入Pareto解集中；解集不為空時，Pareto解集中的解和新的非支配解合并，找到合并解集中的非支配，替換解集中原來的解。算法主要步驟如下：

步驟1將父代與子代合并，并從中挑選非支配解。

步驟2判斷外部Pareto解集是否為空，若解集為空，將非支配解全部放入解集當中；若解集不為空，則跳轉(zhuǎn)到步驟3。

步驟3將新產(chǎn)生的非支配解與Pareto解集當中的非支配解合并，找到合并解中新的非支配解，將Pareto解集重新放入Pareto解集當中。

2.3.6 NSGA-Ⅲ算法求解IPPS問題

基于以上對算法關(guān)鍵操作的描述，本文使用NSGA-Ⅲ算法求解IPPS問題，具體步驟如下。

步驟1設定算法中各個參數(shù)。

步驟2輸入待求解的IPPS問題，采用上文介紹的編碼方法，為每個工件初始化工藝路線種群。

步驟3設置工藝規(guī)劃階段算法的終止條件為最大迭代次數(shù)，使用上文方法對每個工件的工藝路線種群進行優(yōu)化，得到工件的工藝路線非支配解集。

步驟4從每個工件的工藝路線非支配解集中為每個工件隨機選擇一條工藝路線，輸入作業(yè)車間調(diào)度階段，根據(jù)每個工件選擇的工藝路線，采用上文介紹的編碼方法，初始化調(diào)度種群。

步驟5判斷NSGA-Ⅲ算法的迭代次數(shù)是否達到最大，如果迭代次數(shù)達到最大，跳轉(zhuǎn)到步驟8。如果沒有達到，則使用上文介紹的方法對調(diào)度種群進行優(yōu)化。

步驟6使用上文介紹的鄰域搜索方法，對經(jīng)過NSGA-Ⅲ算法產(chǎn)生的新調(diào)度種群進行局部搜索。

步驟7更新NSGA-Ⅲ算法當前的迭代次數(shù)，并跳轉(zhuǎn)到步驟5。

步驟8更新Pareto解集，判斷NSGA-Ⅲ算法的迭代次數(shù)是否達到最大，如果迭代次數(shù)達到最大，則算法結(jié)束，輸出Pareto解集，否則跳轉(zhuǎn)到步驟4。

3 結(jié)果與分析

上述求解IPPS問題的NSGA-Ⅲ算法使用Visual C++進行編寫，運行程序的計算機CPU為Core-(TM)i5-3230M(1.80GHz),4GB內(nèi)存。

3.1 測試實例

已有文獻中缺少考慮綠色制造的多目標IPPS問題測試實例，為了驗證算法有效性，以6種工件、5臺機器為例進行測試，工件間的調(diào)整時間見表3，機器間的轉(zhuǎn)運時間見表4，工件加工信息見表5，機器的能耗信息見表6。

表3 工件間調(diào)整時間Tab.3 Adjustment time between jobs h

表4 機器間的轉(zhuǎn)運時間Tab.4 Transmission time between machines

表5 工件加工信息Tab.5 Workpieces processing informations

續(xù)表5

表6 機器的能耗信息Tab.6 Energy consumption of the machines

(6)

式中：P*為算法找到的PF；P為算法真正的PF；d(v,p)為P*中的一個解v與P之間最小的歐氏距離；|P*|為P*的數(shù)量。

本文中IGD值越小代表結(jié)果越好。值得注意的是，在IPPS問題的測試實例上沒有真實的Pareto前沿，計算該指標時，將不同算法在同一個測試問題上進行20次測試，然后將測試得到的Pareto解集合并，在合并的解集中找到非支配解，將這個合并解集中的非支配解當作真實的Pareto前沿計算IGD值。

3.2 算法參數(shù)設置

電能碳排放因子αe取全國排放因子的平均值0.674 7 kg CO2/kWh，冷卻液碳排放因子參考香港中小型企業(yè)碳審計工具箱[19]，αc取碳排放因子和處理廢液碳排放因子之和，αc=3.05 kg CO2/L。在測試實例時，設定算法的整體最大迭代次數(shù)GIPPS為200，算法的其他參數(shù)如表7所示。

表7 算法參數(shù)設置Tab.7 Parameters setting

3.3 實驗結(jié)果與分析

為了測試本文算法在不同規(guī)模問題上的有效性，從6種工件中隨機挑選工件，組成7個不同規(guī)模的問題，問題2～7中都會出現(xiàn)相同的工件。在7個不同規(guī)模的問題上，本文算法與文獻[4]和[8]中的算法進行對比，同時，為了驗證本文算法中變鄰域搜索的有效性，不包含鄰域搜索的NSGA-Ⅲ算法同時參與對比，每個規(guī)模的問題進行20次測試。各個算法獲得的非支配解如表8所示，由于篇幅原因，只列舉了部分非支配解。算法對比的IGD值為20次測試的平均值，如表9所示。本文算法獲得的最優(yōu)解工藝路線見表10，該解對應的甘特圖見圖1。

表10 問題7的一個非支配解對應的工藝路線Tab.10 Process route corresponding to a non-dominated solution of problem 7

由表8可以看出，不同算法都可以找到比較不錯的非支配解，不同算法獲得的非支配解之間沒有明顯的支配關(guān)系；由表9可以看出，在問題2～7上，本文算法實驗結(jié)果的IGD值最小，說明本文算法獲得的非支配前沿最接近真實非支配前沿。隨著問題規(guī)模增大，與其他算法之間的差距更明顯，說明本文所提 算法在解決問題規(guī)模大的多目標IPPS問題時效果更好；由表9和圖1可以看出，本文算法獲得的非支配解是可行解，可以指導實際生產(chǎn)。

表8 不同算法獲得的非支配解Tab.8 Non-dominated solutions obtained by different algorithms

表9 不同算法實驗結(jié)果的平均IGD值Tab.9 Average IGD value of the experimental results of each algorithm

續(xù)表10

圖1 問題7的一個非支配解對應的甘特圖Fig.1 A Gantt chart corresponding to a non-dominated solution of problem 7

4 結(jié) 語

針對復雜的多目標IPPS問題，設計兼顧碳排放、完工時間、總拖期的多目標集成模型。提出了改進的NSGA-Ⅲ算法，算法采用編碼方式、選擇方式以及變鄰域搜索，使NSGA-Ⅲ算法可以高效地解決組合優(yōu)化問題。采用7個不同規(guī)模的測試實例對本文算法進行測試，測試結(jié)果證明了本文算法的可行性與準確性，且在求解大規(guī)模多目標IPPS問題時，比現(xiàn)有算法更有優(yōu)勢。該算法策略為復雜的多目標IPPS問題提供了一種有效的解決方案，為智能制造系統(tǒng)的排產(chǎn)優(yōu)化提供了決策依據(jù)。在今后的研究中，將對實際生產(chǎn)中的動態(tài)環(huán)境進行研究，如機器故障和急件加工的不確定事件，構(gòu)建不確定環(huán)境下的數(shù)學模型，并設計更為高效的算法，使研究成果實用性更好，能更好地指導實際生產(chǎn)。