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