一種面向FJSP的混合優化遺傳算法

侍守創，江 浩，韓占港，蔣馨宙

(1.中國船舶重工集團公司第七一六研究所，江蘇 連云港 222002；2.哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001)

1 引言

柔性作業車間調度問題(Flexible Job-shop Scheduling Problem，FJSP)是一類滿足任務配置需求和順序約束要求的組合優化問題，屬于NP-hard范疇[1]。

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

本文提出一種混合優化的遺傳算法，從染色體選擇、變異等多個步驟入手進行優化，在確定的時間內，對多目標柔性作業車間調度可以得到一個有效的近優解，且收斂速度更快。

2 問題描述

2.1 柔性作業車間調度

對在柔性作業車間調度問題中，任務由一系列工序組成，每臺機器所需處理的工序不確定。對每一道工序，都有一組具有不同處理時間的機器可用。問題描述涉及的變量符號定義如下：

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

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

● 工序集：O={O1，O2，…，ON}，Oi∈{O1，O2，…，ON}為第i個任務的工序

● 工序數目：ni，任務Ji的工序數，每一個任務Ji由ni道工序組成

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

● 完成工序Oij的機器集合：Zij

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

● 加工時間：pijk，任意的機器mk∈Zij處理工序Oij的加工時間

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

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

1)初始狀態約束：所有機器在0時刻可用，所有任務0時刻可進行；

2)機器占用約束：一臺機器同一時刻最多只能進行一道工序；

3)任務進行約束：任一任務在每一時刻僅能在一臺機器上進行，并且任務的不同工序需按給定的先后順序進行，不同任務的工序之間是獨立的，沒有先后約束；

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

則柔性車間作業調度問題可分解為：

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

2)資源調度問題：動態規劃某臺機器上分配的任務，以獲得一個全局優化的解，使得適應度函數盡可能的小。

2.2 適應度函數

本文基于四種約束條件：最少等待時間，優先級優先，最少超期任務和強制保障，定義以下適應度函數：

1)最少等待時間

(1)

其中，Ci為任務Ji的實際完成時間。最少等待時間即找出實際完成時間最長的任務，最小化其所需花費時間。

2)優先級優先:預先為N個任務制定優先級，優先級高的需優先完成。

3)最少超期任務

(2)

式中，vi表示任務Ji的權重，Ti定義為任務未在預期時間內完成的超期懲罰，ei表示任務Ji的預期完成時間，并且有

Ti=max{0，Ci-ei}

(3)

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

3 mGAs算法

3.1 算法優化

本文提出的混合優化遺傳算法，在個體選擇階段采用量子粒子群算法優化個體選擇算子，并采用精英保留策略篩選出適應度最大的個體；在交叉和變異階段，使用了交叉概率和變異概率動態變化的方式，并且設計了機器鏈段編碼基于貪心算法的單點變異算子。總體算法流程圖如圖1所示。

圖1 混合優化遺傳算法基本流程圖

3.1.1 染色體編碼及適應度函數確定

本文采用分段編碼方式，第一段編碼為工序排序，對工序的加工順序進行編碼，第二段編碼為對每道工序所需機器進行編碼。此種編碼方式可將工序和機器相對應，不僅能保證產生可行調度，還可避免死鎖問題。

設某一任務的適應度由最晚完工時間、優先級優先和最少超期任務三個約束條件約束，其適應度函數為

(4)

式中，FullFillTime為最晚完工時間，Tardiness為超期懲罰，定義如下：

(5)

式中，Ci為任務Ji的預期完成時間，ei為任務Ji的預期完成時間。

3.1.2 初始化種群及個體選擇

對使用隨機生成方式進行初始種群的產生，可保證初始種群個體的多樣性，使個體盡可能地分布在解空間的大部分區域。

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

圖2 個體競爭選擇示意圖

3.1.3 交叉與變異

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

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

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

對機器段序列的變異則使用貪心算法：隨機產生一個變異點，再根據變異點對應工序的加工機器集，對該點的值進行更新。若存在一個機器Mi，對于同一道工序Ok，其加工時間少于當前變異點值所指向機器Mj的加工時間，則更新當前基因值為i，其中，Mi與Mj都屬于實現工序Ok的機器集。

如圖4所示，隨機產生的變異點為最后一位，對應任務3的第二道工序，并且存在機器M2加工時間少于當前指向機器M1，則更新當前機器編碼變異點值為2。

圖4 染色體機器段變異示意圖

3.1.4 染色體解碼及其優化

解碼染色體包括任務分配以及工序調度兩步。

完成任務分配，需順序遍歷染色體的工序段，根據當前遍歷的工序進行任務分配和適應度函數的求解。例如，設當前工序段基因序列為

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

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

算法1 染色體解碼及優化偽代碼

輸入 待插入工序p，機器任務隊列MissionQueue

輸出 處理完的機器任務隊列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

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

6)if preProcessFinishTime>=gapBegin do

7)p.Start=preProcessFinishTime

8)else

9)p.Start=gapBegin;

10)end if

∥更新工序的開始和結束時間

∥preProcessFinishTime是p的前置工序結束時間

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

12)insert(m，p)

13)return MissionQueue

14)end if

15)gapBegin=m.End;

16)end for

∥更新工序的開始和結束時間

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

18)enQueue(MissionQueue，p);

19)return MissionQueue

20)END

3.2 算法描述

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

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

輸出 調度方案

1)BEGIN:

2)Initialize:initial population

3)Evaluate population

4)while not reach the termination condition do

5)while not yield enough individual do

∥量子粒子群和精英策略相結合進行個體選擇操作

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

∥機器段：兩點交叉

11)Machine sequence:two-point crossover

12)end if

13)end while

14)if reach mutation condition do

15)update(MR)

∥工序段：兩點交換

16)Procedure sequence:two-point swapping

∥機器段：基于貪心算法選擇變異機器

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

在設置完算法參數之后，接著隨機產生初始種群。初始種群中的每一個個體的工序段基因序列和機器段基因序列都是在編碼的規則下隨機產生的。在個體選擇時加入量子粒子群算法，提升了收斂速度和最終產生的解的質量。算法最終會在達到預設的最大迭代次數時，或者產生預期的解時，終止循環，最后輸出結果。

4 實驗驗證

4.1 實驗設計

本文選用Bradimarte[18]提出的若干個不同測試實例集(Mk01(10*6)、Mk03(15*8)、Mk05(15*4)和Mk08(20*10)等)對提出的混合優化遺傳算法進行實驗驗證。

算法運行環境如表3所示。

表3 運行環境參數

本文測試所選擇的混合優化遺傳算法運行參數如表4所示，表中n為任務數，m為機器數。

表4 算法運行參數

4.2 實驗及結果分析

在最大完工時間的約束條件下，本文采用的混合優化遺傳算法，與GANCE[19]和eGAs[20]同時使用Bradimarte提出的基準測試數據進行測試并比較。

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

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

圖6中，本文所提出的算法與文獻[19]和文獻[20]中的算法在若干個數據集上的運行時間之間的對比。根據數據集的復雜程度，初始種群數在50到300之間，運行次數為5次，最終取平均值作為結果。

圖6 mGAs與其它算法在運行時間上的對比

圖7中，在Mk02、Mk04和Mk06上運行本文算法，從運行結果可以看出在迭代一定次數后，算法可以得到一個較好的近優解。

圖7 mGAs在Mk0等測試集上的對比

圖8 Mk01測試數據運行結果甘特圖

5 結束語

本文在基于傳統遺傳算法解決柔性作業車間調度問題的研究基礎上，使用動態調整交叉和變異概率的方式優化傳統遺傳算法的交叉和變異算子，有效解決了遺傳算法過早收斂的問題；使用量子粒子群優化傳統遺傳算法的選擇算子，使得算法在運行結果上更加可靠。最后，通過在測試集上對本文算法以及其它算法進行對比實驗，證明本文所提出的混合優化遺傳算法可以在更短的時間內獲得一個有效的近優解，并且驗證了該算法的有效性。