一種面向FJSP的混合優(yōu)化遺傳算法

侍守創(chuàng)，江 浩，韓占港，蔣馨宙

(1.中國(guó)船舶重工集團(tuán)公司第七一六研究所，江蘇 連云港 222002；2.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

1 引言

柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem，F(xiàn)JSP)是一類滿足任務(wù)配置需求和順序約束要求的組合優(yōu)化問題，屬于NP-hard范疇[1]。

近年來，針對(duì)FJSP問題，國(guó)內(nèi)外學(xué)者進(jìn)行了許多相關(guān)研究，并取得了一些成果。目前代表性研究方法有粒子群算法、遺傳算法、鄰域搜索算法等，同時(shí)學(xué)界提出可采用啟發(fā)式算法如禁忌搜索算法[2]、模擬退火算法[3]、遺傳算法[4]以及蟻群算法[5]等解決該問題。魏巍等人[6]以加工質(zhì)量、加工成本和加工工期為多目標(biāo)，并采用一種改進(jìn)的Pareto算法進(jìn)行優(yōu)化，缺陷是不適合數(shù)據(jù)規(guī)模較大的問題，并且FJSP是NP-hard問題，其求解時(shí)間隨著數(shù)據(jù)規(guī)模增大而迅速增長(zhǎng)，而近似方法可以在確定時(shí)間內(nèi)得到一個(gè)較優(yōu)解。針對(duì)FJSP的求解方法大致分為精確方法和近似方法兩類，精確方法適用于小規(guī)模FJSP問題，當(dāng)問題規(guī)模增大時(shí)，便不再適用[7]。基于智能優(yōu)化算法的解決方案能夠在可行時(shí)間內(nèi)求得大規(guī)模FJSP問題的近優(yōu)解，現(xiàn)已成為解決柔性作業(yè)車間調(diào)度問題的主流方法以及研究熱點(diǎn)。Xia和Wu[8]提出了使用粒子群和模擬退火相結(jié)合的方式來解決FJSP，但是多次運(yùn)行結(jié)果方差較大，不能有效得到一個(gè)較優(yōu)解。Fattah和Mehrabad[9]提出一個(gè)數(shù)學(xué)模型并采用禁忌搜索和模擬退火算法來解決實(shí)際生產(chǎn)環(huán)境中的作業(yè)調(diào)度問題，然而對(duì)約束情況較多、情況較復(fù)雜的柔性作業(yè)車間問題解決能力差。Gao和Sun[10]提出一種解決 FJSP 的混合遺傳算法，使用鄰域下降和改進(jìn)染色體結(jié)構(gòu)相結(jié)合的方式，提高種群中個(gè)體的適應(yīng)性，但是編碼方法過去復(fù)雜。Yao和Hu[11]提出了一個(gè)優(yōu)化蟻群算法，通過改進(jìn)適應(yīng)性參數(shù)和交叉算子等來提高算法效果。其中，遺傳算法以其隱式并行處理能力、魯棒性強(qiáng)的特點(diǎn)，在FJSP問題上得到了廣泛應(yīng)用。然而，傳統(tǒng)遺傳算法存在收斂速度過快、容易陷入局部最優(yōu)的缺陷，應(yīng)用效果并不是十分理想，因此，學(xué)界對(duì)遺傳算法進(jìn)行了不同程度的改進(jìn)[12]。劉勝等人[13]采用非線性排序法重新設(shè)計(jì)了輪盤賭選擇算子，以及工序編碼段和機(jī)器編碼段雙變異的互換變異算子;張國(guó)輝等[14]設(shè)計(jì)一種局部搜索、全局搜索及隨機(jī)產(chǎn)生相結(jié)合的初始化種群的方法，提高種群初始解的質(zhì)量，缺陷是算法處理時(shí)間過長(zhǎng);張超勇等[15]提出一種改進(jìn)的基于工序的編碼以及主動(dòng)調(diào)度的解碼機(jī)制，不能有效解決多目標(biāo)問題。Jin Wang等[16]提出并實(shí)現(xiàn)了其實(shí)時(shí)化基于實(shí)時(shí)制造數(shù)據(jù)的調(diào)度，為了得到一個(gè)可行解，采用了無限次重復(fù)博弈優(yōu)化方法，缺點(diǎn)是需要較長(zhǎng)的時(shí)間才能得到一個(gè)近優(yōu)解。Robert L等[17]提出了一種改進(jìn)的元啟發(fā)式算法，增加了資源分配染色體和改進(jìn)了用于搶占處理和資源分配的擾動(dòng)操作符。

本文提出一種混合優(yōu)化的遺傳算法，從染色體選擇、變異等多個(gè)步驟入手進(jìn)行優(yōu)化，在確定的時(shí)間內(nèi)，對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度可以得到一個(gè)有效的近優(yōu)解，且收斂速度更快。

2 問題描述

2.1 柔性作業(yè)車間調(diào)度

對(duì)在柔性作業(yè)車間調(diào)度問題中，任務(wù)由一系列工序組成，每臺(tái)機(jī)器所需處理的工序不確定。對(duì)每一道工序，都有一組具有不同處理時(shí)間的機(jī)器可用。問題描述涉及的變量符號(hào)定義如下：

● 任務(wù)集：J={J1，J2，J3，…，JN}，其中Ji∈J(i=1，2，…，N)為第i個(gè)任務(wù)

● 機(jī)器集：M={M1，M2，M3，…，MR}，其中Mr∈M(r=1，2，…，R)為第r個(gè)機(jī)器

● 工序集：O={O1，O2，…，ON}，Oi∈{O1，O2，…，ON}為第i個(gè)任務(wù)的工序

● 工序數(shù)目：ni，任務(wù)Ji的工序數(shù)，每一個(gè)任務(wù)Ji由ni道工序組成

● 工序子集：Oi={Oi1，Oi2，…，Oini} ，其中Oij，(j=1，2，…，ni)表示任務(wù)Ji的第j道工序

● 完成工序Oij的機(jī)器集合：Zij

● 參與處理工序Oij的機(jī)器：Mk∈Zij?M

● 加工時(shí)間：pijk，任意的機(jī)器mk∈Zij處理工序Oij的加工時(shí)間

給定N個(gè)加工任務(wù)J={J1，J2，J3，…，JN}，由R臺(tái)機(jī)器M={M1，M2，M3，…，MR}完成；其中每個(gè)任務(wù)Ji∈J包含ni道工序{oi1，oi2，…，oini}，每道工序Oij可由機(jī)器集合Zij中的機(jī)器完成。

且該問題需滿足以下約束條件：

1)初始狀態(tài)約束：所有機(jī)器在0時(shí)刻可用，所有任務(wù)0時(shí)刻可進(jìn)行；

2)機(jī)器占用約束：一臺(tái)機(jī)器同一時(shí)刻最多只能進(jìn)行一道工序；

3)任務(wù)進(jìn)行約束：任一任務(wù)在每一時(shí)刻僅能在一臺(tái)機(jī)器上進(jìn)行，并且任務(wù)的不同工序需按給定的先后順序進(jìn)行，不同任務(wù)的工序之間是獨(dú)立的，沒有先后約束；

4)工序連續(xù)加工約束：任一工序一旦開始，便不允許中斷。

則柔性車間作業(yè)調(diào)度問題可分解為：

1)任務(wù)分配問題：合理分配每一道工序Oij給機(jī)器Mk∈Zij。

2)資源調(diào)度問題：動(dòng)態(tài)規(guī)劃某臺(tái)機(jī)器上分配的任務(wù)，以獲得一個(gè)全局優(yōu)化的解，使得適應(yīng)度函數(shù)盡可能的小。

2.2 適應(yīng)度函數(shù)

本文基于四種約束條件：最少等待時(shí)間，優(yōu)先級(jí)優(yōu)先，最少超期任務(wù)和強(qiáng)制保障，定義以下適應(yīng)度函數(shù)：

1)最少等待時(shí)間

(1)

其中，Ci為任務(wù)Ji的實(shí)際完成時(shí)間。最少等待時(shí)間即找出實(shí)際完成時(shí)間最長(zhǎng)的任務(wù)，最小化其所需花費(fèi)時(shí)間。

2)優(yōu)先級(jí)優(yōu)先:預(yù)先為N個(gè)任務(wù)制定優(yōu)先級(jí)，優(yōu)先級(jí)高的需優(yōu)先完成。

3)最少超期任務(wù)

(2)

式中，vi表示任務(wù)Ji的權(quán)重，Ti定義為任務(wù)未在預(yù)期時(shí)間內(nèi)完成的超期懲罰，ei表示任務(wù)Ji的預(yù)期完成時(shí)間，并且有

Ti=max{0，Ci-ei}

(3)

4)強(qiáng)制保障：任務(wù)集中，存在某些任務(wù)是必須要保障完成的，稱為強(qiáng)制保障。

3 mGAs算法

3.1 算法優(yōu)化

本文提出的混合優(yōu)化遺傳算法，在個(gè)體選擇階段采用量子粒子群算法優(yōu)化個(gè)體選擇算子，并采用精英保留策略篩選出適應(yīng)度最大的個(gè)體；在交叉和變異階段，使用了交叉概率和變異概率動(dòng)態(tài)變化的方式，并且設(shè)計(jì)了機(jī)器鏈段編碼基于貪心算法的單點(diǎn)變異算子?？傮w算法流程圖如圖1所示。

圖1 混合優(yōu)化遺傳算法基本流程圖

3.1.1 染色體編碼及適應(yīng)度函數(shù)確定

本文采用分段編碼方式，第一段編碼為工序排序，對(duì)工序的加工順序進(jìn)行編碼，第二段編碼為對(duì)每道工序所需機(jī)器進(jìn)行編碼。此種編碼方式可將工序和機(jī)器相對(duì)應(yīng)，不僅能保證產(chǎn)生可行調(diào)度，還可避免死鎖問題。

設(shè)某一任務(wù)的適應(yīng)度由最晚完工時(shí)間、優(yōu)先級(jí)優(yōu)先和最少超期任務(wù)三個(gè)約束條件約束，其適應(yīng)度函數(shù)為

(4)

式中，F(xiàn)ullFillTime為最晚完工時(shí)間，Tardiness為超期懲罰，定義如下：

(5)

式中，Ci為任務(wù)Ji的預(yù)期完成時(shí)間，ei為任務(wù)Ji的預(yù)期完成時(shí)間。

3.1.2 初始化種群及個(gè)體選擇

對(duì)使用隨機(jī)生成方式進(jìn)行初始種群的產(chǎn)生，可保證初始種群個(gè)體的多樣性，使個(gè)體盡可能地分布在解空間的大部分區(qū)域。

個(gè)體選擇階段，首先根據(jù)建立的種群，將單個(gè)染色體作為粒子，開始粒子的尋優(yōu)迭代，繼而對(duì)粒子最優(yōu)位置以及粒子群的最優(yōu)位置進(jìn)行計(jì)算并對(duì)結(jié)果進(jìn)行分析，選出若干個(gè)體，最后使用精英策略從選出的個(gè)體中篩選出適應(yīng)度最大的若干個(gè)體。其競(jìng)爭(zhēng)選擇過程如圖2所示。

圖2 個(gè)體競(jìng)爭(zhēng)選擇示意圖

3.1.3 交叉與變異

本文測(cè)試了三種交叉算子：順序交叉(OX)、循環(huán)順序交叉(COX)、混合順序交叉(MOX)，以及兩種變異算子：逆轉(zhuǎn)變異(OBM)、互換變異(SBM)，根據(jù)測(cè)試結(jié)果，最終采用效率最高的順序交叉算子產(chǎn)生子代染色體。

變異的作用是使算法能探索新的解空間，跳出局部最優(yōu)解。變異算子的選擇對(duì)算法能否求得全局最優(yōu)解有很大的影響。對(duì)于工序段的變異，是以互換變異實(shí)現(xiàn)的，即隨機(jī)交換工序段序列兩個(gè)不同位置處的值，如圖3所示。

圖3 染色體工序段變異示意圖

對(duì)機(jī)器段序列的變異則使用貪心算法：隨機(jī)產(chǎn)生一個(gè)變異點(diǎn)，再根據(jù)變異點(diǎn)對(duì)應(yīng)工序的加工機(jī)器集，對(duì)該點(diǎn)的值進(jìn)行更新。若存在一個(gè)機(jī)器Mi，對(duì)于同一道工序Ok，其加工時(shí)間少于當(dāng)前變異點(diǎn)值所指向機(jī)器Mj的加工時(shí)間，則更新當(dāng)前基因值為i，其中，Mi與Mj都屬于實(shí)現(xiàn)工序Ok的機(jī)器集。

如圖4所示，隨機(jī)產(chǎn)生的變異點(diǎn)為最后一位，對(duì)應(yīng)任務(wù)3的第二道工序，并且存在機(jī)器M2加工時(shí)間少于當(dāng)前指向機(jī)器M1，則更新當(dāng)前機(jī)器編碼變異點(diǎn)值為2。

圖4 染色體機(jī)器段變異示意圖

3.1.4 染色體解碼及其優(yōu)化

解碼染色體包括任務(wù)分配以及工序調(diào)度兩步。

完成任務(wù)分配，需順序遍歷染色體的工序段，根據(jù)當(dāng)前遍歷的工序進(jìn)行任務(wù)分配和適應(yīng)度函數(shù)的求解。例如，設(shè)當(dāng)前工序段基因序列為

[3，2，1，3，1，1，2，3，2]

則據(jù)此序列以及機(jī)器段編碼，依次將工序分配給指定的機(jī)器加工隊(duì)列進(jìn)行加工。然而在實(shí)際任務(wù)分配過程中，常常存在機(jī)器工序序列的間隔過大的問題，也就是存在兩個(gè)相鄰工序，其間的等待時(shí)間過長(zhǎng)，完全可以將后續(xù)的符合一定約束條件的工序提前，進(jìn)行“插隊(duì)”操作。實(shí)現(xiàn)“插隊(duì)”操作的偽代碼如下：

算法1 染色體解碼及優(yōu)化偽代碼

輸入 待插入工序p，機(jī)器任務(wù)隊(duì)列MissionQueue

輸出 處理完的機(jī)器任務(wù)隊(duì)列MissionQueue

1)BEGIN:

2)Initialize:gapBegin=0，gapEnd=0

3)for m in MissionQueue do

4)gapEnd=m.Start;

5)if gapEnd-gapBegin >=p.costTime

&&gapEnd-costTime>=preProcessFinishTime do

∥工序“插隊(duì)”需要滿足的約束條件

6)if preProcessFinishTime>=gapBegin do

7)p.Start=preProcessFinishTime

8)else

9)p.Start=gapBegin;

10)end if

∥更新工序的開始和結(jié)束時(shí)間

∥preProcessFinishTime是p的前置工序結(jié)束時(shí)間

11)p.End=p.Start+p.costTime

12)insert(m，p)

13)return MissionQueue

14)end if

15)gapBegin=m.End;

16)end for

∥更新工序的開始和結(jié)束時(shí)間

17)update(p.start，p.end)

18)enQueue(MissionQueue，p);

19)return MissionQueue

20)END

3.2 算法描述

算法2：算法整體框架偽代碼

輸入 數(shù)據(jù)集，算法參數(shù)：初始種群大小(PS)，交叉率(CR)，變異率(MR)

輸出 調(diào)度方案

1)BEGIN:

2)Initialize:initial population

3)Evaluate population

4)while not reach the termination condition do

5)while not yield enough individual do

∥量子粒子群和精英策略相結(jié)合進(jìn)行個(gè)體選擇操作

6)Select individuals from population by QPS and elite strategy

7)if reach crossover condition do

8)update(CR)

9)Crossover individuals which were selected

∥工序段：順序交叉

10)Procedure sequence:OX

∥機(jī)器段：兩點(diǎn)交叉

11)Machine sequence:two-point crossover

12)end if

13)end while

14)if reach mutation condition do

15)update(MR)

∥工序段：兩點(diǎn)交換

16)Procedure sequence:two-point swapping

∥機(jī)器段：基于貪心算法選擇變異機(jī)器

17)Machine sequence:choose the machine with least process time

18)end if

19)yield new population

20)Evaluate new population

21)end while

22)output a optimized schedule

23)END

在設(shè)置完算法參數(shù)之后，接著隨機(jī)產(chǎn)生初始種群。初始種群中的每一個(gè)個(gè)體的工序段基因序列和機(jī)器段基因序列都是在編碼的規(guī)則下隨機(jī)產(chǎn)生的。在個(gè)體選擇時(shí)加入量子粒子群算法，提升了收斂速度和最終產(chǎn)生的解的質(zhì)量。算法最終會(huì)在達(dá)到預(yù)設(shè)的最大迭代次數(shù)時(shí)，或者產(chǎn)生預(yù)期的解時(shí)，終止循環(huán)，最后輸出結(jié)果。

4 實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)設(shè)計(jì)

本文選用Bradimarte[18]提出的若干個(gè)不同測(cè)試實(shí)例集(Mk01(10*6)、Mk03(15*8)、Mk05(15*4)和Mk08(20*10)等)對(duì)提出的混合優(yōu)化遺傳算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。

算法運(yùn)行環(huán)境如表3所示。

表3 運(yùn)行環(huán)境參數(shù)

本文測(cè)試所選擇的混合優(yōu)化遺傳算法運(yùn)行參數(shù)如表4所示，表中n為任務(wù)數(shù)，m為機(jī)器數(shù)。

表4 算法運(yùn)行參數(shù)

4.2 實(shí)驗(yàn)及結(jié)果分析

在最大完工時(shí)間的約束條件下，本文采用的混合優(yōu)化遺傳算法，與GANCE[19]和eGAs[20]同時(shí)使用Bradimarte提出的基準(zhǔn)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試并比較。

由圖5所示，分別使用文獻(xiàn)[20]和本文提出的算法在Mk04數(shù)據(jù)集上運(yùn)行了5次，其中包含了15個(gè)任務(wù)和8臺(tái)機(jī)器，記錄了平均最大完工時(shí)間隨著種群迭代次數(shù)的增加而減少的折線。從折線可以看出，在數(shù)據(jù)集相同、最終結(jié)果相近的情況下，本文所提出的算法在收斂速度上更具有優(yōu)勢(shì)。

圖5 mGAs與其它遺傳算法在Mk04上的對(duì)比

圖6中，本文所提出的算法與文獻(xiàn)[19]和文獻(xiàn)[20]中的算法在若干個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間之間的對(duì)比。根據(jù)數(shù)據(jù)集的復(fù)雜程度，初始種群數(shù)在50到300之間，運(yùn)行次數(shù)為5次，最終取平均值作為結(jié)果。

圖6 mGAs與其它算法在運(yùn)行時(shí)間上的對(duì)比

圖7中，在Mk02、Mk04和Mk06上運(yùn)行本文算法，從運(yùn)行結(jié)果可以看出在迭代一定次數(shù)后，算法可以得到一個(gè)較好的近優(yōu)解。

圖7 mGAs在Mk0等測(cè)試集上的對(duì)比

圖8 Mk01測(cè)試數(shù)據(jù)運(yùn)行結(jié)果甘特圖

5 結(jié)束語(yǔ)

本文在基于傳統(tǒng)遺傳算法解決柔性作業(yè)車間調(diào)度問題的研究基礎(chǔ)上，使用動(dòng)態(tài)調(diào)整交叉和變異概率的方式優(yōu)化傳統(tǒng)遺傳算法的交叉和變異算子，有效解決了遺傳算法過早收斂的問題；使用量子粒子群優(yōu)化傳統(tǒng)遺傳算法的選擇算子，使得算法在運(yùn)行結(jié)果上更加可靠。最后，通過在測(cè)試集上對(duì)本文算法以及其它算法進(jìn)行對(duì)比實(shí)驗(yàn)，證明本文所提出的混合優(yōu)化遺傳算法可以在更短的時(shí)間內(nèi)獲得一個(gè)有效的近優(yōu)解，并且驗(yàn)證了該算法的有效性。