基于改進遺傳算法的作業車間調度

王 明，蔡勁草，王 雷

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

0．引言

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

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

1．作業車間調度模型

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

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

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

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

2．1．編碼與解碼

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

工件J1、J2和J3分別用數字1、2和3表示，假設它的一個染色體表示為[213123312]，其中染色體中的數字即表示工件也表示工序，其中從左到右第n次出現的該數字的次數表示該工件的第n道工序，如數字1在染色體中從左到右出現三次，則第一個數字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．選擇

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

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

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

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

2．2．2．交叉

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

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

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

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

（4）將P1交叉區域的內容替換為B的內容，將P2交叉區域的內容替換為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)區間的值，就可自適應調整交叉和變異概率。

2．2．4．遺傳終止

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

圖4 變異過程Fig 4 Mutation process

3．調度實例

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

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

圖5 調度結果Fig.5 Scheduling result

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

圖6 進化曲線Fig.6 Evolutionary curve

4．結論

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

參考文獻：

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

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

[3]蔣麗雯．基于遺傳算法車間作業調度問題研究[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]彭憶炎，孔建壽，陳軒，等．面向智能制造的作業車間調度算法研究[J]．南京理工大學學報：自然科學版，2017，41（3）：322-329．

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

[9]張超勇，董星，王曉娟，等．基于改進非支配排序遺傳算法的多目標柔性作業車間調度[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]王雷．類生物化制造系統協調機制及關鍵技術研究[D]．南京：南京航空航天大學，2010：37-39．

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

[12]謝勝利，黃強，董金祥．求解JSP的遺傳算法中不可行調度的方案[J]．計算機集成制造系統，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.