黃夏寶，魏淑玲

(1.福建江夏學(xué)院 工商管理學(xué)院，福建 福州 350108；2.福州大學(xué) 經(jīng)濟與管理學(xué)院，福建 福州 350116)

隨著全球經(jīng)濟的高速發(fā)展，能源消耗迅速、環(huán)境污染嚴(yán)重等問題日益突出，如何實現(xiàn)節(jié)能減排、減少環(huán)境污染成為當(dāng)下亟需解決的重要問題之一。制造業(yè)產(chǎn)生了全球近1/3的能源消耗,制造過程中能源的大量消耗和CO2的過度排放對環(huán)境造成嚴(yán)重影響。因此，減少制造過程中的能量消耗，實現(xiàn)低碳的綠色制造是新時代下制造業(yè)的發(fā)展要求[1]。

在柔性作業(yè)車間中，允許工件的工序在不同的機器上加工，更符合現(xiàn)代制造車間的實際情況。同時，由于柔性作業(yè)車間調(diào)度問題(flexible job-sop scheduling problem, FJSP)是NP-hard問題，眾多學(xué)者已對此問題展開了深入研究。單目標(biāo)FJSP僅關(guān)注車間調(diào)度中單個性能指標(biāo)的優(yōu)化。LI等[2]以最大完工時間最小為目標(biāo)，將遺傳算法局部搜索方法相結(jié)合，綜合提升算法的搜索能力。SOBEYKO等[3]結(jié)合基于關(guān)鍵路徑的局部搜索和變鄰域搜索方法，求解總拖期最小的大規(guī)模FJSP。ZHENG等[4]提出基于知識引導(dǎo)的果蠅優(yōu)化算法，求解以最大完工時間最小為目標(biāo)的雙資源約束FJSP。而在生產(chǎn)實踐中往往需要同時考慮多個目標(biāo)，使得多目標(biāo)FJSP成為了近年的研究熱點問題。在這些研究中，初期多采用運籌學(xué)方法和啟發(fā)式調(diào)度規(guī)則獲取全局最優(yōu)解。隨著調(diào)度模型的復(fù)雜化和目標(biāo)的多樣化，遺傳算法、免疫算法、蟻群算法、模因算法[5]、離散病毒算法[6]等智能算法開始廣泛應(yīng)用于多目標(biāo)FJSP問題的求解。徐華等[7]提出一種混合離散蝙蝠算法，通過優(yōu)先指派規(guī)則產(chǎn)生初始種群，同時采用位置變異策略實現(xiàn)快速搜索，有效地避免算法過早收斂。仲于江等[8]提出一種基于小生境粒子群算法，利用小生境技術(shù)計算得到粒子刪除概率，并根據(jù)該概率值更新外部精英存檔，從而保證算法能夠獲取更多優(yōu)質(zhì)的調(diào)度解。以上文獻多為針對2個或3個目標(biāo)的FJSP研究，4個目標(biāo)及以上的高維多目標(biāo)FJSP問題的研究較少。張超勇等[9]提出改進的非支配排序遺傳算法能夠有效求解以時間、成本、設(shè)備利用率等經(jīng)濟指標(biāo)為優(yōu)化目標(biāo)的6目標(biāo)FJSP問題，但得到的非支配解的數(shù)量過多，決策者很難直接從中篩選出最優(yōu)的調(diào)度解。白俊杰等[10]在算法中引入偏好信息來引導(dǎo)粒子向決策者偏好的Pareto前沿收斂，一定程度上縮小了高維多目標(biāo)FJSP的搜索空間。林震等[11]利用基于多交叉策略的元胞多目標(biāo)遺傳算法求解以瓶頸機器負(fù)荷、總機器負(fù)荷、加工成本、制造工期為目標(biāo)的高維FJSP問題，通過改進的精英策略提升算法收斂速度。黃利福等[12]在粒子群算法中引入模糊理論，以模糊物元的相似度作為適應(yīng)度值引導(dǎo)算法進化，求解優(yōu)化多個經(jīng)濟指標(biāo)的高維多目標(biāo)FJSP。

隨著社會節(jié)能環(huán)保意識的增強，柔性作業(yè)車間低碳調(diào)度也逐漸引起學(xué)者的重視。蔣增強等[13]提出基于設(shè)備狀態(tài)能耗曲線的低碳策略，并設(shè)計基于血緣變異的非支配排序遺傳算法解決算法過早收斂的問題。唐立力[14]提出改進的候鳥優(yōu)化算法求解能耗目標(biāo)最小的低碳調(diào)度問題。雷德明[15]提出一種基于新型優(yōu)化機理的教學(xué)優(yōu)化(TLBO)算法最小化總碳排放和平均延遲時間。張國輝等[16-17]對考慮機器速度的低碳FJSP模型展開研究，通過控制機器的加工速度以降低機器的碳排放總量。姜天華[18]提出改進的灰狼優(yōu)化算法求解能耗成本和時間成本加權(quán)和最小的低碳調(diào)度模型。李明等[19]提出一種新型帝國競爭算法求解4目標(biāo)的低碳FJSP問題，搜索到高質(zhì)量的Pareto最優(yōu)解。

總體而言，高維多目標(biāo)FJSP和低碳FJSP是當(dāng)前調(diào)度問題研究的熱點和難點，但仍都處于起步階段[20]。在高維多目標(biāo)FJSP問題研究中，對于完工時間、拖期等經(jīng)濟指標(biāo)的研究較多，而對于能量消耗等綠色指標(biāo)的綜合研究還較少。筆者綜合考慮生產(chǎn)效率、機器利用率等經(jīng)濟指標(biāo)以及能源消耗指標(biāo)，建立了以最大完工時間、瓶頸機器負(fù)荷、總機器負(fù)荷、能量消耗為目標(biāo)的高維多目標(biāo)FJSP低碳調(diào)度模型。該模型不但更貼近生產(chǎn)實際，而且順應(yīng)了綠色制造的理念。在高維多目標(biāo)FJSP中，隨著目標(biāo)維數(shù)的增多，種群中Pareto解的數(shù)量呈指數(shù)上升，傳統(tǒng)的多目標(biāo)優(yōu)化方法選擇壓力不足，無法從眾多Pareto解中篩選出最優(yōu)調(diào)度解。為增強算法選擇壓力，獲取一組均勻分布的優(yōu)良調(diào)度解，筆者設(shè)計了改進的NSGA-Ⅲ算法求解高維多目標(biāo)FJSP低碳調(diào)度問題。

1 高維多目標(biāo)柔性作業(yè)車間低碳調(diào)度模型

1.1 高維多目標(biāo)FJSP低碳調(diào)度問題描述

n個工件在m臺機器上加工，每個工件都由若干道工序組成；每道工序可以在不同的機器上加工；工序加工時間和能量能耗與選擇的加工機器相關(guān)。低碳調(diào)度的目標(biāo)是為每道工序分配合適的機器，并確定每臺機器上工序的加工順序，以實現(xiàn)經(jīng)濟指標(biāo)和綠色指標(biāo)的協(xié)同優(yōu)化。低碳FJSP模型還需滿足以下約束條件：①某一時刻，同一臺機器至多只能加工一個工件；②同一道工序只能在一臺機器上加工；③工序在機器上加工時，不允許被中斷，即加工是非搶占式的；④所有工件的優(yōu)先級相同；⑤不同工件的工序之間不存在先后約束，同一工件的工序間存在順序約束關(guān)系；⑥所有零件在t=0時刻都可以被加工。

1.2 高維多目標(biāo)FJSP低碳調(diào)度模型

1.2.1 參數(shù)與變量設(shè)置

為更好地描述高維多目標(biāo)FJSP低碳調(diào)度模型，定義以下參數(shù)和變量：n為工件總數(shù)；m為機器總數(shù)；J={J1,J2,…,Jn}為工件集合,i=1,2,…,n；M={M1,M2,…,Mm}為機器集合,k=1,2,…,m；hi為工Ji的總工序數(shù);Oij為工件i的第j道工序,其可選加工機器數(shù)為mij；tijk、qijk、eijk分別表示工序Oij在機器Mk上的加工時間、加工功率和加工能耗；sij、cij分別為工序Oij的開始加工時間和完工時間；Ci為工件Ji的完工時間；當(dāng)工序Oij在機器Mk上加工時，xijk=1，否則xijk=0；工序Oij先于工序Ohl在Mk上加工時，ykijhl=1，否則ykijhl=0；L為一個很大的正整數(shù)。

1.2.2 能量消耗指標(biāo)

生產(chǎn)過程中資源消耗包括機器加工產(chǎn)生的能量消耗以及工件原材料、切削液等物料資源消耗，其中受調(diào)度方案影響的是加工電能消耗[21]。因此，筆者采用電能消耗作為能量消耗指標(biāo)的度量，能量消耗系數(shù)矩陣可表示為：

E={eijk}m×n

(1)

機械加工過程中，機器維持自身運轉(zhuǎn)需要消耗很大一部分功率，即機器空載功率qu。當(dāng)機器空閑時，輸入功率全部用于機器空轉(zhuǎn)。當(dāng)機器加工工件時，輸出功率ql的一部分用于維持機器自身運轉(zhuǎn)，另一部分用于承擔(dān)負(fù)荷帶來的功率損耗，即載荷損耗功率qa，其余用于完成工件的切削加工，即切削功率qc。則機器的功率平衡方程[22]可表示為：

ql=qu+qa+qc

(2)

(3)

(4)

因此，可利用機器空載功率和工序加工時間數(shù)據(jù)建立能量消耗系數(shù)矩陣，計算機器加工的能量消耗，然后通過比較不同調(diào)度方案下能量消耗總量的大小篩選出節(jié)能的調(diào)度方案。

1.2.3 調(diào)度模型建立

筆者綜合考慮生產(chǎn)效率、設(shè)備利用率和能量消耗等指標(biāo)，建立了考慮能量消耗的多目標(biāo)低碳FJSP調(diào)度模型。模型包含4個優(yōu)化目標(biāo)：最大完工時間最小(CM)、瓶頸機器負(fù)荷最小(WM)、機器總負(fù)荷最小(WT)、機器能量消耗最小(ET)。

目標(biāo)函數(shù)：

(5)

(6)

(7)

(8)

約束條件：

sij+xijk×tijk≤cijk

(9)

cij≤si(j+1)

(10)

sij+pijk≤shl+L(1-ykijhl)

(11)

cij≤si(j+1)+L(1-ykihl(j+1))

(12)

(13)

式(9)和式(10)表示同一個工件的工序存在先后順序，工件的前一道工序完成后才能加工下一道工序；式(11)和式(12)表示在同一時刻，同一臺機器只能加工一道工序；式(13)表示機器資源約束，即同一道工序在同一時刻只能在一臺機器上加工。

2 改進的NSGA-Ⅲ算法

為求解高維多目標(biāo)FJSP低碳調(diào)度問題，設(shè)計了改進的NSGA-Ⅲ調(diào)度算法。首先，利用快速非支配排序算法對種群進行排序；其次，在高維目標(biāo)空間中引入均勻參考點，利用基于參考點的小生境選擇機制篩選出優(yōu)良個體?；趨⒖键c的小生境選擇把目標(biāo)空間劃分為多個子區(qū)域，算法可以在多個子空間中均勻搜索，在保證算法收斂性的同時提高了解的多樣性[25]。改進的NSGA-Ⅲ算法的具體流程如下：

(1)初始化參考點和遺傳算法參數(shù)，設(shè)計染色體編碼，利用隨機初始化方法生成初始化種群P0，種群個體數(shù)為N。

(2)執(zhí)行交叉變異產(chǎn)生第v代子代種群Qv，合并第v代子代種群與父代種群Pv，得到個體數(shù)為2N的種群Rv=Pv+Qv。

(3)利用基于Pareto支配的快速非支配排序法對種群Rv進行排序，獲得各個支配層個體F1、F2、…、Fw，l=1，2,…,w。

(4)從第一層非支配層開始，依次將非支配層中的個體加入到新種群Sv中，直到Sv中的個體大于等于N，其中使得Sv中個體數(shù)首次大于等于N的最后一層非支配層為Fl。

(6)利用基于參考點的小生境選擇機制從最后一個非支配層Fl中選擇出K=N-|Pv+1|個個體，得到新種群Sv。

(7)迭代直至滿足最大迭代次數(shù)。

2.1 編碼與解碼

采用基于工序和基于機器相結(jié)合的雙層編碼方法，分別確定工序排序和機器分配。基于工序部分的編碼長度等于所有工件的總工序數(shù)，每個工件的工序用相應(yīng)的工件號表示，工件號出現(xiàn)的順序即為工序的加工順序。基于機器的編碼長度也等于所有工件的總工序數(shù)，染色體從左到右依次按照工件號和工序的順序進行排列?；蛭簧系恼麛?shù)表示當(dāng)前工序選擇的機器在可選機器集中的順序編號，保證了后續(xù)遺傳操作產(chǎn)生的解仍是可行解。

基于該編碼方式，采用插入式貪婪解碼算法進行染色體解碼，確保產(chǎn)生活動調(diào)度解。依次讀取染色體的工序，將工序插入到可利用的機器空閑間隔時間中以減少機器空轉(zhuǎn)，從而提高機器利用率、縮短最大完工時間。

2.2 交叉與變異

筆者針對雙層編碼選用不同的交叉操作，基于工序的編碼采用改進的基于工序優(yōu)先順序(IPOX)的交叉方法，基于機器的編碼采用多點交叉(MPX)操作。IPOX交叉方法僅交叉父代染色體中工序的加工順序，不改變機器分配。首先將工件隨機分成兩個子集J、J′；然后將父代中包含J的工件復(fù)制到子代C1，P2中包含J′的工件復(fù)制到子代C2，保持位置和順序不變；將P2中包含J′的工件按順序插入C1空白處，P1中包含J的工件插入C2。MPX交叉操作僅交叉父代染色體中工序的加工機器，不改變加工順序。隨機生成一個與機器染色體等長的0、1數(shù)列R；選出P1、P2中與R中的“1”位置對應(yīng)的機器號，交叉復(fù)制到C2、C1，保持原有的位置和順序；將P1、P2中剩余的基因復(fù)制到C1、C2。

變異操作通過對染色體施加小規(guī)模擾動以增加種群多樣性，筆者對雙層編碼采用不同的變異方式。基于工序的編碼執(zhí)行插入式變異，在工序排序部分隨機選擇一個基因，插入到另一個隨機的基因位并保持工序的機器分配不變?；跈C器的編碼在執(zhí)行變異時，隨機選擇染色體上的r個基因，依次在各工序的加工機器集中隨機選取機器進行替換。

2.3 基于參考點的小生境選擇機制

2.3.1 歸一化目標(biāo)值和參考點

(14)

(15)

2.3.2 關(guān)聯(lián)參考點

連接參考點與標(biāo)準(zhǔn)化超平面的原點構(gòu)造基于參考點的參考線，計算種群中的每個個體到參考線的垂直距離。選擇與參考線垂直距離最短的個體，將該個體與對應(yīng)的參考點關(guān)聯(lián)。三維目標(biāo)空間中關(guān)聯(lián)參考點的示意圖如圖1所示，其中空心點表示目標(biāo)空間中的均勻參考點，虛線表示基于參考點的參考線，與虛線連接的實心點表示與該參考點相關(guān)聯(lián)的種群個體。

圖1 三維目標(biāo)空間關(guān)聯(lián)參考點示意圖

2.3.3 小生境選擇機制

3 實例驗證分析

3.1 實驗平臺及參數(shù)設(shè)定

改進的NSGA-Ⅲ算法采用Matlab 2016a編程，程序在CPU主頻2.20 GHz，內(nèi)存4G的計算機上運行。選取Kacem基準(zhǔn)問題中的3種不同規(guī)模的基準(zhǔn)實例進行測試，包括8×8 P-FJSP、10×10 T-FJSP、15×10 T-FJSP。由于基準(zhǔn)實例中沒有功率數(shù)據(jù)，筆者采用隨機函數(shù)生成法生成功率數(shù)據(jù)，功率數(shù)據(jù)為1～5之間的隨機整數(shù)。合理的參數(shù)設(shè)置很大程度影響算法的性能，為保證算法的求解質(zhì)量和運行效率，參考文獻[27]和文獻[28]中的參數(shù)，設(shè)置實驗參數(shù)如下：交叉概率為0.7，變異概率為0.1，種群個體數(shù)為120，最大迭代次數(shù)T為200，參考點個數(shù)H為120。

3.2 仿真結(jié)果分析

選取3種不同規(guī)模的基準(zhǔn)實例，驗證改進的NSGA-Ⅲ調(diào)度算法求解不同調(diào)度問題的有效性。其中10×10 T-FJSP、15×10 T-FJSP基準(zhǔn)實例是完全FJSP調(diào)度問題，允許每個工序在所有可選機器上加工，8×8 P-FJSP是部分FJSP問題。8×8 P-FJSP規(guī)模實例的一組解甘特圖如圖2所示，相應(yīng)的目標(biāo)值分別為CM=15，WM=12，WT=74，ET=222；10×10 T-FJSP規(guī)模實例的一組解甘特圖如圖3所示，相應(yīng)的目標(biāo)值分別為CM=8，WM=7，WT=44，ET=128；15×10 T-FJSP規(guī)模實例的一組解甘特圖如圖4所示，相應(yīng)的目標(biāo)值分別為CM=15，WM=15，WT=104，ET=26。

圖2 8×8 P-FJSP甘特圖

圖3 10×10 T-FJSP甘特圖

圖4 15×10 T-FJSP甘特圖

圖5 改進的NSGA-Ⅲ算法的最大完工時間收斂曲線

圖6 改進的NSGA-Ⅲ算法的瓶頸機器負(fù)荷收斂曲線

改進的NSGA-Ⅲ調(diào)度算法求解15×10 T-FJSP問題的最大完工時間收斂曲線如圖5所示，瓶頸機器負(fù)荷收斂曲線如圖6所示，總機器負(fù)荷收斂曲線如圖7所示，能量消耗收斂曲線如圖8所示?？梢钥闯?，4個目標(biāo)在60代時均收斂于最優(yōu)值，說明在60代已達到4個目標(biāo)的綜合優(yōu)化。該結(jié)果表明NSGA-Ⅲ調(diào)度算法具有較強的選擇壓力，能夠在高維目標(biāo)空間中均勻搜索，快速收斂得到均衡各目標(biāo)的低碳調(diào)度解。

圖7 改進的NSGA-Ⅲ算法的總機器負(fù)荷收斂曲線

圖8 改進的NSGA-Ⅲ算法的能量消耗收斂曲線

3.3 算法結(jié)果對比

為驗證算法中基于參考點的小生境選擇機制的有效性，選取與NSGA-Ⅲ算法框架相似的NSGA-Ⅱ算法對3種不同規(guī)模的基準(zhǔn)實例的運行結(jié)果進行對比。采用文獻[29]中的解質(zhì)量指標(biāo)(QS)和空間分布度(DS)指標(biāo)作為解的分布性度量指標(biāo)。QS表示算法的解在新的Pareto解集合中所占的比例，用于衡量解集的非支配性。即把兩種算法的解集進行對比，生成新的非支配解集合，并計算其中屬于各自算法的解的比例。QS越接近1，表明該算法的求解質(zhì)量越高。DS表示非支配解在Pareto前沿上分布的均勻程度，通過解集中個體之間的距離測度。DS越小，則該非劣解集的分布越均勻。T表示算法收斂到最優(yōu)值的時間，由算法多次運行后取平均值得到。T越小，則算法收斂速度越快。對比實驗結(jié)果如表1所示。

表1 Kacem測試集實驗結(jié)果對比表

由表1可知，改進的NSGA-Ⅲ算法的解質(zhì)量指標(biāo)(QS)、空間分布度指標(biāo)(DS)均優(yōu)于NSGA-Ⅱ算法，且隨著基準(zhǔn)實例規(guī)模的增大，NSGA-Ⅲ算法的QS值越優(yōu)。這表明改進的NSGA-Ⅲ調(diào)度算法能夠有效求解較大規(guī)模的FJSP問題，獲得均勻分布的優(yōu)良調(diào)度解。該結(jié)果體現(xiàn)了基于參考點的小生境選擇機制的有效性，能夠在高維目標(biāo)空間中均勻搜索，獲得優(yōu)良的Pareto非支配解。

從收斂時間T看，在8×8 P-FJSP中，改進的NSGA-Ⅲ算法的收斂速度稍快于NSGA-Ⅱ算法，而在另外兩個規(guī)模稍大的實例中，改進的NSGA-Ⅲ算法的收斂速度稍差于NSGA-Ⅱ算法，二者相差比例均在10%以內(nèi)。其原因是兩種算法都是利用快速非支配排序法對種群進行排序，而隨著目標(biāo)空間的擴大，基于參考點的小生境選擇機制的計算復(fù)雜度略大于NSGA-Ⅱ算法的擁擠距離計算。總體而言，兩種算法在收斂速度方面表現(xiàn)基本相當(dāng)。

綜上所述，改進的NSGA-Ⅲ算法具有與NSGA-Ⅱ算法基本相同的收斂速度，得到的非支配解的質(zhì)量明顯優(yōu)于NSGA-Ⅱ算法。因此，改進的NSGA-Ⅲ算法能夠有效求解高維多目標(biāo)低碳FJSP問題，獲得一組均勻分布的低碳調(diào)度解。

4 結(jié)論

筆者采用改進的NSGA-Ⅲ調(diào)度算法求解綜合考慮最大完工時間、瓶頸機器負(fù)荷、總機器負(fù)荷和能量消耗指標(biāo)的高維多目標(biāo)FJSP低碳調(diào)度模型。在分析機器能量消耗指標(biāo)的基礎(chǔ)上建立機器能量消耗矩陣，提出了綜合考慮經(jīng)濟指標(biāo)和能量消耗指標(biāo)的高維多目標(biāo)FJSP低碳調(diào)度模型。為解決傳統(tǒng)多目標(biāo)優(yōu)化方法在高維多目標(biāo)FJSP問題中選擇壓力不足的問題，設(shè)計了改進的NSGA-Ⅲ調(diào)度算法。實驗結(jié)果表明基于參考點的小生境選擇機制能夠在高維目標(biāo)空間中高效搜索，在增強算法選擇壓力的同時提升種群多樣性，獲得一組較優(yōu)的低碳調(diào)度解。但算法的收斂速度還有待提高，未來將考慮通過改進支配關(guān)系進一步提高算法的搜索效率和收斂速度。另外，筆者考慮的是靜態(tài)環(huán)境下的低碳FJSP，忽略了實際生產(chǎn)過程中的動態(tài)因素。在實際生產(chǎn)過程中，往往存在機器故障、工件延遲、緊急訂單插入等不確定因素。因此，進一步研究動態(tài)環(huán)境下的低碳調(diào)度也是一個重要的研究方向。