王冠，高尚，房思佳

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

0 前言

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

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

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

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

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

1.1 問題描述

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

1.2 目標函數(shù)

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

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

(1)

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

(2)

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

(3)

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

=min(max|-|)

(4)

1.3 約束條件

文中做出如下假設：

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

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

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

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

≤(+1)

(5)

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

-=

(6)

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

(7)

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

(8)

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

(9)

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

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

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

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

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

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

2.2 選擇操作

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

(10)

2.3 交叉與變異

2.3.1 混合交叉方案

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

圖3 IPOX工序交叉示意

圖4 IPOX設備交叉示意

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

圖5 改進的MPX交叉示意

2.3.2 混合變異方案

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

圖6 工序變異示意

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

圖7 設備變異示意

2.3.3 自適應交叉、變異概率

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

(11)

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

3 實例仿真

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

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

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

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

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

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

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

(12)

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

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

(13)

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

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

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

圖10 原始調度甘特圖

4 結論

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