王靜云，王 雷，李佳路

（安徽工程大學機械工程學院，安徽，蕪湖 241000）

0 引言

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

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

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

1 不相關并行機HFSP 問題描述

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

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

另外，還有如下假設：

1）每一臺機器只能加工一件工件，每個工件每道工序只在一臺機器上加工；

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

3）不考慮工件之間的運輸時間和準備時間；

4）所有工件的到達時間都為0；

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

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

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

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

2 改進遺傳算法求解

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

圖2 改進的遺傳算法流程圖Fig.2 Improved genetic algorithm flowchart

2.1 編碼方式

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

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

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

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

2.3 遺傳操作

2.3.1 選擇

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

2.3.2 自適應交叉

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

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

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

2.4 精英保留策略

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

2.5 模擬退火局部搜索

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

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

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

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

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

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

3 仿真實驗及結(jié)果分析

3.1 仿真案例1

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

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

表1 案例1 工件加工時間表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 次的仿真實驗中，LZGA 的尋優(yōu)性最好。

3.2 仿真案例2

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

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

通過10 次實驗仿真，對比文獻算法和本研究算法所得到的結(jié)果數(shù)據(jù)，如表4 所示。由表4 可以看出，我們算法的方差為0.11，穩(wěn)定性良好，10 次的結(jié)果均優(yōu)于文獻結(jié)果，進一步表明本文算法的有效性和魯棒性。本研究算法求得此實例的最優(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é)論

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