王 明，蔡勁草，王 雷

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

0．引言

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

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

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

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

本文以工件的最短完工時間為目標(biāo)，建立目標(biāo)函數(shù)（1）為：

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

2．改進(jìn)遺傳算法求解作業(yè)車間調(diào)度問題

2．1．編碼與解碼

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

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

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

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

2．2．遺傳操作設(shè)計

2．2．1．選擇

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

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

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

圖2 解碼獲得的調(diào)度結(jié)果Fig.2 Scheduling results obtained by decoding

2．2．2．交叉

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

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

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

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

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

圖3 交叉過程Fig 3 Crossprocess

2．2．3．變異

變異方法選擇不當(dāng)則有可能產(chǎn)生無意義的方案。本文利用單個染色體基因段倒置的方式進(jìn)行變異，這種變異方法也較為簡單。首先在一個染色體上任取A、B兩點，將這兩點之間的基因?qū)嵤┑刮患纯傻玫叫碌娜旧w。變異操作具體實施的過程如圖4所示。

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

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

2．2．4．遺傳終止

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

圖4 變異過程Fig 4 Mutation process

3．調(diào)度實例

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

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

圖5 調(diào)度結(jié)果Fig.5 Scheduling result

表2 加工工藝及約束關(guān)系Tab.2 Processing time and process constraints

圖6 進(jìn)化曲線Fig.6 Evolutionary curve

4．結(jié)論

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

參考文獻(xiàn)：

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

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

[3]蔣麗雯．基于遺傳算法車間作業(yè)調(diào)度問題研究[D]．上海：上海交通大學(xué)，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è)車間調(diào)度算法研究[J]．南京理工大學(xué)學(xué)報：自然科學(xué)版，2017，41（3）：322-329．

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

[9]張超勇，董星，王曉娟，等．基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J]．機(jī)械工程學(xué)報，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é)調(diào)機(jī)制及關(guān)鍵技術(shù)研究[D]．南京：南京航空航天大學(xué)，2010：37-39．

[12]萬敏，唐敦兵，王雷，等．求解車間調(diào)度問題的改進(jìn)型自適應(yīng)遺傳算法[J]．機(jī)械科學(xué)與技術(shù)，2011，30（1）：39-42．

[12]謝勝利，黃強(qiáng)，董金祥．求解JSP的遺傳算法中不可行調(diào)度的方案[J]．計算機(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.