基于自適應的NSGA-Ⅱ多目標柔性作業車間調度

王冠，高尚，房思佳

(1.河北科技大學經濟管理學院，河北石家莊 050018；2.上海集成電路裝備材料產業創新中心有限公司，上海201800)

0 前言

柔性作業車間調度是典型的NP-hard問題需要兼顧生產設備分配和工序排列方案，與傳統車間調度相比更加貼近真實情況。在實際應用中，僅圍繞單一目標進行評價愈發難以滿足實際需求，因此將研究重點聚焦在多目標柔性車間調度上。有許多算法可用于求解此類問題，例如遺傳算法、粒子群算法、蟻群算法、免疫算法等。遺傳算法因具備收斂性好、魯棒性高且有較好的擴展性等優點得到了更多的青睞。其中，吳秀麗等提出了一種混合遺傳算法；鞠全勇和朱劍英將粒子群和遺傳算法的優點相結合，提出了多種群混合遺傳算法。非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm,NSGA)是由SRINIVAS和DEB提出，通過尋找Pareto最優解解決多目標優化問題的方法，雖然該方法可以推廣到更高維、更復雜的問題，但是NSGA存在計算復雜度較高、沒有精英策略的問題。其后，DEB等對NSGA進行改進，提出基于非支配排序的多目標遺傳算法(NSGA-Ⅱ),以便在問題中找到更好的擴散解，實現了對這類問題更好的求解能力。

標準的NSGA-Ⅱ算法存在“易早熟”和易陷入局部最優的缺陷，所以研究柔性作業車間調度時需要對算法進行合理的改進。算法的改進主要針對交叉方法、自適應方法和尋找最優解等方面。在交叉方法的改進方面，張超勇等、宋昌興等分別提出了基于工序編碼的POX交叉算子方法和基于機器編碼的MPX交叉方法，提高了精英庫中的個體質量。在自適應方法改進方面，荊巍巍等在迭代過程的不同階段動態調整交叉與變異的概率提高算法計算效率。YUAN等運用層次分析法確定多目標最優解的方式，改進了尋找最優解的方法。

綜上所述，以最大完工時間、加工能耗、設備總負荷和最大延期時間4個方面為目標函數并建立數學模型，同時采用IPOX和改進的MPX方法分別實現工序層和設備層的交叉方案，應用了更高效率的具有自適應性的交叉和變異概率算法。在尋找最優解的過程中，先對Pareto解集中的各目標函數值進行量綱一化處理并運用層次分析法確定各目標權重，最終通過線性加權獲得柔性作業車間調度方案的滿意解。

1 多目標柔性車間調度模型

作為企業生產管理過程中的重要參考指標，文中根據完工時間、加工能耗、設備總負荷和延期時間4個方面建立目標函數并在滿足多目標柔性作業車間工藝約束前提下，綜合考慮多方面因素建立約束條件。

1.1 問題描述

在柔性車間生產單元最大荷載能力的限制下，待加工工件個數用表示，設備臺數用表示，={,,…,}表示工件集合，={,,…,,…,}表示設備集合。工件(=1,2,…,)共包含(=1,2,…,)道工序，各工件的工藝流程已知，設備集中所包含的設備可滿足所有工序的加工要求。表示第個工件的第道工序。因為每臺設備的性能參數及型號不同，所以工序的加工時間、負荷和能耗會因為設備選擇方案的不同而有所差異，最佳的設備選擇與加工順序方案直接構成最優的調度方案。

1.2 目標函數

表示從首個工件開始加工到最后工件加工結束所用時間，即最大完工時間。表示工件的完工時間，目標函數表示為

=min (max {|=1,2,…,})

(1)

表示所有工件在各道工序加工時所使用設備的能耗總和。表示設備加工第個工件第道工序的加工能耗，表示選擇加工設備進行工序的加工，表示加工設備的待機消耗，目標函數表示為

(2)

表示所有工件在各道工序加工時所使用設備的總負載。表示加工設備的最大載荷量，即在單位時間內加工設備完成的最大加工數量，目標函數表示為

(3)

表示各工件延期交貨時間總和。表示工件的交貨期，目標函數表示為

=min(max|-|)

(4)

1.3 約束條件

文中做出如下假設：

(1)同工件存在工序約束，不同工件間不存在約束。

(2)每個工件的加工時間及加工情況已知，加工時間中已包括加工準備等其余必要時間。

(3)所有設備在=0時均為空閑狀態。

表示工件第道工序在所選設備上開始加工的時間，表示工件第道工序在所選設備上完成加工的時間，工序間的約束表示為

≤(+1)

(5)

表示設備開始進行工序的加工時間，表示設備已完成工序的時間，表示工序在設備上的加工時間，工件加工一旦開始，中間不可中斷，設備約束表示為

-=

(6)

工序在設備上的決策變量表示為

(7)

最大完工時間、加工能耗和加工設備總負載的函數值大于零且最小值最優，適應度函數表示為

(8)

最大延期時間的函數值大于等于零且最小值最優，適應度函數表示為

(9)

2 改進的NSGA-Ⅱ多目標柔性車間算法設計

解決多目標優化問題對算法性能有一定的要求，NSGA-Ⅱ因為具備計算效率高、收斂性好、魯棒性強等優點成為較好的選擇，但是其算法效率可以進一步提升。文中對自適應和交叉變異方案進行了改進，改進后的算法在運算過程中采用混合交叉和變異方案，并且在不同階段動態調整交叉和變異概率。算法流程如圖1所示。

圖1 改進的NSGA-Ⅱ多目標柔性車間算法流程

2.1 染色體編碼與解碼的設計

文中采用工序、設備雙層編碼的方式分別用于解決工序排列及設備分配問題。為了方便理解算法過程，以一個五臺設備加工4種工件的柔性作業車間調度問題為例進行分析，工件1和工件3有3道工序，工件2和工件4有2道工序，各工件每道工序對應的可選設備集為5臺設備中部分設備。基于工序、設備的雙層編碼過程如圖2所示，工件號是工序編碼方格內的數字，可選設備集表示第個工件在第道工序加工時可選用的設備集合，設備編碼方格內的數字代表第個工件在第道工序加工時選用的設備序號。解碼方式采用插入式貪婪解碼，將個體編碼轉變成調度甘特圖。

圖2 基于工序、設備的雙編碼過程

2.2 選擇操作

多目標優化問題中的各目標之間往往會相互沖突。為盡量避免此情況，文中采用快速非支配排序方法，從而有效地降低計算過程的復雜程度并尋出滿意解。首先，對種群進行非支配排序，令種群劃分為不同層級，接下來對同一層級內的個體進行擁擠度計算，最終應用二元錦標賽機制從種群中選出優先度較高的個體。優先度較高的個體選擇原則為首先進行層級的比較，個體的層級越低越會被優先選擇，其次比較擁擠度距離，個體的擁擠度距離越大越會被優先選擇。其中，擁擠度距離計算方法如下：

(10)

2.3 交叉與變異

2.3.1 混合交叉方案

基于IPOX交叉算子對工序進行交叉的流程如圖3所示。首先從工件集中隨機選取若干工件，如選取{,}，將PF1中的和工件按照相同的位置復制到PC1，將PF2中和工件按照相同的位置復制到PC2，將PF1中的和工件按照相同的順序復制到PC2，將PF2中的和工件按照相同的順序復制到PC1。因編碼方式為工序與設備雙層編碼，所以在進行工序交叉時，當前父代所對應的設備也要進行與工序交叉相同的操作，操作流程如圖4所示。

圖3 IPOX工序交叉示意

圖4 IPOX設備交叉示意

設備編碼部分采用改進的MPX交叉，改進的MPX交叉流程如圖5所示。首先從工件集中隨機選取若干個工件，如選取{,}并記錄它出現的位置，然后分別將父代設備編碼MF1與MF2中非記錄位置基因放入子代設備編碼MC1和MC2，最后交換MF1和MF2中記錄位置的相同工序設備基因，并依次插入子代對應位置。

圖5 改進的MPX交叉示意

2.3.2 混合變異方案

工序變異部分流程如圖6所示。首先任意交換2道工序的排序，交換后按照每個工件的工藝順序進行檢驗，發現因交換工序所產生的非法基因則對它進行修復。

圖6 工序變異示意

設備變異過程的示意如圖7所示。首先任意選出一道工序，然后讀取所選工序的可用設備集，并從設備集中任意選擇一臺設備替換當前設備，最后重新計算與其相對應的目標函數值。

圖7 設備變異示意

2.3.3 自適應交叉、變異概率

交叉和變異概率對種群多樣性和算法收斂有著重要作用。因為對參數設定不合理則會出現算法早熟、計算效率降低等問題，為防止上述情況發生，文中采用自適應交叉和變異概率，依據算法的迭代次數動態地更新交叉和變異概率，交叉概率和變異概率的計算方法如下:

(11)

首先由各個目標函數的適應度分量計算出交叉概率c和變異概率m，再取c和m的平均值得出交叉概率與變異概率，式中為目標函數的數量。max、avg和min分別表示種群中第個目標函數適應度的最大值、平均值和最小值;′為2個即將交叉個體中適應度較大值;為待變異個體的適應度值;1>>>>0，1>>>>0。

3 實例仿真

某石油企業的機加車間在調度周期內安排8臺設備加工8種類型工件。柔性車間調度問題實例數據見表1，表中展示了不同類型工件的不同工序對應的可選設備集及加工時間。

表1 8×8柔性車間調度實例數據

文中以表1中數據為例進行MATLAB軟件仿真分析，算法中各參數設定見表2。

表2 算法參數設定

計算過程中，各目標變化趨勢如圖8所示，圖中所示為4個目標函數的平均值與標準差。依據圖中的變化趨勢可知各目標在經過60次迭代后趨于穩定。

圖8 迭代過程中目標函數變化趨勢

在達到算法設置最大迭代次數后，對最終的Pareto解集采用線性加權法確定最滿意解。需對目標函數值量綱一化進行比較，量綱一化方法如下:

(12)

式中：=1，2，…，；=1，2，…，；和分別為Pareto解集中解和目標函數的數量;max和min分別為Pareto解集中第個目標函數的最大值與最小值，為量綱一化前的函數值，為量綱一化后的函數值。

通過線性加權的方法對Pareto解集中的所有解進行綜合評價，若某解為解集中評價值最大的解，則選取它為滿意解，計算方法如下:

(13)

式中：表示賦予不同目標函數的權重大??；文中根據車間具體需求運用層次分析法得出最大完工時間權重為=0.35，最大延期時間權重=0.32，能耗權重=0.16，設備總負載權重=0.17。最終得到的最優調度甘特圖如圖9所示，最大完工時間為70 min，延期時間為0 min，設備負載時間為348 min，能耗為110.73 kW·h。

圖9 最優調度甘特圖

原始調度甘特圖如圖10所示，其最大完工時間為90 min，延期時間為10 min，機器負載時間為358 min，能耗為131.48 kW·h。對比圖9、圖10所示的方案可以發現:優化后調度方案的最大完工時間、加工設備負載時間和加工能耗相較于初始值分別減少了22.22%、2.79%和15.78%，延期時間減少了10 min。

圖10 原始調度甘特圖

4 結論

文中考慮到算法運算的不同迭代次數對交叉和變異概率的要求不同，提出了交叉和變異概率在算法不同階段動態改變的自適應NSGA-Ⅱ算法，然后采用能夠顯著提升NSGA-Ⅱ算法計算效率與精度的IPOX和改進的MPX對工序層和設備層進行交叉操作，在提高種群多樣性、避免非法解產生的同時有效提升計算效率及搜索能力，為獲取最優的多目標柔性車間的調度方案提供保證。最終應用實例仿真驗證的方法評價算法的有效性與可行性,與初始調度方案中的最大完工時間、設備負載時間和能耗相比分別減少22.22%、2.79%和15.78%，延期時間減少了10 min。