柔性作業(yè)車間調(diào)度優(yōu)化的改進遺傳退火算法

（蘭州交通大學(xué) 交通運輸學(xué)院，蘭州 730070）

0 引言

制造業(yè)是國民經(jīng)濟的主體，是立國之本、興國之器、強國之基。隨著《中國制造2025》的提出以及為了加快實現(xiàn)到2025年我國邁入制造強國的戰(zhàn)略目標，制造行業(yè)對于車間的調(diào)度方案優(yōu)化、效率優(yōu)化等研究有著迫切的需求。

車間調(diào)度問題（Job-shop Scheduling Problem，JSP）是制造業(yè)研究的核心和重點。其中柔性作業(yè)車間調(diào)度（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）是JSP問題的延伸和拓展，F(xiàn)JSP突破了資源唯一性的限制，每道工序可以在多臺不同的機器上加工，這樣，F(xiàn)JSP便衍生了兩個子問題，即機器分配問題和工序調(diào)度問題，從而使得其相對于經(jīng)典JSP而言更加復(fù)雜，但同時又使其更加符合實際的生產(chǎn)環(huán)境，因此對它的研究更加具有理論價值和實際應(yīng)用價值。

FJSP是一類滿足任務(wù)配置和順序約束要求的組合優(yōu)化問題，屬于NP難問題[1]。近年來，學(xué)者們相繼提出了一系列啟發(fā)式算法和智能算法，取得了一些成果。如：Brandimarte[2]采用分層的思想，他先采用現(xiàn)有的分派規(guī)則解決路徑子問題，然后再利用禁忌搜索算法解決排序子問題[3]；Xia和Wu[4]運用粒子群算法與模擬退火算法混合求解多目標FJSP問題；Gao J[5,6]將遺傳算法與局部搜索相結(jié)合，并改進了交叉變異算子，提出新的遺傳算法；Pezzella[7]通過集成不同的遺傳策略來產(chǎn)生初始種群，設(shè)計了求解FJSP問題性能更好的遺傳算法。國內(nèi)研究FJSP的文獻也很多；趙良輝[8]、潘全科[9]采用模擬退火算法求解車間調(diào)度問題；吳秀麗[10～12]相繼提出了小生境技術(shù)的混合遺傳算法、免疫遺傳算法、改進的細菌覓食優(yōu)化算法求解FJSP問題；張超勇[13～15]在提出POX交叉算子的前提下，之后又將其改進提出了改進的遺傳算法和改進的非支配排序遺傳算法（NSGA-II）求解FJSP問題；徐新黎[16]、李小濤[17]分別多智能題免疫算法和多智能體遺傳算法求解車間調(diào)度問題；劉愛軍[18]、蔣增強[19]分別提出了基于血緣變異和改進的NSGA-II求解多目標柔性作業(yè)車間調(diào)度問題。由此可知，柔性作業(yè)車間調(diào)度問題是當(dāng)前學(xué)術(shù)界和工業(yè)界關(guān)注的熱點問題。

基于此背景及混合算法能提高單一算法性能的思想，本文在前人研究的基礎(chǔ)上[20～23]，提出了改進的遺傳退火算法（Enhanced Genetic and Simulated Annealing,EGSA），引入了S-自適應(yīng)遺傳算子以及采用非齊次的降溫策略[24,25]，不僅能對交叉和變異概率進行非線性調(diào)整而且還能很好的控制溫度的下降，增強了遺傳算法良好的全局搜索能力和模擬退火算法有效避免陷入局部最優(yōu)的能力。

1 問題模型

1.1 問題的描述

1）每一工序必須一次加工完成，不允許中途中斷（非搶占式調(diào)度）；

2）一臺機器在任何時刻最多只能加工一個產(chǎn)品；

3）一個產(chǎn)品不能同時在兩臺機器上加工；

4）在t=0時刻，所有的工件都可被加工。

1.2 模型的建立

FJSP的調(diào)度目標是找出n個工件所有工序的加工順序，并分配相應(yīng)的機器，使其最大完工時間最小。設(shè)T為調(diào)度方案的最大完工時間Makespan，Cij為工序Oij的完工時間，則數(shù)學(xué)模型為：

其中：1）是目標函數(shù)；2）反映的是工藝約束；3）限定一臺機器同一時間只能加工一個工件；4）限定工序Oij只能在一臺機器上獨立完成，不能跨機器加工；5）和 6）是決策變量。

2 改進遺傳退火算法的FJSP尋優(yōu)

2.1 編碼和解碼

利用遺傳算法對非確定多項式難題（NP）進行優(yōu)化的關(guān)鍵之一就是編碼。FJSP是要解決機器上工件工序的排序問題及機器的分配問題，因此只采用單一的基于工序的編碼、基于工件的編碼、基于析取圖的編碼、基于機器的編碼等[26]難以得到問題的最優(yōu)解。所以本文采用基于工序編碼和基于機器編碼的雙層編碼方式，如圖2所示，此編碼將工序和機器對應(yīng)起來不僅能保證產(chǎn)生可行調(diào)度而且還可以避免死鎖。

圖1 基于工序和機器的雙層編碼

圖1的染色體表示有3個工件共8個工序，在5個設(shè)備上進行加工。其中基于工序的編碼出現(xiàn)的第一個3表示工件3的第1道工序，即O31，再對應(yīng)基于機器的編碼工件3的部分，則O31對應(yīng)機器4，即：同理可得：。解碼時根據(jù)解的前半段工序編碼和后半段工序所對應(yīng)的機器機器編碼依次計算工序的開始和完工時間即可。

2.2 交叉和變異

2.2.1 自適應(yīng)交叉變異算子

在一般的遺傳算法中，交叉概率pC和變異概率pM采用給定的固定值，這將有可能導(dǎo)致在求解較復(fù)雜問題時，當(dāng)種群的適應(yīng)度趨于局部最優(yōu)時，固定的pC和pM難以使算法及時跳出局部最優(yōu)；而對于適應(yīng)度高于種群平均適應(yīng)度的個體，固定的pC和pM又難以保護個體的優(yōu)良基因。因此采用固定的pC和pM在求解復(fù)雜優(yōu)化問題時算法存在早熟及穩(wěn)定性差等缺點。于是，為了提高算法搜索全局最優(yōu)解的能力，中外學(xué)者如：Srinvas[27]、王小平[28]、石山[29]、王萬良[30]等人對自適應(yīng)遺傳算子進行了研究，并取得了很好的成果。因此本文引入了能對交叉和變異概率進行非線性調(diào)整得S-自適應(yīng)交叉變異算子，其表達式如下：

其中：fmax為種群中最大的適應(yīng)度值，favg為每代種群的平均適應(yīng)度值，f′表示交叉的兩個個體中較大的適應(yīng)度值，f是被選擇變異個體的適應(yīng)度值；一般地，k1=k2=1，k3=k4=0.5，c=0.6。

該方法所構(gòu)造的遺傳算子隨種群適應(yīng)度變化而自適應(yīng)調(diào)整交叉變異概率。能對偏離最優(yōu)解的個體自動采用較大的pC和pM，以產(chǎn)生向最優(yōu)解方向移動的新個體，提高搜索速度；對靠近最優(yōu)解的個體自動采用較小的pC和pM，保護個體的優(yōu)良基因，使個體逐漸接近全局最優(yōu)解。

2.2.2 交叉操作

在JSP問題中，常用的交叉策略有JOX、SXX、PPX、SPX、GT、LOX等[31]，研究表明設(shè)計交叉算子最重要的標準是子代對父代優(yōu)良特征的繼承性和子代的可行性。

1）工序的IPOX交叉策略

IPOX交叉策略僅交叉父代工序的加工順序，保留工件中工序分配的機器到子代。設(shè)有父代1和父代2，通過IPOX交叉后產(chǎn)生的子代1和子代2，其交叉步驟如下：

Step1：將工件分成兩個集合JS1和JS2；假定分組結(jié)果為JS1={1,3}，JS2={2}；

Step2：將父代1/父代2中包含在JS1/JS2的工件復(fù)制到子代1/子代2中，同時不改變基因的位置；

Step3：將父代1/父代2中包含在JS1/JS2的工件復(fù)制到子代2/子代1，同時不改變它們的次序，以下是圖解說明。

圖2 工序的IPOX交叉策略

2）機器的交替位置交叉策略

APX是輪流選擇父代1和父代2中的基因，若某一基因在子代出現(xiàn)的次數(shù)超過了在父代出現(xiàn)的次數(shù)，則后續(xù)不再選擇該基因，按以上規(guī)則，直到子代的長度達到父代染色體的長度為止。具體操作如圖3所示。

圖3 機器的APX交叉策略

2.2.3 變異操作

1）工序的改進倒位變異策略

本文改進的倒位變異策略EIVM，其具體操作如下：設(shè)父代染色體的長度為L，則從父代的隨機位置選取長度不超過所選位置到L區(qū)間的子基因串，然后將這個基因串中所有的子基因倒位后再隨機的插入染色體中，得到新的子代。

圖4 工序的EIVM變異策略

2）機器編碼的隨機替換變異策略

由于柔性JSP中每道工序可以有多臺機器進行加工的特點，因此，在機器染色體變異時，在基因串中隨機選擇一個基因，在此基因的機器集合中隨機選擇一個與它不相等的整數(shù)（不同的機器），替換當(dāng)前的基因，這樣可保證的解是可行解。

圖5 機器的RRM變異策略

2.3 降溫規(guī)則

利用模擬退火算法對每個染色體開展局部搜索時，精細的冷卻退火規(guī)則能夠使算法在有限次的迭代過程中逼近問題的最優(yōu)解。本文的溫度下降指定一個有限的非齊次馬爾可夫鏈序列，溫度更新表達式為：

2.4 停止規(guī)則

在整個搜索算法過程中，有兩個終止規(guī)則。第一個是給定的最大的迭代次數(shù)M，另外一個是降溫達到終止溫度tf（即當(dāng)滿足以上要求之一時，終止運算。

2.5 算法步驟

Step1：初始化，給定種群規(guī)模MAXPOP，k=0；初始溫度種群pop(k)；

Step2：如果滿足停止規(guī)則，停止計算；否則，對種群pop(k)中每一個染色體i∈ p op(k)的鄰域中隨機選狀態(tài)按模擬退火中的接受概率：

接受或拒絕j，其中f(i)為狀態(tài)i的目標值；這一階段共需MAXPOP次迭代選出新種群NewPOP1（k+1）；

Step3：在NewPOP1（k+1）中計算適應(yīng)函數(shù)：

其中fmin是NewPOP1（k+1）中的最小值；由適應(yīng)函數(shù)決定的概率分布從NewPOP1（k+1）中隨機選MAXPOP個染色體形成種群NewPOP2（k+1）；

Step4：按遺傳算法的S-自適應(yīng)算子進行IPOX、APX交叉得到CrossPOP（k+1）；再通過EIVM、RRM變異得到MutPOP（k+1）；

3 仿真實驗

本算法使用仿真工具為：Matlab R2016b；運行環(huán)境：Windows 7；處理器：Intel(R) Core(TM) i5-2450M CPU @2.50GHz 4.0GB內(nèi)存。

參數(shù)設(shè)置如下：種群規(guī)模為200，c=0.6，初始溫度t0=100，終止溫度tf=10，溫度可以下降的最大次數(shù)M=1000。

為了驗證EGSA算法的有效性和可行性，本文選取柔性作業(yè)車間調(diào)度Kacem的3個基準問題（8×8、10×10、15×10）進行求解[32]，并與當(dāng)前取得效果比較好的算法進行比較，如：PSO+SA[4]、PSO+TS[33]、LSA[34]等。對這三個基準問題應(yīng)用本文提出的EGSA分別運行10次，得到的統(tǒng)計結(jié)果如表1所示。

由表可知本文的EGSA算法在求解這三個算例時，都能在很短的時間得到最優(yōu)解，并且在8×8、15×10的算例上，表現(xiàn)出更明顯的優(yōu)勢，分別比其他4種、2種算法得到的解更優(yōu)，說明ESGA算法具有高效性和精確性的特點。

圖6 三種算法求解Kacem 15×10算例的收斂曲線對比圖

為了說明算法的性能，本文將15×10的基準問題為算例，將本文提出的EGSA同時算法與傳統(tǒng)的遺傳退火算法GASA、遺傳算法GA進行收斂性能對比，三種算法的收斂曲線圖如圖6所示。由收斂圖可知三種算法都能尋找到最優(yōu)解11小時；EGSA在第76代就開始收斂到最優(yōu)解，GASA大約在第300代開始收斂到最優(yōu)解；而GA收斂速度最慢，迭代到第900代左右才收斂到最優(yōu)，且根據(jù)其目標值在約100代到600代的變化情況，可知其魯棒性稍差。通過對比發(fā)現(xiàn)，混合算法（EGSA、GASA）比單一算法（GA）性能更優(yōu)，魯棒性更好，同時也說明了EGSA算法不僅高效、精度高而且收斂速度快，具有較強的搜索能力，能夠在較短時間與迭代次數(shù)內(nèi)獲取最優(yōu)解。

表1 EGSA求解Kacem算例結(jié)果統(tǒng)計與對比

圖7 Kacem15×10最優(yōu)調(diào)度方案

由上述收斂曲線對比得出的Kacem15×10最優(yōu)調(diào)度方案的甘特圖如圖7所示。由圖可知機器M2、M7、M10從t=0時刻開始直到任務(wù)結(jié)束，一直處于工作狀態(tài)。若定義：機器負荷=工作時間/最大完工時間，則這三臺機器的工作負荷均為100%，表明這三臺機器工作強度很高，所以企業(yè)應(yīng)該加強對這幾臺機器的日常保養(yǎng)和維護工作。

4 結(jié)論

柔性作業(yè)車間調(diào)度是實施生產(chǎn)計劃的重要環(huán)節(jié)，本文建立了以最小化最大完工時間為優(yōu)化目標的FJSP模型，提出了一種改進的遺傳退火算法。為了克服傳統(tǒng)算法采用的固定交叉變異概率和固定溫度衰減系數(shù)帶來的易早熟、穩(wěn)定性差等缺點，于是引進了S-自適應(yīng)算子和非齊次的降溫規(guī)則對算法進行改進。最后使用MATLAB工具將算法對Kacem基準算例進行了測試，也與傳統(tǒng)算法進行了收斂性對比，結(jié)果表明本文提出的算法具有較好的可行性、高效性、精確性、魯棒性，并提出企業(yè)在實際管理中應(yīng)該注意的問題。

由于作者水平有限，只是研究了單目標的FJSP問題，并沒有研究多目標的FJSP問題，在實際中生產(chǎn)中，制造商不僅要考慮最大完工時間，而且還需要考慮設(shè)備負荷、加工成本、能耗、客戶滿意度等綜合因素，因此多目標的FJSP問題將是下一步研究的重點內(nèi)容。