鄒澤樺,曾九孫,蔡晉輝

(中國(guó)計(jì)量大學(xué) 計(jì)量測(cè)試工程學(xué)院,杭州 310000)

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

鄒澤樺,曾九孫,蔡晉輝

(中國(guó)計(jì)量大學(xué) 計(jì)量測(cè)試工程學(xué)院,杭州 310000)

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

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

0 引言

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

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

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

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

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

注：J1標(biāo)示工件1，O11標(biāo)示工件1的第1道工序，符號(hào)‘-’標(biāo)示該工序無(wú)法在相應(yīng)機(jī)器上加工。

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

最大完工時(shí)間最小:

(1)

式中,Cj表示各個(gè)工件的完工時(shí)間。

機(jī)器最大負(fù)荷最小:

(2)

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

機(jī)器總負(fù)荷最小:

(3)

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

2 自適應(yīng)混合遺傳算法設(shè)計(jì)

2.1 自適應(yīng)遺傳算法設(shè)計(jì)

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

2.1.1 編碼

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

機(jī)器選擇基因塊：該基因塊長(zhǎng)度為各工件所有工序之和OALL,每個(gè)基因位用機(jī)器編號(hào)表示，每個(gè)基因位表示當(dāng)前工序可選機(jī)器集中所選擇的機(jī)器號(hào)。

圖1 機(jī)器選擇基因塊

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

圖2 工序排序基因塊

2.1.2 初始化種群

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

2.1.3 選擇

本文首先采用最大完工時(shí)間最小即公式(1)的指標(biāo)來對(duì)調(diào)度個(gè)體的適應(yīng)值進(jìn)行評(píng)價(jià)，即個(gè)體適應(yīng)值小的為優(yōu)良個(gè)體。當(dāng)兩調(diào)度個(gè)體的最大完工時(shí)間相同時(shí)，再考慮機(jī)器最大負(fù)荷即公式(2)和總機(jī)器負(fù)荷即公式(3)。

在計(jì)算完每個(gè)調(diào)度個(gè)體的適應(yīng)值后，采用精英保留策略和錦標(biāo)賽法相結(jié)合的方法進(jìn)行個(gè)體選擇。

2.1.4 交叉

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

海明距離的確定：

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

Step2：通過對(duì)工序排序基因塊中基因的解碼，得到各工序的順序號(hào)。

表2 工序排序基因塊海明距離計(jì)算

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

Step3：將Hm和Hp相加得到兩個(gè)父代調(diào)度個(gè)體的海明距離H。

確定海明距離后，通過與交叉閾值的比較，從而確定兩調(diào)度個(gè)體是否進(jìn)行交叉。本文提出的交叉閾值公式為：

(4)

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

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

2.1.5 變異

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

表3 變異概率選擇表

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

當(dāng)調(diào)度個(gè)體滿足變異概率要求時(shí)，則隨機(jī)產(chǎn)生一新個(gè)體替換當(dāng)前變異個(gè)體。

2.2 變鄰域搜索算法設(shè)計(jì)

在自適應(yīng)遺傳算法進(jìn)化期間加入變鄰域搜索算法，平衡算法在搜索過程中的廣泛性和集中性。本文結(jié)合文獻(xiàn)[14]不同的鄰域搜索結(jié)構(gòu)，設(shè)計(jì)了3種鄰域搜索方法。

2.2.1 鄰域結(jié)構(gòu)VNS1

鄰域結(jié)構(gòu)VNS1采取隨機(jī)改變工序排序基因塊中某一工序排序的方法，具體操作步驟為：

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

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

Step3：將G設(shè)置為G+1，若G

2.2.2 鄰域結(jié)構(gòu)VNS2

在鄰域結(jié)構(gòu)VNS2中，隨機(jī)選擇兩工件號(hào)，交換這兩個(gè)工件號(hào)所對(duì)應(yīng)的所有工序，從而改變工序排序基因塊中工序的加工順序，具體操作步驟為：

Step1：從所有工件號(hào)中隨機(jī)選擇兩個(gè)；

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

2.2.3 鄰域結(jié)構(gòu)VNS3

在鄰域結(jié)構(gòu)VNS3中，采取改變機(jī)器選擇基因塊中某一基因所選機(jī)器的方法，具體操作步驟為：

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

Step2：在機(jī)器選擇基因塊中隨機(jī)選擇一個(gè)基因，判斷該基因所對(duì)應(yīng)的工件工序，然后依次選擇該工序可選加工機(jī)器集中的機(jī)器，選取可使適應(yīng)值最小的機(jī)器。

Step3：將S設(shè)置為S+1，若S

2.3 算法整體流程

當(dāng)自適應(yīng)遺傳算法在執(zhí)行完交叉變異操作后為擴(kuò)大每個(gè)調(diào)度個(gè)體的局部搜索范圍，結(jié)合以上3種變鄰域搜索，具體流程如下：

Step2：令n←1，l←1；

Step3：若l=1，則對(duì)x進(jìn)行VNS1鄰域結(jié)構(gòu)變換(Gmax=2)；若l=2，則對(duì)x進(jìn)行VNS2鄰域結(jié)構(gòu)變換；若l=3，則對(duì)x進(jìn)行VNS1鄰域結(jié)構(gòu)變換(Gmax=4) ；若l=4，則對(duì)x進(jìn)行VNS3鄰域結(jié)構(gòu)變換(Smax=1)；若l=5，則對(duì)x進(jìn)行VNS1鄰域結(jié)構(gòu)變換(Gmax=6) ；若l=6，則對(duì)x進(jìn)行VNS3鄰域結(jié)構(gòu)變換(Smax=2)，進(jìn)過相應(yīng)鄰域結(jié)構(gòu)變換后的解為x′；

Step5：若n

自適應(yīng)混合遺傳算法總體流程如圖 3所示。

圖3 自適應(yīng)混合遺傳算法總體流程圖

3 實(shí)驗(yàn)結(jié)果及分析

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

圖4 8×8 P-FJSP實(shí)例的收斂曲線

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

圖5 8×8 P-FJSP調(diào)度實(shí)例解

圖6 10×10 T-FJSP調(diào)度實(shí)例解

圖7 15×10 P-FJSP調(diào)度實(shí)例解

4 總結(jié)

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

[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án)洪森. 柔性作業(yè)車間生產(chǎn)計(jì)劃與調(diào)度集成優(yōu)化求解策略[J]. 自動(dòng)化學(xué)報(bào), 2013, 39(9): 147-1491.

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

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

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

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

[9] 廖 珊, 翟所霞, 魯玉軍. 基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度方法研究[J]. 機(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] 張國(guó)輝. 柔性作業(yè)車間調(diào)度方法研究[D]. 武漢：華中科技大學(xué), 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。

國(guó)家自然科學(xué)基金(61203088,61673358)。

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

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

1671-4598(2017)04-0167-05

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

TP18

A

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