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

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

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

1 問題描述

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

式中：下標max、avg 和min 分別表示Pareto 解集中對應參數的最大值、平均值和最小值。

2 改進NSGA-Ⅲ算法

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

2.1 編碼與解碼

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

圖1 解碼圖

2.2 種群初始化及自適應交叉變異

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

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

2.3 基于目標空間參考點選擇策略

1）凈化目標空間 父代個體經過基因重組后，得到新的種群S，對其進行最值歸一化操作：定義S的理想點為Fi（x）的最小值zimin，進行目標函數的轉化：

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

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

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

3 仿真分析

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

表1 算法獨立運行200次Pareto解集數和運行時間對比表

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

圖2 不同算法下非劣解和目標歸一化結果對比圖

圖3 基于mk01的R-NSGA-III最佳調度方案圖

4 結論

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