改進(jìn)遺傳算法求解帶不相關(guān)并行機(jī)的HFSP

王靜云，王 雷，李佳路

（安徽工程大學(xué)機(jī)械工程學(xué)院，安徽，蕪湖 241000）

0 引言

車間調(diào)度是典型的NP-hard 問題，混合流水車間調(diào)度問題（Hybrid flow shop scheduling problem,HFSP）是車間調(diào)度中常見的調(diào)度類型，是傳統(tǒng)的流水線生產(chǎn)與并行機(jī)調(diào)度的綜合。目前，混合流水車間調(diào)度廣泛存在于化工、冶金、紡織、機(jī)械、裝配、運(yùn)輸?shù)刃袠I(yè)中[1]。

近年來，越來越多的智能優(yōu)化算法應(yīng)用于HFSP。張?jiān)吹仍趥鹘y(tǒng)的差分算法上結(jié)合了反向?qū)W習(xí)策略生成初始種群，添加自適應(yīng)差分因子，并在個(gè)體選擇時(shí)引入Metropolis 準(zhǔn)則[2]；Zhou 等人運(yùn)用帶分布估計(jì)的混合差分進(jìn)化算法，求解了一種可重入混合流水車間調(diào)度問題[3]；Mageed 和Ibrahim 研究了無等待的兩階段問題，采用PSO 算法優(yōu)化了總延遲時(shí)間[4]；Meng 等人針對不相關(guān)并行機(jī)的節(jié)能混合流水車間調(diào)度問題，提出了改進(jìn)的遺傳算法，通過對比模擬退火算法和遷徙鳥類優(yōu)化算法，證明了其改進(jìn)的遺傳算法的有效性[5]；羅函明等針對布谷鳥算法常規(guī)解碼方法難以獲得最優(yōu)解的缺點(diǎn)，提出一種改進(jìn)的解碼方法，通過對比原始規(guī)則解碼、隨機(jī)規(guī)則解碼、改進(jìn)規(guī)則解碼所得結(jié)果，驗(yàn)證其有效性[6]；Mousavi 等人提出了一種基于遺傳算法的近似求解方法，求解了最大完成時(shí)間和總拖延時(shí)間最小化的雙目標(biāo)問題[7]；杜利珍等提出了基于權(quán)重的編碼方式的果蠅優(yōu)化算法，來求解混合流水車間調(diào)度問題，并通過與經(jīng)典算法進(jìn)行對比驗(yàn)證了其算法的有效性[8]；宋存利采用正序解碼和逆序解碼，提出貪婪交叉算子變異算子，增加了種群的多樣性，提高了遺傳算法在求解HFSP 時(shí)的局部搜索能力[9]；軒華等人研究了可重入多階段混合流水車間調(diào)度問題，以最小化最大完工時(shí)間為目標(biāo)建立數(shù)學(xué)模型。在GA 的基礎(chǔ)上，結(jié)合NEH 啟發(fā)式算法產(chǎn)生工件初始加工順序，使得遺傳參數(shù)隨進(jìn)化代數(shù)和個(gè)體適應(yīng)函數(shù)值兩個(gè)方面進(jìn)行自適應(yīng)調(diào)節(jié)[10]。

已有的研究表明，GA 算法在求解HFSP 時(shí)全局搜索能力較好，但易陷入局部極值。針對此問題，本研究針對最小化最大完工時(shí)間為目標(biāo)的不相關(guān)并行機(jī)混合流水車間調(diào)度問題進(jìn)行研究。首先建立了不相關(guān)并行機(jī)混合流水車間調(diào)度問題的數(shù)學(xué)模型，然后提出了改進(jìn)的遺傳算法進(jìn)行求解。為彌補(bǔ)遺傳算法的迭代后期容易陷入局部搜索的缺陷，在傳統(tǒng)遺傳算法的基礎(chǔ)上利用改進(jìn)的自適應(yīng)交叉和變異概率因子及模擬退火局部搜索策略，增強(qiáng)遺傳算法在迭代后期跳出局部最優(yōu)的能力。通過兩個(gè)案例來驗(yàn)證改進(jìn)遺傳算法的有效性。

1 不相關(guān)并行機(jī)HFSP 問題描述

不相關(guān)并行機(jī)HFSP 可以描述為：n個(gè)工件經(jīng)過m道工序的加工，所有的工件有著相同的加工路徑，存在一道或多道工序有并行機(jī)，如圖1 所示。HFSP 需要解決的問題就是確定每個(gè)工件在哪一臺機(jī)器上加工，使得某一個(gè)或多個(gè)指標(biāo)最優(yōu)。

圖1 混合流水車間結(jié)構(gòu)Fig.1 Hybrid flow shop structure

另外，還有如下假設(shè)：

1）每一臺機(jī)器只能加工一件工件，每個(gè)工件每道工序只在一臺機(jī)器上加工；

2）工件一旦加工，就不能中斷，直到完工；

3）不考慮工件之間的運(yùn)輸時(shí)間和準(zhǔn)備時(shí)間；

4）所有工件的到達(dá)時(shí)間都為0；

5）相鄰兩道工序有無限的緩沖儲存區(qū)。

不相關(guān)并行機(jī)HFSP有n個(gè)工件經(jīng)過m道工序；工件編號為i（i=1,2,…,n）；工序的編號為j（j=1,2,…,m）；Mj為工序j 的并行機(jī)數(shù)量；Ci為工件i 的完工時(shí)間；Pijk為工件i在工序j的第k臺機(jī)器上加工時(shí)間；Sijk為工件i在工序j的第k臺機(jī)器上加工的開始時(shí)間；Eijk為工件i 在工序j的第k臺機(jī)器上加工的完工時(shí)間；Xil為0-1 的變量，表示工件i 被安排在第l 個(gè)位置進(jìn)行加工；Yijk為0-1 的變量，表示工件i在工序j的第k臺機(jī)器上進(jìn)行加工。

本研究優(yōu)化的目標(biāo)是最小完工時(shí)間，即n個(gè)工件完工時(shí)間的最小值，根據(jù)以上的問題描述，目標(biāo)函數(shù)為最小化完工時(shí)間：

式（1）表示目標(biāo)函數(shù)最大完工時(shí)間；式（2）表示工件在完成前一道工序才能開始下一道工序的加工；式（3）表示在同一道工序工件的加工完工時(shí)間的計(jì)算公式；式（4）、（5）表示至少有一道工序有并行機(jī)；式（6）、（7）表示工件的排序位置約束；式（8）表示工件在每一道工序只能在該工序的一臺機(jī)器上進(jìn)行加工。

2 改進(jìn)遺傳算法求解

遺傳算法求解做和優(yōu)化問題能獲得較好的優(yōu)化結(jié)果，但遺傳算法在迭代后期容易陷入局部最優(yōu)，本研究應(yīng)用改進(jìn)的遺傳算法對HFSP 進(jìn)行研究。改進(jìn)后的遺傳算法的流程圖如圖2 所示。

圖2 改進(jìn)的遺傳算法流程圖Fig.2 Improved genetic algorithm flowchart

2.1 編碼方式

假設(shè)要加工n個(gè)工件，每一個(gè)工件要經(jīng)過m道工序， 每一道工序的并行機(jī)數(shù)量為Mj（Mj>1,j=1,2,…,m）。構(gòu)造一個(gè)n×m的編碼矩陣：

矩陣元素aij是在區(qū)間（1，Mj+1）上隨機(jī)產(chǎn)生的一個(gè)實(shí)數(shù)，其中實(shí)數(shù)部分表示工件i在工序j的第[aij]臺的機(jī)器上進(jìn)行加工，[]表示向下取整；小數(shù)部分表示工件i在工序j的第[aij]臺的機(jī)器的加工順序，數(shù)值較大優(yōu)先加工。

2.2 初始種群和適應(yīng)度函數(shù)

初始種群的規(guī)模為popsize，本文采用產(chǎn)生隨機(jī)數(shù)的方式來產(chǎn)生初始解。本研究的混合流水車間調(diào)度問題以最大完工時(shí)間Cmax為研究問題的目標(biāo)，故選擇完工時(shí)間的倒數(shù)為適應(yīng)度函數(shù)，即f（i）=1/Cmax。

2.3 遺傳操作

2.3.1 選擇

通過采用二元錦標(biāo)賽選擇法，從初始種群中隨機(jī)選出兩個(gè)個(gè)體，計(jì)算兩個(gè)個(gè)體的適應(yīng)度值，將適應(yīng)度最優(yōu)的個(gè)體放入下一代種群集合中。重復(fù)該操作，直到新的種群規(guī)模達(dá)到了原先的種群規(guī)模。

2.3.2 自適應(yīng)交叉

交叉算子對種群進(jìn)行迭代尋優(yōu)，pc的大小決定了種群尋優(yōu)的速度快慢，其值過大，會破壞原先較優(yōu)解，其值過小，會導(dǎo)致算法的搜索速度緩慢，種群多樣性較差。在種群進(jìn)化的前期，應(yīng)該盡可能擴(kuò)大搜索的范圍，增加種群的多樣性，pc的取值應(yīng)較大；在種群進(jìn)化的后期，為了使得較優(yōu)解保留下來，pc的取值應(yīng)較小[11]?；谝陨系姆治?，本文設(shè)置如下的交叉概率公式：

變異操作使得種群保持多樣性，避免陷入局部最優(yōu)，但pm的值過大，遺傳算法便近似于隨機(jī)搜索，種群尋優(yōu)性差[11]?；谝陨系姆治?，設(shè)置如下的變異概率公式：

其中pmi為個(gè)體i的變異概率，pmmax為最大交叉概率，pmmin為最小交叉概率。本文選用多點(diǎn)變異，隨機(jī)產(chǎn)生多個(gè)變異位置，當(dāng)滿足變異條件時(shí)，將變異位置的基因用區(qū)間（1，Mj+1）的隨機(jī)數(shù)代替。

2.4 精英保留策略

為防止每一代遺傳操作導(dǎo)致上一代最優(yōu)解的流失或破壞，在進(jìn)行選擇操作時(shí)，采取精英保留策略，將上一代經(jīng)過遺傳操作的種群個(gè)體進(jìn)行適應(yīng)度值排序，取出適應(yīng)度值高的個(gè)體，用保留下來的適應(yīng)度值高個(gè)體代替經(jīng)過遺傳操作后的適應(yīng)度低的個(gè)體，使得精英個(gè)體得以保留延續(xù)。

2.5 模擬退火局部搜索

模擬退火算法的Metropolis 準(zhǔn)則具有以一定的概率接受差解，能很好地彌補(bǔ)遺傳算法在迭代后期容易陷入局部最優(yōu)的缺點(diǎn)。引入以下的概率公式接受新解[12]：

Step1：設(shè)置初始參數(shù)，初始溫度T，終止溫度T-stop，溫度下降系數(shù)α,迭代次數(shù)it，迭代次數(shù)上限為I。

Step2：在除去精英保留策略的解集中依次取解x0, 在x0的鄰域內(nèi)隨機(jī)搜索一個(gè)新解x’，如果f（x’）＞f（x0），則接受新解，用x’代替x0，轉(zhuǎn)至step5；否則下一步。

Step3：生成一個(gè)0-1 的隨機(jī)數(shù)rand，按照模擬退火接收差解概率公式得到p，如果p＞rand，則接受差解，否則不接受差解。it++。

Step4：若it 小于I，轉(zhuǎn)至step2，否則下一步。

Step5：更新溫度，若溫度達(dá)到終止溫度，終止。否則轉(zhuǎn)至step2。

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

3.1 仿真案例1

將結(jié)合遺傳自適應(yīng)調(diào)節(jié)和模擬退火局部搜索的GA 記為LZGA，添加遺傳自適應(yīng)調(diào)節(jié)的GA 記為AGA，為測試本文算法的性能，將LZGA 與AGA和傳統(tǒng)GA 進(jìn)行對比。我們應(yīng)用MATLAB 2016a 對HFSP 進(jìn)行案例分析，6 個(gè)工件，經(jīng)過4 道工序，三道工序機(jī)器數(shù)量分別為3 臺、3 臺、3 臺，工件在各臺機(jī)器上的加工時(shí)間如表1 所示。種群大小均設(shè)置為50，迭代次數(shù)均設(shè)置為200。應(yīng)用軟件進(jìn)行10次仿真實(shí)驗(yàn)，對比所得的實(shí)驗(yàn)數(shù)據(jù)，結(jié)果如表2 所示，迭代圖如圖3 所示。

圖3 收斂曲線對比圖Fig.3 Convergence graph for comparison

表1 案例1 工件加工時(shí)間表Table 1 Workpiece processing information for Case 1

表2 案例1 結(jié)果對比Table2 Comparison of results for Case 1

圖4 LZGA 求解案例1 調(diào)度甘特圖Fig.4 Scheduling Gantt chart on case 1 by using LZGA

由表2 和圖3 可以看出，GA 算法未能找到最優(yōu)解，陷入局部極值未能跳出局部最優(yōu)；AGA 算法3 次找到了最優(yōu)解，但其在前期易陷入局部極值，在迭代中后期才跳出；而LZGA 算法10 次均找到了最優(yōu)解且在迭代前期就能很快地跳出局部極值。因此在10 次的仿真實(shí)驗(yàn)中，LZGA 的尋優(yōu)性最好。

3.2 仿真案例2

以文獻(xiàn)[13]中的發(fā)動機(jī)加工車間為例，6 個(gè)工件經(jīng)過3 道工序的加工，三道工序機(jī)器數(shù)量分別為2臺、3 臺、3 臺，工件在各臺機(jī)器上的加工時(shí)間如表3 所示。以本研究的改進(jìn)遺傳算法求解此案例，設(shè)置種群大小為50，最大迭代次數(shù)為200，初始溫度為1000，終止溫度為10，降溫系數(shù)為0.97，最小交叉概率為0.7，最大變異概率為0.05。

表3 案例2 產(chǎn)品工序加工時(shí)間表Table 3 Workpiece processing information for Case 2

通過10 次實(shí)驗(yàn)仿真，對比文獻(xiàn)算法和本研究算法所得到的結(jié)果數(shù)據(jù)，如表4 所示。由表4 可以看出，我們算法的方差為0.11，穩(wěn)定性良好，10 次的結(jié)果均優(yōu)于文獻(xiàn)結(jié)果，進(jìn)一步表明本文算法的有效性和魯棒性。本研究算法求得此實(shí)例的最優(yōu)解調(diào)度甘特圖如圖5 所示。

表4 案例2 結(jié)果對比Table 4 Comparison of results for Case 2

圖5 LZGA 求解案例2 調(diào)度甘特圖Fig.5 Scheduling Gantt chart on case 2 by using LZGA

4 結(jié)論

我們研究了不相關(guān)并行機(jī)混合流水車間調(diào)度問題，目標(biāo)是最小化最大完工時(shí)間。針對遺傳算法在迭代后期易陷入局部最優(yōu)的缺陷，在遺傳算法的交叉和變異操作中增加了自適應(yīng)調(diào)節(jié)，在遺傳操作后添加局部搜索策略，并用模擬退火的Metropolis準(zhǔn)則接受差解。對比案例仿真結(jié)果表明：改進(jìn)后的遺傳算法更容易找到最優(yōu)解，且不容易陷入局部最優(yōu)，具有良好的魯棒性和穩(wěn)定性。