基于改進遺傳算法的作業(yè)車間調度

王 明，蔡勁草，王 雷

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

0．引言

作業(yè)車間調度(Job shop scheduling problem,JSP)是車間調度中最常見的調度類型，是最難的組合優(yōu)化問題之一，對其研究具有重大的現(xiàn)實意義[1]?？茖W有效的生產調度不但可以提高生產加工過程中工人、設備資源的高效利用，還可縮短生產周期，降低生產成本[2]。隨著遺傳算法在組合優(yōu)化問題的廣泛應用，許多人開始對遺傳算法進行深度研究。已有研究結果[3-6]表明，遺傳算法對求解作業(yè)車間調度問題具有較好的效果。然而，由于傳統(tǒng)遺傳算法存在運行時間過長、易早熟收斂的缺點，許多學者在縮短運行時間、避免早熟收斂、保持種群多樣性方面對遺傳算法進行了改進研究，且都取得了較好的成果[7]。文獻 [8]為了解決柔性作業(yè)車間調度問題中權重難以確定導致調度效率低的缺點，提出了一種改進的動態(tài)隨機搜索遺傳算法；張超勇等[9]人利用基于改進非支配排序遺傳算法求解多目標柔性作業(yè)車間調度問題；文獻[10]利用混合遺傳禁忌搜索算法對柔性作業(yè)車間調度進行了研究。

本文試圖利用改進遺傳算法解決作業(yè)車間調度問題，并以完工時間為目標函數，通過實驗結果驗證了其有效性和可行性。

1．作業(yè)車間調度模型

JSP可簡述為有n個工件需要在m臺設備上進行加工，每個工件包含m個工序。工件在其被加工過程中需滿足：（1）任一時刻的設備只能加工一個工件的某道工序，且每個工件同一時刻只能被一臺設備加工；（2）一旦開始加工，工序中途不能被打斷；（3）每個工件在同一臺設備上最多加工一次；（4）每個工件必須遵守給定的工藝路線約束進行加工；（5）不考慮工件的運輸、裝夾等輔助時間。

本文以工件的最短完工時間為目標，建立目標函數（1）為：

式(1)中，Cik表示工件i在機器k上的完工時間。

2．改進遺傳算法求解作業(yè)車間調度問題

2．1．編碼與解碼

作業(yè)車間調度編碼的方法很多，但由于基于工序的編碼具有編碼和解碼方案簡單、柔性高、容易實現(xiàn)等特點[11]，所以在此選用基于工序的編碼與解碼。該問題的加工時間和工藝約束如表1所示。

工件J1、J2和J3分別用數字1、2和3表示，假設它的一個染色體表示為[213123312]，其中染色體中的數字即表示工件也表示工序，其中從左到右第n次出現(xiàn)的該數字的次數表示該工件的第n道工序，如數字1在染色體中從左到右出現(xiàn)三次，則第一個數字1表示工件J1的第1道工序，第二個數字1表示工件J1的第2道工序，第三個數字1表示工件J1的第3道工序，其它含義相同。圖1所示的是編碼及其對應的解碼過程。最后得到加工甘特圖，如圖2所示，總完工時間C=12。

表1 加工時間和工藝約束Tab.1 Processing time and process constraints

圖1 基于工序編碼的解碼方式Fig.1 method of decoding operation-basedcoding

2．2．遺傳操作設計

2．2．1．選擇

復制的作用是將父代個體的信息傳遞給子代，而這種傳遞是有選擇的，父代中的每一個染色體，根據其適應度的大小決定它能夠被選擇復制到子代的幾率。通過選擇，使得群體中的優(yōu)秀個體數目逐漸得到增加，整個優(yōu)化過程朝著更好的方向進化，反映了優(yōu)勝劣汰的基本原則[12]。根據適應度函數決定第i個父代個體被復制到子代個體數量為：

式（2）中，N是種群的規(guī)模；gi是父代中第i個體的適應度值(在此取式(1)的倒數為適應度函數)。所以，個體的適應度值如果越大的話，其被進化到下一代的數目也就會更多。

在選擇的過程中，為了使得最優(yōu)的個體能夠順利地進化到下一代，將每一代中最優(yōu)前10%的精英個體直接進化到下一代。

圖2 解碼獲得的調度結果Fig.2 Scheduling results obtained by decoding

2．2．2．交叉

為了進一步擴大算法的搜索空間，同時使子代獲得比父代更好的解，需要進行交叉操作，產生新的染色體。鑒于本文所采用的基于工序編碼方法的特點，使用順序交叉和單點交叉相結合的方式，其算法步驟如下[13]：

（1）在兩個父代個體染色體P1和P2中，隨機選擇一個基因位i，將1～i之間的基因片段作為交叉區(qū)域，并把交叉區(qū)域內的基因編碼串分別記錄到A和B中；

（2）在父代個體P1中，從左向右依次查找B中的所有基因值，將P1中出現(xiàn)在對應位置的基因位刪除。同樣，在父代個體P2中從左向右依次查找A中的所有基因值，將P2中對應位置的基因位刪除；

（3）在兩個父代個體P1、P2中，剩下的基因位右移并保持相對位置不變。

（4）將P1交叉區(qū)域的內容替換為B的內容，將P2交叉區(qū)域的內容替換為A的內容。至此，將分別得到兩個子代個體C1和C2。具體的交叉過程如圖3所示。

圖3 交叉過程Fig 3 Crossprocess

2．2．3．變異

變異方法選擇不當則有可能產生無意義的方案。本文利用單個染色體基因段倒置的方式進行變異，這種變異方法也較為簡單。首先在一個染色體上任取A、B兩點，將這兩點之間的基因實施倒位即可得到新的染色體。變異操作具體實施的過程如圖4所示。

為了加快收斂速度和增加個體多樣性，利用文獻[14]提出一種自適應交叉和變異概率，具體計算如下：

在式（3）、（4）中，gmax是每代群體中個體的最大適應度值；gavg是每代群體的平均適應度值；g'是被選擇交叉的兩個個體中較大的適應度值；g是被選擇變異個體的適應度值。只要設定 k1, k2, k3, k4取(0,1)區(qū)間的值，就可自適應調整交叉和變異概率。

2．2．4．遺傳終止

重復以上步驟，直到滿足收斂條件或達到最大搜索步數為止，方可結束尋優(yōu)搜索。

圖4 變異過程Fig 4 Mutation process

3．調度實例

鑒于JSP的重要性和代表性，本文利用MT06基準案例來對本文使用的改進自適應遺傳算法進行驗證，其中MT06的加工工序和加工時間如表2所示。

算法參數選擇為：k1=1.0，k2=1.0，k3=0.5，k4=0.5，種群規(guī)模N=100，代數T=100。運用 matlab編程求解，很快就可收斂于調度問題的最優(yōu)解，如圖5所示。本文改進算法與基本遺傳算法的對比進化曲線如圖6所示?？芍?，利用本文改進的自適應遺傳算法只需3代就可得到問題的最優(yōu)值，而利用基本遺傳算法需要50代才能得到問題的最優(yōu)值，從而說明該改進遺傳算法的有效性和可行性。

圖5 調度結果Fig.5 Scheduling result

表2 加工工藝及約束關系Tab.2 Processing time and process constraints

圖6 進化曲線Fig.6 Evolutionary curve

4．結論

針對作業(yè)車間調度問題，利用一種改進的自適應遺傳算法進行求解。建立了以完工時間為目標的作業(yè)車間調度模型，通過設置編碼、解碼方案，以及確定選擇、交叉、變異等遺傳算子，并利用精英個體保留策略及改進的自適應交叉和變異概率解決作業(yè)車間調度問題。通過對基準案例實驗，得到優(yōu)化調度方案和進化曲線，結果驗證了該方法的有效性和可行性。

參考文獻：

[1]王凌．車間調度及其遺傳算法[M]．北京：清華大學出版社，2002：1-9．

[2]陶澤，張海濤．基于遺傳算法的Job-Shop調度問題研究[J]．沈陽理工大學學報，2016，35（2）：60-64．

[3]蔣麗雯．基于遺傳算法車間作業(yè)調度問題研究[D]．上海：上海交通大學，2007：17-20．

[4]GEN M,LIN L.Multiobjective Genetic Algorithm for Scheduling Problems in Manufacturing Systems[J].Industrial Engineering&Management Systems,2012,11(11):310-330.

[5]KURDI M.An effective new island model genetic algorithm for job shop scheduling problem[J].Computers&Operations Research,2016,67:132-142.

[6]ASADZADEH L.A local search genetic algorithm for the job shop scheduling problem with intelligent agents[J].Computers&Industrial Engineering,2015,85:376-383.

[7]彭憶炎，孔建壽，陳軒，等．面向智能制造的作業(yè)車間調度算法研究[J]．南京理工大學學報：自然科學版，2017，41（3）：322-329．

[8]趙小強，何浩．一種求解柔性作業(yè)車間調度問題的改進DRSGA[J]．南京理工大學學報：自然科學版，2016，40（3）：297-302．

[9]張超勇，董星，王曉娟，等．基于改進非支配排序遺傳算法的多目標柔性作業(yè)車間調度[J]．機械工程學報，2010，46（11）：156-164．

[10]LI X,GAO L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics,2016,174:93-110.

[11]王雷．類生物化制造系統(tǒng)協(xié)調機制及關鍵技術研究[D]．南京：南京航空航天大學，2010：37-39．

[12]萬敏，唐敦兵，王雷，等．求解車間調度問題的改進型自適應遺傳算法[J]．機械科學與技術，2011，30（1）：39-42．

[12]謝勝利，黃強，董金祥．求解JSP的遺傳算法中不可行調度的方案[J]．計算機集成制造系統(tǒng)，2002，8（11）：902-906．

[13]SRINIVAS M,PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithm [J].IEEE Transactions on Systems,Man,and Cybernetics,1994,24(4):656-667.