超啟發(fā)式遺傳算法柔性作業(yè)車間綠色調度問題研究*

屈新懷,紀 飛,孟冠軍,丁必榮,王 嬌

(合肥工業(yè)大學 機械工程學院,安徽 合肥 230009)

0 引 言

我國正處在由制造大國邁向制造強國的重要歷史階段,但是我國制造業(yè)整體資源消耗高,環(huán)境污染嚴重,產品卻處于價值鏈的中低端。因此,轉變制造業(yè)高消耗、高排放、低效率的粗放增長方式,促進制造業(yè)與生態(tài)環(huán)境協(xié)調發(fā)展,實現綠色制造是我國建設制造強國的必由之路[1]。

調度作為制造系統(tǒng)的重要環(huán)節(jié),受到越來越多的重視,高效合理的綠色車間調度能夠有效地實現節(jié)能減排、減少環(huán)境污染,較傳統(tǒng)調度更符合當前的發(fā)展理念,更具應用價值。柔性作業(yè)車間調度問題(flexible job shop scheduling problem, FJSP)是作業(yè)車間調度問題(job shop scheduling problem, JSP)的擴展,釋放了工序的資源約束,使問題更加貼近實際應用[2]。

近年來,越來越多的學者對綠色柔性作業(yè)車間調度問題進行了研究。劉瓊等人[3]提出了產品制造過程碳足跡計算方法,建立了以碳足跡、完工時間、設備利用率為優(yōu)化目標的多目標優(yōu)化調度模型,設計了第二代非支配解遺傳算法進行求解。雷德明等人[4]提出了一種基于新型優(yōu)化機理的教學優(yōu)化算法,以此來求解低碳柔性作業(yè)車間調度問題。李聰波等人[5]研究了考慮柔性作業(yè)車間廣義能耗調度優(yōu)化模型,基于模擬退火算法對模型進行了求解。李明等人[6]針對以完工時間、拖期、機器負荷和總能耗為目標的高維度多目標柔性作業(yè)車間調度問題,提出了一種新型帝國競爭算法對其進行了求解。MOKHTARI H等人[7]建立了以完工時間、設備利用率和總能耗為目標的多目標優(yōu)化模型,提出了用遺傳算法與模擬退火算法相結合的混合算法進行求解。LUO Shu等人[8]基于改進灰狼優(yōu)化算法,求解了多目標柔性作業(yè)車間低碳調度。

上述文獻都采用了啟發(fā)式算法對柔性作業(yè)車間調度問題進行求解。啟發(fā)式算法通常是根據特定的問題設置特定的搜索算子及參數,決定將哪種算子應用于特定的問題是一個持續(xù)的挑戰(zhàn)。

但是,提前預測特定算子在特定問題上的表現是非常困難的;此外,調度環(huán)境和目標的變化會影響算法的求解能力,不能保證算法的求解效果。所以,在此基礎上，通用性強的超啟發(fā)式算法受到了越來越多學者的關注。

超啟發(fā)式算法(HHA)是一種選擇或生成啟發(fā)式來解決計算搜索問題的搜索方法,致力于尋找一個好的方法來解決問題,是在一個啟發(fā)式的搜索空間上操作,而不是直接在特定問題解決方案的搜索空間上進行操作;其由高層啟發(fā)式策略(high level strategy,HLS)和低層啟發(fā)式算子(low level heuristic,LLH)兩部分構成,通過高層啟發(fā)式策略選擇或生成低層啟發(fā)式算子來實現對解空間的搜索。

BURKE E K等人[9]提出了基于蟻群優(yōu)化的遺傳規(guī)劃超啟發(fā)式算法,求解混合流水車間調度問題,通過離線遺傳規(guī)劃生成了啟發(fā)式調度規(guī)則,然后通過蟻群優(yōu)化進行了選擇。CHEN Lin等人[10]提出了一種基于粒子群算法的超啟發(fā)式算法,求解車間調度問題。SU N等人[11,12]提出了超啟發(fā)式交叉熵算法,求解模糊分布式流水綠色調度問題模型。

針對傳統(tǒng)啟發(fā)式算法通用性較差的問題,筆者建立多目標柔性作業(yè)車間綠色調度模型,設計超啟發(fā)式遺傳算法對問題進行求解;采用遺傳算法作為高層啟發(fā)式策略,并設計9種低層啟發(fā)式算子;采用隨機方法生成高層策略域種群,設計貪婪初始化方法生成低層問題域種群,最后通過標準算例及車間調度實例對算法性能進行驗證。

1 柔性作業(yè)車間綠色調度問題

1.1 問題描述

柔性作業(yè)車間綠色調度問題可描述為:將n個工件安排到m臺機器上進行加工,每個工件有多道工序且每道工序的加工順序是確定的,每道工序有多臺可選擇加工機器,在不同加機器上的加工時間不同。

在加工過程中,機器有加工和空載兩種狀態(tài),不同機器加工同一道工序產生的碳排放不同,機器空載狀態(tài)也會產生碳排放。

柔性作業(yè)綠色調度問題是以能耗為目標,解決工序排序和機器選擇兩個子問題。工件完工時間為調度方案開始實施到工件最后一道工序完成加工所經歷的時間,所有工件中完工時間最大的時間稱為最大完工時間,最大完工時間是衡量車間生產性能的重要指標。

綜上所述,筆者以最大完工時間和能耗為目標建立了柔性作業(yè)車間綠色調度模型。該問題滿足以下假設條件:

(1)在初始時刻,機器和工件都處于可用狀態(tài);(2)工序加工過程不允許中斷;(3)每臺機器同一時刻只可加工一個工件;(4)不同工件相互獨立,同工件的不同工序有加工順序約束;(5)不考慮機器的準備時間和工件的搬運時間。

1.2 模型建立

此處優(yōu)化目標是最大完工時間和能耗。筆者建立以最大完工時間和能耗為目標函數的數學模型如下:

f1=Cmax

(1)

(2)

i=1,2,…,n;j=1,2,…,Ni

(3)

Sij-Ci(j-1)≥0

i=1,2,…,n;j=2,3,…,Ni

(4)

i,i′=1,2,…,n;j,j′=1,2,…,Ni;

k=1,2,…,m

(5)

i=1,2,…,n;j=1,2,…,Ni

(6)

xijk∈{0，1}

(7)

yiji′j′∈{-1，0，1}

(8)

式中：Cmax—最大完工時間；n—工件總數；Ni—工件i的工序數；m—機器總數；Oij—工件i的第j道工序；tijk—工序Oij在機器k上的加工時間；cijk—機器k加工工序Oij時，單位時間平均能耗；Sij—工序Oij的開始時間；Cij—工序Oij的完工時間；xijk—0-1變量，若工序Oij在機器k上加工為1，否則為0；yiji′j′—決策變量，若工序Oij為工序Oi′j′相鄰的前一道工序則yiji′j′為-1，若工序Oi′j′為工序Oij相鄰的后一道工序則yiji′j′為1，否則yiji′j′為0。

其中：式(1，2)為目標值；式(3)表示工序加工過程中不允許中斷；式(4)表示同工件的不同工序加工順序約束；式(5)表示每臺機器同一時刻只可加工一個工件；式(6)表示每道工序只可被一臺機器加工；式(7，8)均為決策變量。

最大完工時間和能耗兩個評價指標的量綱和量綱單位不同，直接將目標值加權和作為目標函數，會影響求解的效果。為了消除其影響，筆者對目標值進行歸一化處理；最后，對處理后同一量級的值進行加權和。

筆者采用min-max標準化對每個種群的目標值進行歸一化，公式如下：

(9)

式中：min—種群中目標值f1的最小值；max—種群中目標值f1的最大值。

則目標函數如下：

(10)

其中：α1和α2分別為2個目標值權重系數，且滿足α1+α2=1。筆者參考文獻[13]142-143，取α1≈α2。

2 超啟發(fā)式遺傳算法設計

超啟發(fā)式遺傳算法是將遺傳算法與超啟發(fā)式算法相結合的一種算法。其高層啟發(fā)式策略采用遺傳算法,高層策略域個體的適應度值與對應問題域種群中最優(yōu)解適應值相同,根據適應度值對高層策略域進行選擇、交叉、變異操作。

筆者設計9種低層啟發(fā)式算子,根據高層策略域個體的編碼選擇相應的算子,對問題域種群進行操作。

算法流程具體描述如下:

步驟(1)。初始化高層策略域種群和低層問題域種群;

步驟(2)。評價問題域種群;

步驟(3)。根據高層策略域染色體的適應度值對低層問題域種群依次進行低層啟發(fā)操作,將更新后的解與原解進行比較,若更新后解的適應值優(yōu)于舊解的適應值,用新解替換舊解;否則,按照一定概率接受新解;

步驟(4)。評價高層策略域種群,并對策略域種群進行選擇、交叉和變異操作;

步驟(5)。對問題域種群進行選擇;

步驟(6)。判斷是否滿足終止條件,滿足則終止循環(huán),輸出最優(yōu)解,否則轉到步驟(2)。

2.1 高層策略設計

采用遺傳算法作為高層啟發(fā)式策略,在算法中,對低層啟發(fā)式算子進行組合,獲得高層策略域種群。在迭代過程中,新的個體通過對父代種群進行遺傳操作來生成,用染色體中每個基因即低層啟發(fā)式算子對問題進行求解。

每個基因在進行求解時,將更新后的解與原解進行比較,若更新后的解適應值優(yōu)于舊解的適應值,用新解替換舊解;否則,按照一定概率接受新解,高層策略染色體的適應度值為新解的適應值。

2.2 低層算法設計

低層算子是由領域專家提供的,需根據實際問題進行設計。依據參考文獻[14]概述的常用算子,筆者將低層啟發(fā)式算子分為2類:交叉算子、變異算子;采用分段編碼方式,染色體由工序排序染色體和機器選擇染色體兩部分構成,針對兩部分分別設計低層算子(具體說明如下,用數字對工序進行編號,用“X”表示空工序)。

2.2.1 交叉算子

將各種交叉算子進行整合得到交叉算子示意圖,如圖1所示。

圖1 交叉算子示意圖

LLH1。順序交叉(order crossover)，在工序染色體上隨機選擇2個切割點，產生片段a和信息片段b，交換父代之間的信息片段，剔除父代1中與信息片段b沖突的基因，并將信息片段a中的基因從第二個交叉點開始從左向右依次插入，生成子代1；同理，對父代2進行操作；

LLH2。基于位置交叉(position-based crossover)，隨機生成一條與工序染色體長度相同的基因為0、1的染色體C，選取父代1、父代2,保留父代染色體與染色體C基因為1的位置相同的基因，得到染色體A、B，剔除父代2中與染色體A沖突的基因，將剩下的基因從左向右依次插入染色體A中得到子代1；同樣，剔除父代1中與染色體B沖突的基因，將剩下的基因從左向右依次插入染色體B中，得到子代2；

LLH3。優(yōu)先保持交叉(precedence preservative crossover)，隨機生成一條與工序染色體長度相同的基因為1、2的染色體C，從父代1(基因為1)到父代2(基因為2)中取未使用的最左邊基因；

LLH4。多點交叉(multi-point crossover)，該操作為隨機生成一條與機器染色體長度相同的基因為0、1的染色體C，選取父代P1、P2,保留父代染色體與染色體C基因為1的位置相同的基因，交換父代與染色體C基因為0的位置相同的基因，得到兩個子代染色體C1、C2；

LLH5。優(yōu)先級操作交叉(precedence operation crossover)，將工件分為工件集1和工件集2，選取父代P1和父代P2，將P1、P2中工件集1的基因分別復制到子代C1和子代C2中的相同位置，然后將P1、P2中工件集2的基因分別按P1、P2中的順序依次填充到C2、C1中空余的基因位上，得到兩個子代工序染色體C1、C2。

2.2.2 變異算子

LLH6。交換變異(swap mutation),在工序染色體上隨機選擇兩個隨機位置(p1,p2),并交換這些位置上的基因;

LLH7。移動變異(shift mutation),選擇一個基因位置p,然后將位置p上的基因隨機向左或向右移動s次;

LLH8。逆轉變異(inversionmutation),在染色體中隨機選擇兩個位置(p1,p2)之間的基因,將兩個位置之間的基因逆序排列;

LLH9。隨機變異(random mutation)，選取父代P，隨機生成一條與機器染色體長度l相同的染色體a，其基因為(0，1)之間實數，若a(i)

將各種變異算子整合得到交叉算子示意圖,如圖2所示。

圖2 變異算子示意圖

2.3 編碼解碼與初始種群

2.3.1 編碼與解碼

在高層策略域中,染色體中的每個基因是由上文的低層啟發(fā)式算子構造,同一染色體中可以采用相同的低層啟發(fā)式算子,染色體長度為6。

解碼高層策略域染色體時,對低層策略域的種群,從左到右依次執(zhí)行染色體中低層啟發(fā)式算子,在執(zhí)行完每個低層啟發(fā)式算子后,對操作前后的兩個解的適應度值進行比較,若更新后解的適應值優(yōu)于舊解的適應值,用新解替換舊解,否則按一定概率接受新解,并繼續(xù)執(zhí)行余下的低層啟發(fā)式算子。

高層策略域染色體示意圖如圖3所示。

圖3 高層策略域染色體示意圖

對低層問題域,采用分段編碼方式,編碼示意圖如圖4所示。

圖4 問題域染色體編碼

圖4中：前段為工序排序染色體編碼，用來確定工序加工順序，數值i表示工件號，而數值出現的次數j表示該工件的第j道工序，對應的工序為Oij；后段為機器選擇染色體編碼，機器編碼按順序為工件J1,J2,…,Jn的工序選擇的加工機器，用數值n表示選擇該工序可加工機器集合中的第n臺機器。

2.3.2 初始種群

采用隨機初始化方法生成高層策略種群。

采用貪婪初始化方法對低層問題域種群進行初始化,具體流程如下:

步驟(1)：設置參數。MPT：機器{M1,M2,…,Mm}對應的緊前工序完工時間，初始值為0；JPT：工件{J1,J2,…,Jn}對應的緊前工序完工時間，初始值為0；初始化基因位置參數k為1；

步驟(2)：隨機生成工序染色體編碼OS；

步驟(3)：為OS基因k上的工序Oij選擇機器：根據可選擇加工集Mij，對比MPT與JPT，確定工序Oij在可選擇加工機器上的開始加工時間，加上加工時間以確定在每臺機器上的完工時間，并計算在每臺機器上的能耗，將完工時間及能耗進行歸一化處理，選擇加權和最小的機器加工工序Oij；

步驟(4)：根據工序Oij選擇的機器，更新MPT與JPT集合中的相應數據，k=k+1；

步驟(5)：循環(huán)執(zhí)行步驟(3)、步驟(4)，根據OS為所有工序選擇機器。

3 實例仿真與結果分析

在Windows10操作系統(tǒng)中,筆者采用MATLAB R2016b編程語言,進行仿真實驗。

3.1 算法性能分析

筆者選取文獻[15]基準算例,以最大完工時間Cmax為目標,驗證基于貪婪初始化方法生成初始化種群的遺傳算法運行效率,并與隨機初始化的遺傳算法和文獻[16]146-149采用的改進初始化的遺傳算法進行比較。

分別迭代200次后,收斂對比圖如圖5所示。

圖5 迭代收斂對比圖方法1為隨機初始化遺傳算法,方法2為文獻[16]150采用的遺傳算法,方法3為筆者采用貪婪初始化的遺傳算法;從左至右依次為8×8、10×10、15×10問題

從圖5可以看出:方法一和方法二迭代200次后陷入局部最優(yōu)解,方法三可以快速跳出局部最優(yōu)解,獲得全局最優(yōu)解。

可見,采用貪婪初始化生成初始種群的算法具有較快的收斂速度和較高的運行效率。

3.2 實例仿真分析

為驗證超啟發(fā)式遺傳算法的有效性,筆者選取文獻[13]143提出的算例(即一個簡化后的8×7 FJSP方問題,表示車間內有8個工件,在7臺機器上進行加工的車間調度問題),以最大完工時間和能耗為目標,對加工車間調度方案進行優(yōu)化。

具體數據如表1所示。

表1 加工車間簡化后的FJSP實例

筆者將采用超啟發(fā)式遺傳算法所得結果,與采用遺傳算法[13]142-143和免疫遺傳算法[17]169-170所得結果進行了比較。

采用超啟發(fā)式遺傳算法得到較優(yōu)結果的調度甘特圖,如圖(6～8)所示。

圖6 調度甘特圖(Cmax=64,Emin=676.3)

圖7 調度甘特圖(Cmax=65,Emin=657.6)

圖8 調度甘特圖(Cmax=69,Emin=647)

采用3種算法對相同算例進行求解,所得結果如表2所示。

表2 算例結果對比

對比分析表2中的數據可以看出:采用3種算法獲得的3組解中,Cmax這個目標值最小都為64;并且在相同Cmax目標值下,采用超啟發(fā)式遺傳算法所得的Emin目標值小于其他算法。

由此可以得出結論:

在Cmax目標值上,超啟發(fā)式遺傳算法與其余兩種算法水平相近;在Emin目標值上,超啟發(fā)式遺傳算法則優(yōu)于其余兩種算法,從而驗證了超啟發(fā)式遺傳算法的有效性和通用性。

4 結束語

筆者對柔性作業(yè)車間綠色目標值調度進行了研究,以最大完工時間和能耗為目標,對目標值進行歸一化處理,以目標值加權和為目標函數;提出了一種超啟發(fā)式遺傳算法,以此來對高度問題進行求解,其中高層策略采用遺傳算法,并設計了9種低層啟發(fā)式算法;采用隨機方法生成高層策略域種群,并設計貪婪初始化方法生成低層問題域種群;最后,通過Kacem算例及實例的仿真結果與其他算法進行了對比,對算法的正確性進行了驗證。

研究結果表明:

(1)與參考算法相比,采用貪婪初始化生成初始種群的超啟發(fā)式遺傳算法具有較快的收斂速度和較高的運行效率;

(2)采用超啟發(fā)式遺傳算法獲得的解的質量不低于部分傳統(tǒng)啟發(fā)式算法,說明超啟發(fā)式算法具有一定通用性。

在后續(xù)研究中,筆者將考慮更多實際因素,增加求解的目標,以提高超啟發(fā)式算法的實用性。