作業(yè)車間調(diào)度JSP與遺傳算法GA及其Python/Java/C++實現(xiàn)
大家好呀，好久不見！
最近小編接觸了遺傳算法（Genetic Algorithm）。關(guān)于遺傳算法，公眾號內(nèi)已經(jīng)有多盤技術(shù)推文介紹：
【優(yōu)化算法】遺傳算法(Genetic Algorithm) （附代碼及注釋）
轉(zhuǎn)載 | 遺傳算法求解混合流水車間調(diào)度問題（附C++代碼）
今天小編再為大家?guī)鞢SDN上一位大牛@sundial dreams
關(guān)于遺傳算法在?作業(yè)車間調(diào)度問題?上的相關(guān)內(nèi)容，希望大家喜歡！
（原文附圖）
問題描述
作業(yè)車間調(diào)度(Job shop scheduling problem, JSP) 是車間調(diào)度中最常見的調(diào)度類型，是最難的組合優(yōu)化問題之一，應(yīng)用領(lǐng)域極其廣泛，涉及航母調(diào)度，機(jī)場飛機(jī)調(diào)度，港口碼頭貨船調(diào)度，汽車加工流水線等，因此對其研究具有重大的現(xiàn)實意義。科學(xué)有效的生產(chǎn)調(diào)度不但可以提高生產(chǎn)加工過程中工人、設(shè)備資源的高效利用，還可縮短生產(chǎn)周期，降低生產(chǎn)成本。
作業(yè)車間調(diào)度問題描述：
一個加工系統(tǒng)有M臺機(jī)器，要求加工N個作業(yè)，其中，作業(yè)i包含工序數(shù)為L_i。令，則L為任務(wù)集的總工序數(shù)。其中，各工序的加工時間已確定，并且每個作業(yè)必須按照工序的先后順序加工。調(diào)度的任務(wù)是安排所有作業(yè)的加工調(diào)度排序，約束條件被滿足的同時，使性能指標(biāo)得到優(yōu)化。作業(yè)車間調(diào)度需要考慮如下約束:
1.每道工序在指定的機(jī)器上加工，且必須在前一道工序加工完成后才能開始加工。
2.某一時刻1臺機(jī)器只能加工1個作業(yè)。
3.每個作業(yè)只能在1臺機(jī)器上加工1次。
4.各作業(yè)的工序順序和加工時間已知，不隨加工排序的改變而改變。
問題的數(shù)學(xué)模型：
令(i,j)表示作業(yè)i的第j個工序。S_ij和T_ij分別表示(i,j)的加工起始時刻和加工時間。Z_ijk表示(i,j)是否在第k臺機(jī)器上加工：如果(i,j)在第k臺機(jī)器上加工，Z_ijk=1；否則，Z_ijk=0，C_k為第k臺機(jī)器的完工時間，則問題的數(shù)學(xué)模型如下：
? ? ?公式(1)為目標(biāo)函數(shù)，即優(yōu)化目標(biāo)，系統(tǒng)中使用總加工時間最短為優(yōu)化目標(biāo)。公式(2)表示1個作業(yè)只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1個作業(yè)的第1道工序的起始加工時刻大于或等于0。公式(4)表示在1臺機(jī)床上不會同時加工1個以上的作業(yè)。
遺傳算法
隨著遺傳算法（genetic algorithm (GA)）在組合優(yōu)化問題的廣泛應(yīng)用，許多人開始對遺傳算法進(jìn)行深度研究。已有研究結(jié)果表明，遺傳算法對求解作業(yè)車間調(diào)度問題具有較好的效果，因此系統(tǒng)采用遺傳算法來解該問題，遺傳算法是計算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。系統(tǒng)通過模擬生物進(jìn)化，包括遺傳、突變、選擇等，來不斷地產(chǎn)生新個體，并在算法終止時求得最優(yōu)個體，即最優(yōu)解。
遺傳算法解決作業(yè)車間調(diào)度問題基本步驟：
1.初始化一定數(shù)量的種群（染色體編碼）
2.計算個體適應(yīng)度（染色體解碼）
3.采用錦標(biāo)賽法選擇染色體并交叉產(chǎn)生新個體
4.個體（染色體）變異
5.達(dá)到遺傳代數(shù)終止算法并從中選取適應(yīng)度最優(yōu)的個體作為作業(yè)車間調(diào)度問題的解
流程圖如下：
遺傳算法所需參數(shù)：
1.種群規(guī)模：種群中個體的數(shù)量，用populationNumber表示
2.染色體長度：個體的染色體的長度，用chromosomeSize表示
3.交叉概率：控制交叉算子的使用頻率，用crossProbability表示，并且值為0.95
4.變異概率：控制變異算子的使用頻率，用mutationProbability表示，并且值為0.05
5.遺傳代數(shù)：種群的遺傳代數(shù)，用于控制遺傳算法的終止，用times來表示
遺傳算法實現(xiàn)基本步驟及偽代碼：
1. 編碼及初始化種群
? ? ? ?采用工序?qū)崝?shù)編碼來表示染色體，即M臺機(jī)器，N個工件，每個工件的工序數(shù)為process_i，則染色體長度為chromosome=process_1+process_2+...，對染色體編碼如下：
chromosome=...,w_i,w_j,w_k,...
其中w_i代表第i個工件編號，而出現(xiàn)的次數(shù)代表該工件的第幾道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的編號，第幾次出現(xiàn)就代表第幾道工序。然后將每一次隨機(jī)生成的染色體個體加入到種群集合中。
算法偽代碼：
2. 解碼及計算適應(yīng)度
? ? ? ?將優(yōu)化目標(biāo)定義為總加工時間最短，因此適應(yīng)度定義為最短加工時間的倒數(shù)，設(shè)fitness為對應(yīng)個體的適應(yīng)度，fulfillTime為最短加工時間，因此? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
其中fulfillTime的計算方法如下：
首先定義如下變量
然后從左到右遍歷個體的染色體序列，其中表示第i個工件的編號，則對應(yīng)的當(dāng)前工序為,設(shè)為p。當(dāng)前工件當(dāng)前工序所使用的機(jī)器編號為，設(shè)為m。當(dāng)前工件當(dāng)前工序?qū)?yīng)的加工時間為，設(shè)為t。則工件的第p道工序的最晚開始時間為? ? ? ? ??
而第m臺機(jī)器的加工時間為? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
工件的第p道工序的結(jié)束時間為
最后加工完所有工件的最短加工時間fulfillTime為
從而計算出適應(yīng)度fitness。
PS.小編覺得解碼的過程類似動態(tài)規(guī)劃。
偽代碼如下：
3. 個體選擇算子
個體的選擇使用錦標(biāo)賽法，其基本策略為從整個種群中隨機(jī)抽取n個個體讓它們競爭，選取其中最優(yōu)的個體。該算子的選擇過程如下
偽代碼如下：
4. 染色體交叉算子
使用Order Crossover(OX)交叉算子，該算子的交叉步驟如下：
對于一對染色體g1, g2，首先隨機(jī)產(chǎn)生一個起始位置start和終止位置end，并由從g1的染色體序列從start到end的序列中產(chǎn)生一個子代原型
?將g2中不包含在child prototype的其余編碼加入到child prototype兩側(cè)
上述步驟將產(chǎn)生一個child，交換g1, g2即可產(chǎn)生另一個child
偽代碼如下：
5. 染色體變異算子
變異的作用主要是使算法能跳出局部最優(yōu)解，因此不同的變異方式對算法能否求得全局最優(yōu)解有很大的影響。使用位置變異法作為變異算子，即從染色體中隨機(jī)產(chǎn)生兩個位置并交換這兩個位置的值
偽代碼如下：
6. 算法整體偽代碼如下：
代碼實現(xiàn)
原作者編寫了Java，Python，C++三個版本的代碼，小編仔細(xì)閱讀了Java代碼，在其中加入一些注釋并略作修改，分享給大家。
說明一下輸入部分，輸入的算例是寫死在代碼中的，算例如下：
Jop0=[(0,3),(1,2),(2,2)]
Jop1=[(0,2),(2,1),(1,4)]
Jop2=[(1,4),(2,3)]
圖中是其中一種可行解。
那么本期內(nèi)容到這里就差不多結(jié)束了。下次再見~
最后祝愿武漢早日度過難關(guān)，小編早就想上學(xué)了！
武漢加油！
進(jìn)入公眾號輸入【GAJSP】不帶【】即可下載代碼