溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關怎樣進行作業車間調度JSP與遺傳算法GA及其Python/Java/C++實現，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
問題描述
作業車間調度(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)]
圖中是其中一種可行解。
以上就是怎樣進行作業車間調度JSP與遺傳算法GA及其Python/Java/C++實現，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
