基于遺傳算法的多目標(biāo)車間調(diào)度*

靳彬鋒，畢 利

(寧夏大學(xué) 信息工程學(xué)院，銀川 750021)

0 引言

車間調(diào)度問題是現(xiàn)代制造企業(yè)自身生存和發(fā)展的基礎(chǔ)[1]。調(diào)度任務(wù)中的單目標(biāo)與多目標(biāo)問題，以及如何合理有效的使用調(diào)度方法，求出滿足生產(chǎn)目標(biāo)的優(yōu)化結(jié)果，許多學(xué)者進行了研究并取得了豐富的成果[2]。由于多目標(biāo)的生產(chǎn)安排更符合制造業(yè)的需求，尤其是柔性作業(yè)車間調(diào)度更貼近實際調(diào)度情況，受到了學(xué)者的廣泛關(guān)注[3]。

文獻[4]提出了一種針對柔性車間調(diào)度問題(FJSP)兩階段節(jié)能的優(yōu)化方法。在第一階段機器選擇方面應(yīng)用了改進的遺傳算法(MGA)，在第二階段工序選擇方面采用了將遺傳算法(GA)與粒子群優(yōu)化(PSO)相結(jié)合的混合方法。文獻[5]提出一種結(jié)合Cauchy分布的粒子群算法和遺傳算子(HPSO+GA)相結(jié)合的混合方法，找到了FJSP問題中能使makespan最小化的工作序列。文獻[6]提出了一種混合遺傳算法(HGA)，用于解決分布式的柔性作業(yè)車間調(diào)度問題(DFJSP)，應(yīng)用了一種新的編碼機制來解決無效的作業(yè)分配問題。文獻[7]提出了一種基于可變區(qū)間重調(diào)度策略(VIRS)的動態(tài)重新調(diào)度方法，以處理動態(tài)柔性作業(yè)車間調(diào)度中的機器故障、緊急工作到達和工件損傷等問題。另一方面，提出了一種改進的遺傳算法(GA)，以求得makespan的最小化。文獻[8]在遺傳算法中加入再激活(reactivation)機制，避免了傳統(tǒng)GA 算法在求解 FJSP 時陷入局部最優(yōu)的情況，增加了種群的多樣性。

本文針對遺傳算法在柔性作業(yè)車間調(diào)度中存在的早熟和搜索性能較差的現(xiàn)象，除了對基本遺傳算法做了改進以外，還結(jié)合模擬退火算法，應(yīng)用模擬退火算法跳出局部最優(yōu)的能力，給出了一種新的混合遺傳算法(HGSA)，用以實現(xiàn)在柔性車間調(diào)度的尋優(yōu)處理。

1 數(shù)學(xué)模型

對柔性作業(yè)車間調(diào)度的問題進行描述：由n個工件Ji組成的工件集J={Ji，1≤Ji≤n}，由m臺機器Mi組成的機器集M={Mi，1≤Mi≤m}，同時每個工件Ji有nj道工序，Oij表示工件Ji的第j道工序，工序Oij可以選擇的加工機器集為W，并且在加工過程中，必須滿足以下約束條件：

(1)某一時刻同一臺機器上只能加工一個工件；

(2)正在加工的工件不能被中斷；

(3)同一工件中的工序之間具有先后約束，不同工件中的工序沒有加工順序的約束；

(4)某一時刻一個工件只能被加工一次。

柔性作業(yè)車間調(diào)度的主要任務(wù)就是將待加工的n個工件所包含的全部工序Oij選擇相應(yīng)機器進行加工，完成所設(shè)定的目標(biāo)，并且對所求目標(biāo)進行優(yōu)化。

(1)最小化最大完工時間：全部待加工工件完成的最后時間，表示為F1，如式(1)所示：

F1= min{max{maxcj}}

(1)

其中，Cj表示工件Jj的完工時間。

(2)最小化加工成本：工件在機器上加工時所耗費的成本Cv與機器處于就緒狀態(tài)所消耗的成本Cs之和，表示為F2，如式(2)所示：

(2)

FDk>0且FD0=0

(3)

FSk>0且FS0=0

(4)

tijk≥0且ti0k=0

(5)

其中，tijk表示工件Ji的第j道工序在加工機器Mk(Mk∈W)上的加工時間。Xijk表示為決策變量，即工件Ji的第j道工序是否選擇在機器Mk上進行加工，Xijk=1表示機器Mk被選中，Oij在機器Mk上進行加工；Xijk=0表示機器Mk沒有被選中。T*表示最優(yōu)調(diào)度方案的最大完工時間。FDK表示第K臺機器的動態(tài)耗費率；FSk表示第K臺機器的靜態(tài)耗費率。

(3)機器最大負(fù)荷：單臺機器設(shè)備最大的使用負(fù)荷，表示為F3，如式(6)所示：

(6)

(4)機器總負(fù)荷：工件加工時所有機器設(shè)備的使用負(fù)荷，表示為F4，如式(7)所示：

(7)

(5)約束條件：

(8)

Stijk>0且Sti0k=0

(9)

2 HGSA算法

2.1 編碼

針對FJSP的特點，采用基于工序-機器的雙層實數(shù)編碼方式，如表1所示。在關(guān)于車間調(diào)度問題的編碼方式中，將加工工序還有機器作為調(diào)度編碼來實現(xiàn)，這樣得到的編碼都是合法、有效的。采用實數(shù)型權(quán)值編碼，解決了傳統(tǒng)的整數(shù)型編碼造成的搜索空間被制約的影響，并且有利于算法加入實數(shù)型遺傳算子，從而提高算法的收斂[9]。

表1 編碼操作

在表1中，基因的整數(shù)部分表示的是工件Ji。小數(shù)部分指的是由輪盤賭決定的該工件選擇機器的可能性，比如工件J4的工序O41，可選機器有6個：M1，M2，M3，M4，M5，M6，每個機器被選擇的概率都是1/6，O41的小數(shù)部分是0.21，則選擇概率為[16.6,0.33)，選擇機器為M2。

2.2 初始化參數(shù)

由于解空間個數(shù)遠(yuǎn)大于初始種群的個數(shù)，對于初始種群的產(chǎn)生，通過合適的方式可以保持種群的多樣性[10]。而傳統(tǒng)的隨機方式可能因為隨機解集中在某一區(qū)域致使算法搜索與收斂不能在全局范圍內(nèi)較好的展開。本文以距離為依據(jù)的方法來產(chǎn)生均勻的初始種群，其流程圖見圖1，步驟描述如下：

(1)選擇初始個體X1，X2，X3，…，Xn，選取任意Xi(1≤i≤n)作為第一個種群中心Y1，即Xi=Y1；

(2)選取距離Xi最遠(yuǎn)的個體Xj為第二個種群中心Y2，則Xj=Y2，計算Y1與Y2的海明距離(Hamming distance)H12；

(3)依次計算個體X1，X2，X3，…，Xn與種群中心Y1、Y2的海明距離Hp1、Hp2，若有min{max(Hp1，Hp2)，p=1，2，…，n} < 0.5H12，則令Xp=Y3，轉(zhuǎn)到(4)，否則轉(zhuǎn)到(6)；

(4)計算Hp1、Hp2、Hp3，若有min{max(Hp1，Hp2，Hp3)，p=1，2，…，n} < 0.5H12，則令Xp=Y4，轉(zhuǎn)到(5)，否則轉(zhuǎn)到(6)；

(5)計算Hp1、Hp2、Hp3，Hp4，若有min{max(Hp1，Hp2，Hp3，Hp4)，p=1，2，…，n} < 0.5H12，則令Xp=Y1，形成新的種群中心，轉(zhuǎn)到(1)，否則轉(zhuǎn)到(6)；

(6)根據(jù)海明距離把全部個體分配到距離其最遠(yuǎn)的種群中。

圖1 種群初始化流程圖

2.3 適應(yīng)度計算

在FJSP多目標(biāo)生產(chǎn)中，適應(yīng)度函數(shù)要綜合考慮不同的目標(biāo)值，因此設(shè)計了一種帶權(quán)值的多目標(biāo)適應(yīng)度函數(shù)，如式(10)所示：

F=1/(ω1·θ1·F1+ω2·θ2·F2+ω3·θ3·F3+ω4·θ4·F4)

(10)

其中，ω1+ω2+ω3+ω4=1，根據(jù)實際調(diào)度情況選擇不同的權(quán)值。θ值表示將數(shù)據(jù)集經(jīng)過歸一化處理后，將目標(biāo)函數(shù)值轉(zhuǎn)化成了相同的數(shù)量級。

2.4 選擇操作

采用輪盤賭的選擇方式[11]。首先對選擇出的個體根據(jù)適應(yīng)度函數(shù)進行適應(yīng)度值的計算，然后按照適應(yīng)度值對應(yīng)的選擇概率進行隨機選取，直到選出滿足設(shè)定數(shù)量的個體數(shù)。

2.5 交叉操作

交叉操作主要是通過父代染色體的交叉互換而得到新的個體[12]。根據(jù)編碼方式，采用適用于浮點型的拉普拉斯交叉算子。拉普拉斯交叉算子，從父代的拉普拉斯分布得到密度函數(shù)系數(shù)，在算術(shù)交叉中加入拉普拉斯分布的兩個系數(shù)，這樣來達到控制子代破壞父代優(yōu)良個體的概率，同時由于算術(shù)交叉的使用擴大搜索空間。假設(shè)在第s代的兩個個體Xs1與Xs2進行交叉，則其第s+1代中的個體Xs1′與Xs2′為：

(11)

(12)

其中，β為：

(13)

式(13)中的μ、b為拉普拉斯的分布參數(shù)，μ∈R是位置參數(shù)，b>0是尺度參數(shù)。μ、b的值可由父代的函數(shù)分布逆推得到。μ的作用是決定與父代種群個體的距離，在此基礎(chǔ)上，b越大表示離父代個體越遠(yuǎn)，b越小表示越靠近父代。a∈[0，1]表示一個分布均勻的隨機數(shù)。在μ、b的共同作用下，父代個體之間的距離影響其子代之間的距離，即子代是對父代成正比例的延長。

2.6 變異操作

逆轉(zhuǎn)變異是一種特別的變異算子。它通常是在個體的染色體編碼上隨機選擇兩個點，即逆轉(zhuǎn)點，接著將這兩個點的基因根據(jù)逆轉(zhuǎn)概率ρ逆向排序。二進制編碼的逆轉(zhuǎn)概率例子如下：

父代染色體:1 0 0 1 0 1 1 0 1 0 0

假設(shè)3和8是兩個逆轉(zhuǎn)點，則

子代染色體:1 0 0 1 1 0 1 0 1 0 0

從上面可以看出，子代染色體經(jīng)過逆轉(zhuǎn)變異操作以后，逆轉(zhuǎn)點3和逆轉(zhuǎn)點8之間的基因序列被逆向排序，即從0 1 0 1 1 0序列，變成了0 1 1 0 1 0序列。

2.7 模擬退火算法

在用遺傳算法求解問題的過程中，收斂速度在后期會變慢下來，這是因為它有突出的全局搜索能力，同時局部搜索能力較弱。為了解決這一問題，讓新的混合算法具有很好的全局搜索和局部搜索能力在遺傳算法中引入模擬退火算法。模擬退火算法因為其杰出的擺脫局部極值能力而受歡迎，其步驟如下所示：

(1)初始化參數(shù)：初始溫度Tmax，初始解S，每個溫度值T的迭代次數(shù)L；

(2)fork=1:L；

①擾動產(chǎn)生新解S′；

②Metropolis準(zhǔn)則。計算增量△T=C(S′)-C(S)，C(S)為評價函數(shù)；

③若△T< 0，S′成為新的當(dāng)前解，否則以概率exp(-△T/T)接受S′作為當(dāng)前解；

④若滿足終止條件，輸出當(dāng)前解作為最優(yōu)解，算法結(jié)束；

(3)溫度T逐漸減少，且T≥ 0，轉(zhuǎn)到第(2)步。

因為局部搜索比較耗時，為了順利地找到最優(yōu)解，在模擬退火算法中加入了基于逆序的局部搜索方法，具體流程圖見圖2。其基本思想是：在遺傳算法中，每一代個體經(jīng)過選擇、交叉和變異等遺傳操作之后，都需要對當(dāng)前最優(yōu)個體進行局部搜索?；谀嫘虻木植克阉鞣椒ㄈ缦拢?/p>

(1)在當(dāng)前解中隨機選擇編碼的兩個不同位置c、d(c

(2)對新個體進行解碼，并計算其適應(yīng)度值，如果優(yōu)于逆序前的個體則替換，否則繼續(xù)保留；

(3)返回(1)。

圖2 基于逆序的SA流程圖

3 仿真分析

3.1 運行環(huán)境

在Intel(R) Core(TM) i5-3337U、CPU主頻 1. 80 GHz、4.00GB 內(nèi)存、Windows8.1操作系統(tǒng)下, 利用 Matlab R2014b編程實現(xiàn)上述算法。

3.2 實例仿真

對某航空發(fā)動機公司生產(chǎn)車間一個生產(chǎn)線上的實際數(shù)據(jù)經(jīng)過取整處理后，得到 6 個工件和6 臺機器，每個工件有 10 道工序的 FJSP 問題, 進行了仿真實驗。

HGSA算法初始參數(shù)設(shè)置如下：遺傳算法的種群規(guī)模為100，最大迭代次數(shù)為300，交叉概率為0.9，變異概率為0.1，適應(yīng)度函數(shù)權(quán)值根據(jù)工廠調(diào)研設(shè)置為ω1=0.6，ω2=0.2，ω3=ω4=0.1。模擬退火算法的初始溫度是100，冷卻系數(shù)是0.99。用改進的混合算法得到的近似Pareto解集如表2所示，調(diào)度人員可以根據(jù)情況選一組解進行加工安排。另外由于所得甘特圖較多，這里只展示第一個Pareto解對應(yīng)的甘特圖如圖3所示，圖4為其對應(yīng)的收斂圖。

表2 所得Pareto近似解集

圖3 序號 1Pareto解對應(yīng)的甘特圖

圖4 序號1Pareto解對應(yīng)的收斂圖

為了驗證本算法的性能，與其他算法進行對比分析。運行20次取平均值。它們的比較結(jié)果如表3所示。

表3 不同算法的結(jié)果比較

從表3可以看出，HGSA算法各項值均比傳統(tǒng)的混合算法、遺傳算法的結(jié)果要好，完工時間分別縮小了54.7%、61.6%，加工成本分別節(jié)省了36.1%、34.8%，最大機器負(fù)荷分別降低了62.2%、69.5%，機器總負(fù)荷分別降低了9.7%、10.2%。另外，單一的模擬退火算法應(yīng)用于柔性作業(yè)車間調(diào)度時，其算法本身的特性，使得算法的時間復(fù)雜度特別大，與HGSA算法相比不具有優(yōu)勢。

4 結(jié)束語

多目標(biāo)柔性作業(yè)車間調(diào)度是離散制造業(yè)中的重要一環(huán)，它比JSP更加貼近實際生產(chǎn)，文本提出了HGSA算法來求解這一問題。首先是用距離來得出均勻的初始化種群，然后是輪盤賭的方式進行選擇，隨后經(jīng)行了拉普拉斯交叉和逆轉(zhuǎn)變異操作，接著是模擬退火的局部尋優(yōu)，從而使本算法達到全局最優(yōu)。仿真實例證明，本算法有較好的全局搜索能力，能得出質(zhì)量較高的Pareto解，對實際的生產(chǎn)調(diào)度問題具有一定的借鑒意義。