基于NSGA-Ⅲ的多目標(biāo)柔性車間調(diào)度

李鵬，徐龍艷，雷俊松，呂勇，畢亞球

（1.湖北汽車工業(yè)學(xué)院 電氣與信息工程學(xué)院，湖北 十堰 442002；2.十堰市計(jì)量檢定測(cè)試所，湖北 十堰 442000；3.湖北漢唐智能科技股份有限公司，湖北 十堰 442000）

在實(shí)現(xiàn)“雙碳”目標(biāo)的要求下，國(guó)家對(duì)制造業(yè)節(jié)能減排提出了新的要求［1-3］。盡管企業(yè)對(duì)制造技術(shù)進(jìn)行更新升級(jí)，但仍存在資源浪費(fèi)［4-5］。數(shù)據(jù)表明，制造過程中非切削工序消耗了95%的時(shí)間，有效的柔性作業(yè)車間調(diào)度方法對(duì)提高企業(yè)生產(chǎn)力具有重要作用［6］。針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題，尹愛軍等［7］研究了遺傳退火算法，針對(duì)最大化生產(chǎn)時(shí)間、最小化生產(chǎn)成本和最大化客戶滿意度采用融合海明相似度的改進(jìn)算法優(yōu)化多個(gè)目標(biāo)；張麗等［8］針對(duì)最大化完工時(shí)間和能耗提出融合密度估計(jì)方法的改進(jìn)NSGA-Ⅱ算法；裴小兵等［9］以最小化完工時(shí)間、總機(jī)器負(fù)荷最小和臨界機(jī)器負(fù)荷最小為目標(biāo)，提出了基于三方博弈的改進(jìn)遺傳算法求解多目標(biāo)柔性作業(yè)車間調(diào)度模型；Tao 等［10］針對(duì)低碳排放約束的柔性作業(yè)車間調(diào)度問題，提出了基于雙鏈編碼的改進(jìn)量子遺傳算法，并且在選定模型的基礎(chǔ)上，提出了使用改進(jìn)的雙鏈量子遺傳算法求解加工路徑選擇的方法；林震等［11］構(gòu)建了以加工成本、瓶頸機(jī)器負(fù)荷、機(jī)器總負(fù)荷及制造工期為目標(biāo)函數(shù)的柔性作業(yè)車間調(diào)度多目標(biāo)優(yōu)化模型，提出了融合多交叉策略的多目標(biāo)遺傳算法，通過2個(gè)基準(zhǔn)實(shí)例求解對(duì)比分析表明所提方法的有效性；解瀟晗等［12］分析了工藝車間調(diào)度中能量消耗的重要環(huán)節(jié)和特點(diǎn)，以能耗和生產(chǎn)時(shí)間為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，采用多層編碼，對(duì)能耗和生產(chǎn)時(shí)間進(jìn)行加權(quán)求和處理，采用多目標(biāo)優(yōu)化算法實(shí)現(xiàn)調(diào)度策略。但上述研究在求解多個(gè)優(yōu)化目標(biāo)時(shí)多個(gè)影響因子相互制約，對(duì)于高維多目標(biāo)優(yōu)化問題，NSGA-Ⅱ會(huì)面臨如基于Pareto支配關(guān)系所導(dǎo)致的選擇壓力過小、擁擠距離在高維空間不適用造成計(jì)算復(fù)雜度過高等問題。文中以最小加工時(shí)間、成本、質(zhì)量和能耗為優(yōu)化目標(biāo)構(gòu)建數(shù)學(xué)模型，運(yùn)用改進(jìn)NSGA-Ⅲ算法對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題進(jìn)行求解。

1 問題描述

柔性作業(yè)車間調(diào)度是指n（i1，i2，…，in）個(gè)工件在m（j=1，2，…，M）個(gè)機(jī)器上加工，工件的每一道工序均可在任意滿足加工要求的機(jī)器上完成。生產(chǎn)調(diào)度是指在滿足每個(gè)工件生產(chǎn)工序的基礎(chǔ)上，為工序安排合適的加工機(jī)器，同時(shí)實(shí)現(xiàn)給定的優(yōu)化目標(biāo)。結(jié)合實(shí)際生產(chǎn)情況，根據(jù)FJSP模型要求，進(jìn)行以下假設(shè)：1）柔性作業(yè)車間調(diào)度過程不能被中斷或搶斷；2）加工同一個(gè)工件時(shí)需按照工件工序依次加工；3）在同一時(shí)刻，1道工序最多只能被1臺(tái)機(jī)器加工；4）所有機(jī)器和操作在零點(diǎn)時(shí)同時(shí)可用；5）同一時(shí)刻1臺(tái)機(jī)器最多只能加工1道工序；6）所有的參數(shù)均為正數(shù)：7）工件之間的轉(zhuǎn)運(yùn)時(shí)間、成本和能耗不予考慮。優(yōu)化目標(biāo)函數(shù)為

式中：下標(biāo)max、avg 和min 分別表示Pareto 解集中對(duì)應(yīng)參數(shù)的最大值、平均值和最小值。

2 改進(jìn)NSGA-Ⅲ算法

與NSGA-Ⅱ相比，NSGA-Ⅲ通過廣泛引入?yún)⒖键c(diǎn)，在解決多目標(biāo)優(yōu)化問題時(shí)其收斂性得到明顯的改善［15］，但是無(wú)法保證超平面上的參考點(diǎn)均勻分布，間接導(dǎo)致算法早熟，使其搜索能力下降，因此需要對(duì)算法進(jìn)行改進(jìn)。

2.1 編碼與解碼

如圖1所示，文中采取小數(shù)編碼。假設(shè)機(jī)器數(shù)為18，工件數(shù)為6，工序數(shù)為18，編碼分上下2 段，分別為工序號(hào)和機(jī)器號(hào)。由于兩段編碼的范圍不同，因此采取0～1之間的隨機(jī)數(shù)表示加工順序和加工機(jī)器。工序編碼時(shí)，首先將所有加工順序以向量的形式表示，數(shù)字為工件號(hào)，出現(xiàn)的次數(shù)為工序。將編碼得到的小數(shù)由小到大進(jìn)行排序，與排序前的編碼進(jìn)行對(duì)比，將編碼與工序一一對(duì)應(yīng)，根據(jù)數(shù)字的變化情況產(chǎn)生不同的工序方案。機(jī)器解碼時(shí)，為了使工序與機(jī)器對(duì)應(yīng)，保證加工機(jī)器可用，在解碼時(shí)候轉(zhuǎn)換為對(duì)應(yīng)的整數(shù)，進(jìn)而實(shí)現(xiàn)實(shí)際機(jī)器的安排。圖1中，第1個(gè)機(jī)器編碼為0.8620，其對(duì)應(yīng)的工件2工序1，通過機(jī)器矩陣查詢，可以加工工序1的機(jī)器有1號(hào)、3號(hào)、4號(hào)和6號(hào)4個(gè)機(jī)器，對(duì)編碼與機(jī)器數(shù)的乘積執(zhí)行向上取整規(guī)則得到4，因此確定加工該工序的機(jī)器為6號(hào)機(jī)器。

圖1 解碼圖

2.2 種群初始化及自適應(yīng)交叉變異

采用隨機(jī)搜索策略和貪婪有序策略生成初始種群，2 種策略初始種群個(gè)體數(shù)量比為7∶3。種群交叉和變異的過程中，交叉和變異概率的大小影響算法的性能［16］。在基本NSGA-Ⅲ算法中，交叉概率pc0和變異概率pm0為固定值，為使算法避免過度發(fā)散和陷入局部最優(yōu)提出自適應(yīng)交叉變異概率：

式中：pcmin和pmmin分別為最小交叉和變異概率；a、b、c、d均為控制參數(shù)；i為進(jìn)化次數(shù)。

2.3 基于目標(biāo)空間參考點(diǎn)選擇策略

1）凈化目標(biāo)空間 父代個(gè)體經(jīng)過基因重組后，得到新的種群S，對(duì)其進(jìn)行最值歸一化操作：定義S的理想點(diǎn)為Fi（x）的最小值z(mì)imin，進(jìn)行目標(biāo)函數(shù)的轉(zhuǎn)化：

2）確定參考點(diǎn) NSGA-Ⅲ預(yù)定義了參考點(diǎn)以保證最優(yōu)解的多樣性，參考點(diǎn)定義在維度為M的超平面上，將超平面分為p等份后得到參考點(diǎn)：

3）關(guān)聯(lián)個(gè)體和參考點(diǎn) 隨著迭代的進(jìn)行，參考點(diǎn)分布在解空間中，以原點(diǎn)和參考點(diǎn)為基準(zhǔn)確定參考向量，計(jì)算個(gè)體與參考向量的截距，截距最小的個(gè)體互相構(gòu)成關(guān)聯(lián)參考點(diǎn)。若產(chǎn)生關(guān)聯(lián)參考點(diǎn)，則說(shuō)明所得解在解空間中分布廣泛，也說(shuō)明了這些解達(dá)到了全局最優(yōu)的效果。

4）交叉操作 假設(shè)共有F層個(gè)體，將產(chǎn)生的新個(gè)體分配至第St層，從F1到FL層中的個(gè)體數(shù)目首次大于N或者（St+1）層的個(gè)體大于目標(biāo)數(shù)，則需要對(duì)（St+1）層的個(gè)體進(jìn)行篩選。篩選時(shí)，遍歷每個(gè)參考點(diǎn)，將數(shù)量最少的參考點(diǎn)Pj進(jìn)行歸屬，若無(wú)歸屬參考點(diǎn)，則Pj值為0。若最后一層非支配層FL有歸屬的參考點(diǎn)個(gè)體，則從中選取距離最小的點(diǎn)加入到下一代種群中，采取歐氏距離判斷參考點(diǎn)的關(guān)聯(lián)度，此時(shí)Pj的值增1 個(gè)單位；若最后一層無(wú)歸屬參考點(diǎn)，則淘汰該參考點(diǎn)。

3 仿真分析

改進(jìn)NSGA-Ⅲ（簡(jiǎn)稱R-NSGA-Ⅲ）采用MATLAB R2019b 編程，種群規(guī)模設(shè)置為30，交叉和變異中的參數(shù)a、b、c和d分別取值0.1、0.1、0.9和0.7。mk01～mk05 為不同工件和工序的標(biāo)準(zhǔn)數(shù)據(jù)集，將R-NSGA-Ⅲ與NSGA-Ⅲ、PSO 和SAA 在5 種不同測(cè)試數(shù)據(jù)測(cè)試后得到平均加工時(shí)間、成本、質(zhì)量和能耗，結(jié)果見表1。對(duì)比發(fā)現(xiàn)，R-NSGA-Ⅲ在加工時(shí)間、成本和能耗方面略低于其他3 種算法，在加工質(zhì)量方面，R-NSGA-Ⅲ高于NSGA-Ⅲ和SAA。

表1 算法獨(dú)立運(yùn)行200次Pareto解集數(shù)和運(yùn)行時(shí)間對(duì)比表

以mk01為實(shí)例仿真，算法獨(dú)立運(yùn)行200次，圖2 為得到非支配解和對(duì)目標(biāo)函數(shù)采用最值歸一化操作后的對(duì)比圖，線條數(shù)量代表所得非支配解的數(shù)量，轉(zhuǎn)折點(diǎn)為算法對(duì)應(yīng)不同優(yōu)化目標(biāo)的計(jì)算值。通過對(duì)比可看出R-NSGA-Ⅲ獲得Pareto 解的數(shù)量?jī)?yōu)于其他算法，且R-NSGA-Ⅲ在加工時(shí)間、成本、質(zhì)量和能耗方面優(yōu)于其他算法，說(shuō)明R-NSGA-Ⅲ算法得到的Pareto解集具有良好的收斂性和多樣性。對(duì)結(jié)果進(jìn)行排序可以得到最優(yōu)調(diào)度方案的甘特圖。以mk01數(shù)據(jù)集為例，在運(yùn)行R-NSGA-Ⅲ算法后得到最佳調(diào)度方案，如圖3 所示，其中不同的顏色和數(shù)字分別代表不同的工件和工序。101 表示工件1的第1道工序在設(shè)備6上加工，以此類推，從圖中可以看出最大加工時(shí)間為58 s。從以上實(shí)驗(yàn)結(jié)果中可以看出R-NSGA-Ⅲ算法的求解質(zhì)量和成功率都高于其他算法。

圖2 不同算法下非劣解和目標(biāo)歸一化結(jié)果對(duì)比圖

圖3 基于mk01的R-NSGA-III最佳調(diào)度方案圖

4 結(jié)論

針對(duì)多個(gè)優(yōu)化目標(biāo)，提出了改進(jìn)NSGA-Ⅲ算法。算法設(shè)計(jì)了一種基于小數(shù)的雙層編碼方式，且引入自適應(yīng)交叉變異策略，避免種群在交叉變異過程中產(chǎn)生無(wú)效解。針對(duì)NSGA-Ⅲ算法超平面上的參考點(diǎn)分布不均勻的問題，提出基于目標(biāo)空間參考點(diǎn)選擇策略。通過仿真實(shí)驗(yàn)分析，驗(yàn)證了算法的可行性和有效性。