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

鄒澤樺,曾九孫,蔡晉輝

(中國計量大學 計量測試工程學院,杭州 310000)

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

鄒澤樺,曾九孫,蔡晉輝

(中國計量大學 計量測試工程學院,杭州 310000)

針對柔性作業(yè)車間調度問題中最大完工時間、機器最大負荷和總機器負荷三項性能指標，提出一種改進的自適應交叉和變異的混合遺傳算法;在基本遺傳算法染色體編碼的基礎上，設計一種基于海明距離的調度個體差異判別方法，并通過自適應交叉閾值和動態(tài)變異概率計算提高遺傳算法整個種群調度個體的多樣性，防止算法過早的進入早熟;在遺傳算法進化期間，對每個調度個體的進化采用變鄰域搜索算法，擴大調度個體的鄰域搜索范圍;最后，使用文獻中相同的調度實例將文章的計算結果與其它文獻中的測試結果進行比較，驗證了所提出的算法的可行性和有效性。

柔性作業(yè)車間調度; 海明距離; 遺傳算法; 變鄰域搜索算法

0 引言

柔性作業(yè)車間調度問題(flexible job-shop scheduling problem，F(xiàn)JSP)是傳統(tǒng)作業(yè)車間調度問題(job-shop scheduling problem，JSP)的擴展，由Bruker和Schile[1]于1990年首次提出。目前，對柔性作業(yè)車間調度問題的算法研究比較普遍。如Liao等[2]采用禁忌搜索法；Birgin等[3]采用列表排程和集束搜索相結合的方法；安玉偉[4]設計了一種基于拉格朗日松弛的分解方法，在確定計劃問題后再對調度問題求解；黃敏[5]等在考慮設備帶有惡性條件的情況下使用嵌套分割算法與單親遺傳算法相結合的方法。同時，將排程算法應用到工廠的實例也越來越多，鄭克波[6]通過遺傳算法實現(xiàn)對某軸承企業(yè)的生產(chǎn)排程；王犇[7]采用TOC約束理論實現(xiàn)對飛機復合材料的生產(chǎn)排程；王延斌[8]先采用蟻群算法解決工序的設備選擇問題之后根據(jù)啟發(fā)式規(guī)則解決設備上各工序加工的先后順序等。其中，遺傳算法由于魯棒性與通用性好、全局搜索能力強的特點得到了廣泛應用，利用遺傳算法求解FJSP的例子也較多，如廖珊等[9]設計一種自適應的遺傳變異算子，改善了遺傳算法后期停滯不前的現(xiàn)象；Teekeng等[10]設計了一種模糊輪盤賭選擇與配對方法改進遺傳算法的選擇操作；Ishikawa等[11]采用分層混合空間遺傳算法方法在設備和工序兩個層次空間下使用遺傳算法，交替優(yōu)化。盡管這些方法在計算效率等方面較傳統(tǒng)方法有了較大改進，但以上文獻多在初始化和選擇階段對遺傳算法進行改進而遺傳算法過早進入早熟與局部搜索能力弱的缺點依舊存在。

為在遺傳算法進化的同時保持種群個體的多樣性，本文在FJSP的基礎上提出了一種自適應交叉和變異方法。在改進當前遺傳算法的同時，設計了三張鄰域搜索結構，將每一代種群的調度個體作為變鄰域搜索的初始解，設計了具有3種結構集的變鄰域搜索方法，在算法進化期間每個調度個體都可以搜索自己鄰域范圍內的最優(yōu)解，從而在防止早熟的同時加快收斂速度。

1 柔性作業(yè)車間調度問題FJSP描述

柔性作業(yè)車調度問題可以描述為:n個工件J={J1,J2,J3,......Jn}要在m臺機器M={M1,M2,M3,...，Mm}上加工。每個工件相互獨立且包含一道或多道工序，工序加工順序及工藝路線則是根據(jù)每個工件的自身情況而確定的.調度目標是為每個工件的各個工序選擇最合適的機器、并且確定每個工件的各個工序的在其所屬的機器上的加工開始時間，使整個系統(tǒng)的某些性能指標達到最優(yōu)或近最優(yōu)狀態(tài)。如表 1所示即為一個柔性作業(yè)車間調度實例。

表1 柔性作業(yè)車間作業(yè)工件工序加工時間表

注：J1標示工件1，O11標示工件1的第1道工序，符號‘-’標示該工序無法在相應機器上加工。

在FJSP的求解過程中，需要一定的目標函數(shù)或者說評價指標來判斷調度方案的優(yōu)劣。下面列出了常見的幾個評價指標：

最大完工時間最小:

(1)

式中,Cj表示各個工件的完工時間。

機器最大負荷最小:

(2)

式中，hj表示工件所包含的工序數(shù)量，Tijh表示工件j的h工序在機器i上的加工時間，xijh表示工件j的h工序是否選擇機器i加工，1表示選擇機器i加工，0表示不選擇機器i加工。

機器總負荷最小:

(3)

以上幾種性能指標比較常用，不同的情況下會有不同的生產(chǎn)調度要求，從而選擇不同的調度策略，一般情況下會選擇最大完工時間最小作為調度目標，目的是盡可能早的完成加工任務。在保證最大完工時間最小的同時，也會考慮平衡各機器負荷，使各機器總負荷最小，最終使整個調度目標在時間的度量下達到最優(yōu)或近最優(yōu)。

2 自適應混合遺傳算法設計

2.1 自適應遺傳算法設計

遺傳算法(genetic algorithm, GA)是對達爾文著《物種起源》的人工化種群模擬，最早在1975年由Michigan大學的Holland[12]教授開始對其進行系統(tǒng)化的研究。

2.1.1 編碼

在染色體編碼方面，本文采用文獻[13]中所采用的分段編碼的方式，將染色體基因分為機器選擇基因塊與工序排序基因塊兩塊。

機器選擇基因塊：該基因塊長度為各工件所有工序之和OALL,每個基因位用機器編號表示，每個基因位表示當前工序可選機器集中所選擇的機器號。

圖1 機器選擇基因塊

工序排序基因塊：該基因塊長度為各工件所有工序之和OALL. 每個基因位用工件號表示，工件號在此基因塊中出現(xiàn)的次數(shù)等于工件所包含的工序數(shù)量，對于第h次出現(xiàn)的工件號，表示該工件第h道工序，以表1調度實例為例的工序排序基因塊如圖2所示，工序加工順序O11-O31-O21-O32-O12-O33-O22。

圖2 工序排序基因塊

2.1.2 初始化種群

為保證初始種群的多樣性，每個調度個體的機器選擇基因塊和工序排序基因塊均采用隨機初始化的方式初始化染色體的各個基因位。

2.1.3 選擇

本文首先采用最大完工時間最小即公式(1)的指標來對調度個體的適應值進行評價，即個體適應值小的為優(yōu)良個體。當兩調度個體的最大完工時間相同時，再考慮機器最大負荷即公式(2)和總機器負荷即公式(3)。

在計算完每個調度個體的適應值后，采用精英保留策略和錦標賽法相結合的方法進行個體選擇。

2.1.4 交叉

交叉操作在遺傳算法屬于關鍵步驟。為判斷兩個編碼染色體之間的差異程度，本文提出一種基于海明距離的調度個體差異判別方法。海明距離(hammingdistance)指相同長度的編碼在同一位置上不同碼值的個數(shù)總和。

海明距離的確定：

Step1：判斷兩個父代調度個體中機器選擇基因塊中相同工序不同機器選擇基因的個數(shù)總和；

Step2：通過對工序排序基因塊中基因的解碼，得到各工序的順序號。

表2 工序排序基因塊海明距離計算

如表2所示，兩個父代調度個體工序排序基因塊分別是1-3-1-3-2-3-2，2-1-3-3-2-1-3通過對各工序的順序計算得出工序排序基因塊海明距離Hp為6；

Step3：將Hm和Hp相加得到兩個父代調度個體的海明距離H。

確定海明距離后，通過與交叉閾值的比較，從而確定兩調度個體是否進行交叉。本文提出的交叉閾值公式為：

(4)

式中,TALL為染色體總長度，即兩倍的工序總和，g為當前進化代數(shù)，G為總群進化總代數(shù)。交叉閾值過大將會導致種群進化緩慢，而過小則極易使種群陷入早熟。由交叉閾值公式(4)可知，在種群進化初期，兩個父代調度個體的交叉閾值接近于染色體總長度的三分之二，只有兩個父代調度個體之間的海明距離達到交叉閾值時才可進行交叉，在進化后期，交叉閾值約為染色體總長度的三分之一，這也與后期調度個體間差異逐漸變小的狀況相符合。

在兩個父代調度個體的海明距離達到交叉閾值后，根據(jù)編碼規(guī)則，交叉方法分為機器選擇基因塊交叉和工序排序基因塊交叉。在機器選擇基因塊交叉中，確定一定數(shù)量的工序，將父代調度個體一中剩余工序的機器選擇號與父代調度個體二中剩余工序的機器選擇號進行交換；在工序排序基因段交叉中，確定一定少于工件總數(shù)數(shù)量的工件號，將兩個父代調度個體中剩余工件號的基因位進行互換。

2.1.5 變異

根據(jù)不同調度個體的交叉操作結果和其適應值大小，本文提出一種自適應變異概率計算方法。如表 3所示，對調度個體適應值優(yōu)于種群平均適應值(f

表3 變異概率選擇表

表3中，xH表示該個體是否參與交叉的標志，當xH=1時，表示該個體參與交叉；否則，該個體沒有參與交叉。Pmax和Pmin為最大變異概率和最小變異概率，為防止過大的變異概率破壞種群調度個體的優(yōu)良模式，這里分別取0.1和0.01，favg即為種群平均適應值，f為該個體適應值，fbest為種群中最佳適應值，fworst為種群中最差適應值。

當調度個體滿足變異概率要求時，則隨機產(chǎn)生一新個體替換當前變異個體。

2.2 變鄰域搜索算法設計

在自適應遺傳算法進化期間加入變鄰域搜索算法，平衡算法在搜索過程中的廣泛性和集中性。本文結合文獻[14]不同的鄰域搜索結構，設計了3種鄰域搜索方法。

2.2.1 鄰域結構VNS1

鄰域結構VNS1采取隨機改變工序排序基因塊中某一工序排序的方法，具體操作步驟為：

Step1：設置鄰域結構VNS1最大循環(huán)次數(shù)Gmax，并將初始化為1；

Step2：在工序排序基因段中隨機選擇一個工序，若該工序在滿足同一工件工序約束的前提下可以隨機跟處于同一設備的加工工序交換位置；

Step3：將G設置為G+1，若G

2.2.2 鄰域結構VNS2

在鄰域結構VNS2中，隨機選擇兩工件號，交換這兩個工件號所對應的所有工序，從而改變工序排序基因塊中工序的加工順序，具體操作步驟為：

Step1：從所有工件號中隨機選擇兩個；

Step2：提取工序排序基因塊中相對應的兩個工件的所有工序號，若兩工件的工序數(shù)量相等，則將對應工序交換即可，若兩個工件的工序數(shù)量不相等，則先將兩者中工序數(shù)較少的工件A工序依次移到工序數(shù)較多的工件B基因位置上，然后在空缺的基因位上填入工件B的工序，產(chǎn)生新的鄰域解。

2.2.3 鄰域結構VNS3

在鄰域結構VNS3中，采取改變機器選擇基因塊中某一基因所選機器的方法，具體操作步驟為：

Step:1：設置鄰域結構VNS3最大循環(huán)次數(shù)Smax，并將設置為1；

Step2：在機器選擇基因塊中隨機選擇一個基因，判斷該基因所對應的工件工序，然后依次選擇該工序可選加工機器集中的機器，選取可使適應值最小的機器。

Step3：將S設置為S+1，若S

2.3 算法整體流程

當自適應遺傳算法在執(zhí)行完交叉變異操作后為擴大每個調度個體的局部搜索范圍，結合以上3種變鄰域搜索，具體流程如下：

Step2：令n←1，l←1；

Step3：若l=1，則對x進行VNS1鄰域結構變換(Gmax=2)；若l=2，則對x進行VNS2鄰域結構變換；若l=3，則對x進行VNS1鄰域結構變換(Gmax=4) ；若l=4，則對x進行VNS3鄰域結構變換(Smax=1)；若l=5，則對x進行VNS1鄰域結構變換(Gmax=6) ；若l=6，則對x進行VNS3鄰域結構變換(Smax=2)，進過相應鄰域結構變換后的解為x′；

Step5：若n

自適應混合遺傳算法總體流程如圖 3所示。

圖3 自適應混合遺傳算法總體流程圖

3 實驗結果及分析

為比較算法的尋優(yōu)性能，分別采取8個工件8臺機器的部分柔性作業(yè)車間調度問題(8×8)、10個工件10臺機器(10×10)的和15個工件10臺機器(15×10)的完全柔性作業(yè)車間調度問題的FJSP實例進行測試。大鄰域搜索次數(shù)，最大迭代次數(shù)。當算法尋求8×8P-FJSP實例的最優(yōu)解時，其收斂曲線如圖4所示，算法在進化到第十代即可尋得最大完工時間的最優(yōu)解。

圖4 8×8 P-FJSP實例的收斂曲線

表 4列出了本文所提出的自適應混合遺傳算法與其他算法在8×8P-FJSP調度實例、10×10和15×10T-FJSP調度實例問題上3個目標函數(shù)：最大完工時間最小，機器最大負荷最小和機器總負荷最小的最優(yōu)值比較。表中比較對象分別為混合目標模擬退火算法(MOSA)[15]、平行變鄰域算法(PVNS)、粒子群與模擬退火混合算法(PSO+SA)[16]以及在預先選擇設備下使用遺傳算法(AL+CGA)[17]。從表 4可以看出，本文所提出的自適應混合遺傳算法取得了較好的計算結果。在求解8×8P-FJSP調度實例時，在少許增加的情況下，和的目標值都等于或優(yōu)于其它4種算法。在求解10×10F-FJSP調度實例時，與Xia的方法相比，在和的目標值相等的情況下，的目標值縮短了2小時，與Kacem的方法相比，在的目標值相等，的目標值增加1小時的情況下，的目標值縮短了3小時。在求解15×10P-FJSP調度實例時，在的目標值和 的目標值與Xia和Kacem的方法相等的情況下，的目標值分別縮短了1小時和13小時。圖 5、圖 6和圖 7分別表示8×8P-FJSP調度實例問題、10×10和15×10T-FJSP調度實例問題相應的甘特圖。實驗結果表示本文所提出的自適應混合遺傳算法在求解柔性作業(yè)車間問題時可以取得較好的調度解。

圖5 8×8 P-FJSP調度實例解

圖6 10×10 T-FJSP調度實例解

圖7 15×10 P-FJSP調度實例解

4 總結

本文針對FJSP柔性作業(yè)車間調度問題，對現(xiàn)有設備選擇基因塊和工序排序基因塊進行分析，提出了一種基于海明距離個體間差異判別方法，將兩父代個體間的海明距離與交叉閾值進行比較后決定是否進行交叉操作，而父代個體是否進行交叉操作也將影響其變異概率，有效防止相似父代個體交叉所導致早熟的出現(xiàn)。同時，針對遺傳算法局部搜索能力較弱的問題，改進了3種鄰域搜索方法，加強了遺傳算法的局部搜索能力。最后通過3個調度實例的實驗比對，驗證了所提出的方法可行性和有效性。

[1]BruckerP,SchilieR.Job-shopschedulingwithmulti-purposemachines[J].Computing, 1990, 45(4): 369-375.

[2]LiaoLM,HuangCJ.Tabusearchheuristicfortwo-machineflowshopwithbatchprocessingmachines[J].Computers&IndustrialEngineering, 2011, 60(3): 426-432.

[3]BirginEG,FerreiraJE,RonconiDP.Listschedulingandbeamsearchmethodsfortheflexiblejobshopschedulingproblemwithsequencingflexibility[J].EuropeanJournalofOperationalResearch, 2015, 247(2): 421-440.

[4] 安玉偉, 嚴洪森. 柔性作業(yè)車間生產(chǎn)計劃與調度集成優(yōu)化求解策略[J]. 自動化學報, 2013, 39(9): 147-1491.

[5] 黃 敏, 付亞平, 王洪峰, 等. 設備帶有惡化特性的作業(yè)車間調度模型與算法[J]. 自動化學報, 2013, 41(3): 551-558.

[6] 鄭波克. 基于MES的軸承制造企業(yè)生產(chǎn)排程優(yōu)化及算法研究[D]. 洛陽：河南科技大學, 2012.

[7] 王 犇. 飛機復合材料MES計劃排程系統(tǒng)研究與開發(fā)[D]. 南京：南京航空航天大學, 2011.

[8] 王延斌. 面向模具的制造執(zhí)行系統(tǒng)關鍵技術研究[D]. 哈爾濱：哈爾濱工業(yè)大學, 2007.

[9] 廖 珊, 翟所霞, 魯玉軍. 基于改進遺傳算法的柔性作業(yè)車間調度方法研究[J]. 機電工程, 2014, 31(6):729-733.

[10]TeekengW,ThammanoA.Modifiedgeneticalgorithmforflexiblejob-shopschedulingproblems[J].ProcediaComputerScience, 2012, 12(12): 122-128.

[11]IshikawaS,KubotaR,HorioK.Effectivehierarchicaloptimizationbyahierarchicalmulti-spacecompetitivegeneticalgorithmfortheflexiblejob-shopschedulingproblem[J].ExpertSystemswithApplications, 2015, 42(24): 9434-9440.

[12]HollandJH.Adaptioninnaturalandartificialsystems[M].AnnArbor:TheUniversityofMichiganPress, 1975.

[13] 張國輝. 柔性作業(yè)車間調度方法研究[D]. 武漢：華中科技大學, 2009.

[14]YazdaniM,AmiriM,ZandiehM.Flexiblejob-shopschedulingwithparallelvariableneighborhoodsearchalgorithm[J].ExpertSystemswithApplications, 2010, 37(1): 678-687.

[15]KaplanogluV.Anobject-orientedapproachformulti-objectiveflexiblejob-shopschedulingproblem[J].ExpertSystemswithApplicationsAnInternationalJournal, 2016, 45(C): 71-84.

[16]XiaW,WuZ.Aneffectivehybridoptimizationapproachformulti-objectiveflexiblejob-shopschedulingproblems[J].KongzhiYuJuece/control&Decision, 2005, 48(2): 409-425.

[17]KacemI,HammadiS,BorneP.Pareto-optimalityapproachforflexiblejob-shopschedulingproblems:hybridizationofevolutionaryalgorithmsandfuzzylogic[J].MathematicsandComputersinSimulation, 2002, 60: 245-276.

Improved Genetic Algorithm for Flexible Job-shop Scheduling Problem

Zou Zehua, Zeng Jiusun, Cai Jinhui

(China JiLiang University, Hangzhou 310000, China)

To deal with the flexible job-shop scheduling problem, a self-adaptive hybrid genetic algorithm is proposed by considering the performance index of maximum completion time, maximum machine load and total load. On the basis of the chromosome coding of basic genetic algorithm for the flexible job-shop scheduling problem, a new method for discriminating differences between scheduling individuals is designed based on the Hamming distance, and the population diversity is improved by the self-adaptive threshold value for the operation of crossover and the dynamic calculation of the probability of the operation of the mutation to prevent premature convergence. During the evolution of the genetic algorithm, each individual executes variable neighborhood search to enhance the local search of genetic algorithm. The self-adaptive and hybrid genetic algorithm is tested on examples taken from the literature and compared with their results. The computation results show that the self-adaptive and hybrid genetic algorithm is feasible and effective.

flexible job-shop scheduling; Hamming distance; genetic algorithm; variable neighborhood search

2016-11-02；

2016-11-26。

國家自然科學基金(61203088,61673358)。

鄒澤樺(1991-)，男，浙江紹興人，碩士研究生，主要從事智能制造、智能生產(chǎn)方向的研究。

曾九孫(1982-)，男，浙江杭州人，副教授，碩士研究生導師，主要從事信號分析與處理，統(tǒng)計過程控制方向的研究。

1671-4598(2017)04-0167-05

10.16526/j.cnki.11-4762/tp.2017.04.046

TP18

A

蔡晉輝(1974-)，男，浙江杭州人，教授，碩士研究生導師，主要從事檢測技術與自動化裝置方向的研究。