一種求解FJSP的混合遺傳算法

賈培豪,毋 濤

(西安工程大學 計算機科學學院,陜西 西安 710048)

0 引 言

在傳統的作業車間調度問題(job-shop scheduling problem,JSP)中,一道工序只存在一臺加工機器,但在企業實際車間生產過程中往往會出現并行機器的現象,導致傳統的作業車間調度不能很好地滿足企業實際需求,由此,柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)便應運而生[1]。FJSP是JSP的一種擴展,相較于JSP而言更為靈活,在規定工序的同時,還需對每道工序分配加工機器,是復雜的NP問題。正是由于FJSP具有較高的應對復雜性問題的能力和解的靈活性,所以更符合車間生產的實際需求,因此成為了車間調度領域的重點研究方向[2]。

近年來,人們對于此類問題的求解，主要采用智能算法作為解決手段。CHAUDHRY等對1990—2014年期間發表的191篇關于求解柔性作業車間調度問題的論文進行了調查分析,發現34%的論文都是通過遺傳算法或混合遺傳算法來求解FJSP[3]。由此可知,遺傳算法已經是解決FJSP的主流方法,但遺傳算法在實際應用過程中往往容易陷入局部最優陷阱[4]。對此,張超勇等針對FJSP問題的特點提出了一種基于雙層編碼的交叉及變異算子,使得子代能更好地繼承父代的優良特征,提高了遺傳算法求解FJSP的解的質量[5];ISHIKAWA等提出了一種名為多層次空間競爭性分布式遺傳算法(hierarchical multi-space competitive distributed genetic algorithm,HmcDGA)的算法求解FJSP,該算法雖然具有競爭優勢,但是計算成本較高[6];LI等提出一種將禁忌搜索算法局部搜索能力強的特點與遺傳算法全局搜索能力強的特點有效結合的禁忌混合遺傳算法求解FJSP,以此增強遺傳算法局部搜索能力[7];楊振泰等改進傳統的Powell搜索法,提出了一種融合Powell搜索法的改進遺傳算法,改善了遺傳算法在進化過程中產生不可行解的情況[8]。

綜上所述,改進標準遺傳算法亦或通過融合其他算法優化標準遺傳算法是求解FJSP的研究趨勢。本文提出一種鯨魚群混合遺傳算法。在遺傳算法的基礎之上,通過將鯨魚群算法計算出的鯨魚個體與遺傳算法得到的染色體相比較,替換掉原有遺傳算法中適應度較低的染色體個體,實現鯨魚群算法不斷向遺傳算法輸送新鮮血液的目標,以此提高遺傳算法求解質量與穩定性。

1 FJSP概述

1.1 問題描述

假設生產車間有待加工工件{J1，J2，…，Jn},有可用機器{M1,M2,…,Mm},其中每個工件包含多道加工工序,每道工序存在至少一臺機器可供加工選擇,且不同機器加工同一工件的耗時也不盡相同。因此,任一工件選擇不同機器進行加工所得到的調度總時長也會有所不同。那么，如何為工件合理的指派加工機器，從而使得加工總時長最短即為問題的求解目標。

1.2 數學模型

柔性作業車間調度問題需滿足如下約束:

1) 工件加工工藝鎖定,即每個工件加工的順序不得改變,前一道工序的加工必須在后一道工序加工開始之前完成;

2) 在任何一個時間節點上,一臺機器只允許加工一個工件;

3) 同一時刻,同一工件的同一道工序只能被一臺機器所加工;

4) 加工過程視作一種理想化的情景,即不考慮外部環境的影響,且加工一旦開始便不可中斷;

5) 所有的工件都須在0時刻開始加工。

結合文獻[9],現給出柔性作業車間調度問題的數學模型。為了方便介紹,首先定義說明相關的數學符號,如表1所示。

問題的優化目標為“最大完工時間”,即工件生產調度所需的最大完工時間最小,目標函數(Fg)為

Fg=min max(Cj),1≤j≤n

(1)

式(1)擁有如下約束:

Sjh+Pijh≤Skl+α(1-yijhkl)

(2)

式中：j=0,1,…,n;k=1,2,…,n;h=1,2,…,hj;l=1,2,…,hk;i=1,2,…,m。

Cjh≤Sj(h+1)+α(1-yiklj(h+1))

(3)

式中：j=1,2,…,n;k=0,1,…,n;h=1,2,…,hj-1;l=1,2,…,hk;i=1,2,…,m。

表 1 數學符號及其定義Tab.1 Mathematical symbols and definitions

Cmax≥Cjhj,j=1,2,…,n

(4)

Sjh+xijhPijh≤Cjh。i=1,2,…,m;

j=1,2,…,n;h=1,2,…,hj

(5)

Cjh≤Sj(h+1)。j=1,2,…,n;

h=1,2,…hj-1

(6)

(7)

Sjh≥0,Cjh≥0

(8)

式(2)和式(3)表示了在任何1個時間節點上,1臺機器只允許加工1個工件;式(4)、式(5)和式(6)表示了加工的總時間大于任意工件完工時間且每個工件加工的順序不得改變,前一道工序的加工必須在后一道工序加工開始之前完成;式(7)表示任何1個工件的任意一道工序都只能選擇1臺機器進行加工;式(8)表示所有的工件都需要在0時刻才能開始加工。

2 算法設計

2.1 遺傳算法

2.1.1 染色體編碼 采用雙層編碼方式進行染色體編碼工作,即對工序以及機器指派分別編碼[10]。第一層為工序編碼。首先構造數列S,假設有Ji個工件需要加工,那么每一個工件均包含PJi道工序。數列S的長度為l,且l=PJ1+PJ2+…+PJi；數列S的基因S[t]∈[1,l],且S[t]不重復。與此同時,再構造數列C,數列C包含PJ1個1,PJ2個2,PJ3個3,以此類推得出數列C。根據數列S對數列C重排序,得到一個新的數列SC，即為工序編碼。第二層為機器指派編碼。同樣構造一個數列M,數列M的長度與數列SC長度相同,數列M的基因為與之索引相對應的工序加工采用第幾個可用機器。

例如,有2個工件J1和J2需要加工,共有3臺機器可供選擇,其中J1包含2道工序,J2包含4道工序,那么PJ1=2,PJ2=4,l=PJ1+PJ2=6。有3臺機器可供選擇且M的長度等于6,則該問題下一個合格的染色體可以表示為“3,4,1,5,2,6,1,2,2,1,2,3”,其中數列S={3,4,1,5,2,6},生成的數列C={1,1,2,2,2,2}。根據數列S對數列C進行重排序得到數列SC={2,2,1,2,1,2},其中數列SC中索引為0的數字2表示零件2的第1道加工工序,索引為1的2表示零件2的第2道加工工序,以此類推。數列M={1,2,2,1,2,3},其中索引為0的數字1表示零件1的第1道加工工序選用它可用機器的第1個進行加工,索引為1的數字2表示零件1的第2道加工工序選用它可用機器的第2個進行加工,以此類推。

2.1.2 適應度函數 優化目標為“最大完工時間”,即完成加工所需的總時間越短則個體適應度越好,適應度函數Ff表示為目標函數的倒數形式,即

Ff=1/Fg

(9)

2.1.3 選擇操作 選用輪盤賭選擇法[11],即種群N中個體i的適應度為Fi,則個體被選擇遺傳到子代的概率為

(10)

從式(10)可以看出,個體選中的概率與適應度函數成正比。

2.1.4 交叉操作 對雙層遺傳算子均采用兩點交叉的方式進行。即隨機選擇2個染色體作為父代染色體,并在染色體長度范圍之內隨機產生2個大于等于0的數字作為索引,然后交換2個索引之間的基因片段,隨即得到2個子代染色體;判斷得到的子代染色體是否符合編碼規范,若不符合則需對其進行修補,修補方式為取交叉片段的補集隨機重排列到非交叉片段。例如,產生隨機數rand(1)=1,rand(2)=3,若2條父代染色體分別為“1,3,2,5,4,6”和“1,2,4,5,3,6”,則交叉片段為索引1到索引3的值,即“3,2,5”和“2,4,5”；進行基因片段互換,得到兩條子代染色體為“1,2,4,5,4,6”和“1,3,2,5,3,6”。可以看出，染色體交叉后不符合規范,因此對其進行修補。按照上述方法修補后的兩條染色體分別為“1,2,4,5,3,6”和“1,3,2,5,4,6”,至此完成交叉操作。

2.1.5 變異操作 由于文中采用雙層編碼的方式,因此染色體變異操作也是分雙層進行。對于第一層遺傳算子的變異操作采用兩點變異,即在染色體長度范圍之內隨機產生2個大于等于0的數字作為索引,然后交換這2個索引所對應的基因的值。例 如,產生隨機數rand(1)=2,rand(2)=3,一條染色體為“1,3,4,6,5,2”,則交換索引為2和索引為3的值,即得到新的染色體“1,3,6,4,5,2”。對于第2層遺傳算子的變異操作則采用單點變異,即同樣產生一個隨機數作為索引,然后對該索引所對應的基因進行變異,變異范圍為該道工序可用機器數。例如,產生隨機數rand(1)=1，一個染色體為“1,2,2,1,2,3”,則變異后的染色體為“1,3,2,1,2,3”。

2.2 鯨魚群算法部分

2.2.1 算法概述 鯨魚群算法(whale swarm optimization algorithm,WSA)是2017年誕生的一種新型啟發式算法,由華中科技大學的ZENG等受鯨魚通過聲音交流尋找獵物的行為啟發所提出[12]。所有的鯨魚都通過超聲波進行交流,不同距離的超聲波強度(ρ)[13]為

ρ=ρ0exp(-ηd)

(11)

式中：d為距離；η是超聲波傳播的衰減系數；ρ0為超聲波強度。當η不變時,ρ隨著d的增加呈現下降趨勢,即隨著距離的增大,超聲波的強度會降低。當2條鯨魚間距離較遠時,無法確定所發出的獵物信息是否正確,因此鯨魚總是會積極地向著“較好且最近的”鯨魚移動,反之亦然。正是因為每條鯨魚都是向著“較好且最近的”鯨魚進行移動,在經過一段時間鯨魚的運動后,就會產生一些鯨魚群。受這種鯨魚尋找食物的啟發,文獻[12]建立了如下算法迭代方程，即

(12)

2.2.2 鯨魚個體距離 鯨魚群算法編碼方式同樣是采用基于機器和工序的雙層編碼方式。但是,由于鯨魚群算法在提出時是用于解決連續性問題的,而基于雙層編碼求解FJSP屬于離散問題,所以導致鯨魚個體間距離計算方式以及鯨魚移動規則均無法直接使用。由此,本文引入文獻[14]所提出的鯨魚個體距離計算方法及移動規則,以2.1.1節中的編碼為例進行說明。一個完整的編碼為{1,2,2,1,2,3,2,2,1,2,1,2},若Pos表示鯨魚個體在解空間的位置，則基于Pos向量的鯨魚個體表示如圖1所示。

圖 1 鯨魚個體表示Fig.1 Individual whale representation

由圖1可得,由機器編碼得到Pos中的機器號,由工序編碼在對應機器上的加工順序得到Pos中的Seq值，其中Seq表示工序在所選機器上的加工次序。機器號和Seq值等2部分共同組成了Pos向量,即鯨魚個體在解空間當中的位置表示。用Pos向量表示法計算鯨魚個體間距離(Dis),即

(13)

2.2.3 鯨魚個體移動 計算出鯨魚個體間距離后,由“最優且最近”的引導鯨魚引導其移動。鯨魚個體移動步驟如下:

1) 以總工序數作為長度,隨機生成一組由0和1組成的數組;

2) 保留數組中1所對應的鯨魚個體工序及機器編碼,復制到新鯨魚個體中;

3) 對數組中0所對應的工序建立集合,在引導鯨魚個體中尋找集合中對應工序以及機器編碼,將其按照引導鯨魚個體中的順序依次填充新鯨魚個體中的空缺部分。

完成鯨魚個體的移動之后，形成新的鯨魚個體。鯨魚個體移動規則如圖2所示。

圖 2 鯨魚個體移動規則Fig.2 Movement rules of individual whale

將移動后得到的鯨魚個體與遺傳算法得到的染色體相比較,替換掉原有遺傳算法中適應度較低的染色體個體,實現鯨魚群算法不斷向遺傳算法輸送新鮮血液的目標。

2.3 鯨魚群混合遺傳算法執行流程

所提出的鯨魚群混合遺傳算法(WSA-GA)是在遺傳算法的基礎之上,通過將鯨魚群算法計算出的鯨魚個體與遺傳算法得到的染色體進行重組,從而改進了遺傳算法。鯨魚群混合遺傳算法執行流程如圖3所示。

圖 3 鯨魚群混合遺傳算法流程圖Fig.3 Flow chart of whale swarm hybrid genetic algorithm

3 實驗與結果分析

3.1 環境與算法參數

實驗環境為Window 10系統,內存16 G,處理器四核I5-7300HQ 2.5 GHz,實驗工具為MatlabR2016a。算法參數設置如下:種群規模=200,算法迭代次數=200,變異概率pm=0.1,交叉概率pc=0.7。

3.2 算例驗證

為了驗證WSA-GA算法的有效性,通過Kacem基準算例[15-16]對算法進行驗證。對4×5,8×8,10×7,10×10以及15×10等5種規模的算例分別進行仿真實驗,將5種算例分別執行20次,記錄最優結果以及20次實驗結果平均值。將本文所提出的WSA-GA算法與文獻[17-22]中的算法結果相對比,并對比傳統遺傳求解結果,對比結果如表2所示。

表 2 Kacem算例對比結果Tab.2 Results of Kacem example comparison

選取Kacem 8×8和15×10等2種規模算例,將鯨魚群混合遺傳算法調度結果通過甘特圖進行展示,如圖4、圖5所示。

圖 4 Kacem 8×8算例調度結果甘特圖Fig.4 Gantt chart of Kacem 8×8 example scheduling result

圖 5 Kacem 15×10算例調度結果甘特圖Fig.5 Gantt chart of Kacem 15×10 example scheduling result

本算法旨在用于實際工業生產,因此求解穩定性與最優結果為算法主要目標。由表2可以看出,所提出的WSA-GA算法在對Kacem 5種規模算例的驗證中均能獲得最優值且結果較為穩定,相較于傳統遺傳算法求解結果均有了明顯提升,一定程度上驗證了算法的有效性與可行性。

4 結 語

針對遺傳算法求解FJSP容易陷入局部最優陷阱的問題,提出了一種鯨魚群混合遺傳算法。通過將鯨魚群算法的鯨魚個體與遺傳算法的染色體進行編碼重組,有效地解決了遺傳算法“早熟”的問題。仿真實驗證明了WSA-GA算法求解FJSP的有效性與可行性,對于解決實際生產調度問題具有一定價值。本文所研究的是單目標的FJSP問題,后續將考慮利用鯨魚群混合遺傳算法解決多目標FJSP問題。