基于自適應(yīng)的NSGA-Ⅱ多目標(biāo)柔性作業(yè)車間調(diào)度

王冠，高尚，房思佳

(1.河北科技大學(xué)經(jīng)濟(jì)管理學(xué)院，河北石家莊 050018；2.上海集成電路裝備材料產(chǎn)業(yè)創(chuàng)新中心有限公司，上海201800)

0 前言

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

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

綜上所述，以最大完工時間、加工能耗、設(shè)備總負(fù)荷和最大延期時間4個方面為目標(biāo)函數(shù)并建立數(shù)學(xué)模型，同時采用IPOX和改進(jìn)的MPX方法分別實(shí)現(xiàn)工序?qū)雍驮O(shè)備層的交叉方案，應(yīng)用了更高效率的具有自適應(yīng)性的交叉和變異概率算法。在尋找最優(yōu)解的過程中，先對Pareto解集中的各目標(biāo)函數(shù)值進(jìn)行量綱一化處理并運(yùn)用層次分析法確定各目標(biāo)權(quán)重，最終通過線性加權(quán)獲得柔性作業(yè)車間調(diào)度方案的滿意解。

1 多目標(biāo)柔性車間調(diào)度模型

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

1.1 問題描述

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

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

表示從首個工件開始加工到最后工件加工結(jié)束所用時間，即最大完工時間。表示工件的完工時間，目標(biāo)函數(shù)表示為

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

(1)

表示所有工件在各道工序加工時所使用設(shè)備的能耗總和。表示設(shè)備加工第個工件第道工序的加工能耗，表示選擇加工設(shè)備進(jìn)行工序的加工，表示加工設(shè)備的待機(jī)消耗，目標(biāo)函數(shù)表示為

(2)

表示所有工件在各道工序加工時所使用設(shè)備的總負(fù)載。表示加工設(shè)備的最大載荷量，即在單位時間內(nèi)加工設(shè)備完成的最大加工數(shù)量，目標(biāo)函數(shù)表示為

(3)

表示各工件延期交貨時間總和。表示工件的交貨期，目標(biāo)函數(shù)表示為

=min(max|-|)

(4)

1.3 約束條件

文中做出如下假設(shè)：

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

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

(3)所有設(shè)備在=0時均為空閑狀態(tài)。

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

≤(+1)

(5)

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

-=

(6)

工序在設(shè)備上的決策變量表示為

(7)

最大完工時間、加工能耗和加工設(shè)備總負(fù)載的函數(shù)值大于零且最小值最優(yōu)，適應(yīng)度函數(shù)表示為

(8)

最大延期時間的函數(shù)值大于等于零且最小值最優(yōu)，適應(yīng)度函數(shù)表示為

(9)

2 改進(jìn)的NSGA-Ⅱ多目標(biāo)柔性車間算法設(shè)計(jì)

解決多目標(biāo)優(yōu)化問題對算法性能有一定的要求，NSGA-Ⅱ因?yàn)榫邆溆?jì)算效率高、收斂性好、魯棒性強(qiáng)等優(yōu)點(diǎn)成為較好的選擇，但是其算法效率可以進(jìn)一步提升。文中對自適應(yīng)和交叉變異方案進(jìn)行了改進(jìn)，改進(jìn)后的算法在運(yùn)算過程中采用混合交叉和變異方案，并且在不同階段動態(tài)調(diào)整交叉和變異概率。算法流程如圖1所示。

圖1 改進(jìn)的NSGA-Ⅱ多目標(biāo)柔性車間算法流程

2.1 染色體編碼與解碼的設(shè)計(jì)

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

圖2 基于工序、設(shè)備的雙編碼過程

2.2 選擇操作

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

(10)

2.3 交叉與變異

2.3.1 混合交叉方案

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

圖3 IPOX工序交叉示意

圖4 IPOX設(shè)備交叉示意

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

圖5 改進(jìn)的MPX交叉示意

2.3.2 混合變異方案

工序變異部分流程如圖6所示。首先任意交換2道工序的排序，交換后按照每個工件的工藝順序進(jìn)行檢驗(yàn)，發(fā)現(xiàn)因交換工序所產(chǎn)生的非法基因則對它進(jìn)行修復(fù)。

圖6 工序變異示意

設(shè)備變異過程的示意如圖7所示。首先任意選出一道工序，然后讀取所選工序的可用設(shè)備集，并從設(shè)備集中任意選擇一臺設(shè)備替換當(dāng)前設(shè)備，最后重新計(jì)算與其相對應(yīng)的目標(biāo)函數(shù)值。

圖7 設(shè)備變異示意

2.3.3 自適應(yīng)交叉、變異概率

交叉和變異概率對種群多樣性和算法收斂有著重要作用。因?yàn)閷?shù)設(shè)定不合理則會出現(xiàn)算法早熟、計(jì)算效率降低等問題，為防止上述情況發(fā)生，文中采用自適應(yīng)交叉和變異概率，依據(jù)算法的迭代次數(shù)動態(tài)地更新交叉和變異概率，交叉概率和變異概率的計(jì)算方法如下:

(11)

首先由各個目標(biāo)函數(shù)的適應(yīng)度分量計(jì)算出交叉概率c和變異概率m，再取c和m的平均值得出交叉概率與變異概率，式中為目標(biāo)函數(shù)的數(shù)量。max、avg和min分別表示種群中第個目標(biāo)函數(shù)適應(yīng)度的最大值、平均值和最小值;′為2個即將交叉?zhèn)€體中適應(yīng)度較大值;為待變異個體的適應(yīng)度值;1>>>>0，1>>>>0。

3 實(shí)例仿真

某石油企業(yè)的機(jī)加車間在調(diào)度周期內(nèi)安排8臺設(shè)備加工8種類型工件。柔性車間調(diào)度問題實(shí)例數(shù)據(jù)見表1，表中展示了不同類型工件的不同工序?qū)?yīng)的可選設(shè)備集及加工時間。

表1 8×8柔性車間調(diào)度實(shí)例數(shù)據(jù)

文中以表1中數(shù)據(jù)為例進(jìn)行MATLAB軟件仿真分析，算法中各參數(shù)設(shè)定見表2。

表2 算法參數(shù)設(shè)定

計(jì)算過程中，各目標(biāo)變化趨勢如圖8所示，圖中所示為4個目標(biāo)函數(shù)的平均值與標(biāo)準(zhǔn)差。依據(jù)圖中的變化趨勢可知各目標(biāo)在經(jīng)過60次迭代后趨于穩(wěn)定。

圖8 迭代過程中目標(biāo)函數(shù)變化趨勢

在達(dá)到算法設(shè)置最大迭代次數(shù)后，對最終的Pareto解集采用線性加權(quán)法確定最滿意解。需對目標(biāo)函數(shù)值量綱一化進(jìn)行比較，量綱一化方法如下:

(12)

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

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

(13)

式中：表示賦予不同目標(biāo)函數(shù)的權(quán)重大?。晃闹懈鶕?jù)車間具體需求運(yùn)用層次分析法得出最大完工時間權(quán)重為=0.35，最大延期時間權(quán)重=0.32，能耗權(quán)重=0.16，設(shè)備總負(fù)載權(quán)重=0.17。最終得到的最優(yōu)調(diào)度甘特圖如圖9所示，最大完工時間為70 min，延期時間為0 min，設(shè)備負(fù)載時間為348 min，能耗為110.73 kW·h。

圖9 最優(yōu)調(diào)度甘特圖

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

圖10 原始調(diào)度甘特圖

4 結(jié)論

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