前兩篇文章中,我們介紹了FJSP問題,并梳理了一遍HA算法。這一篇文章對小編實作的(很亂很爛的)代碼進行簡單解讀。
往期回顧:
種群進化+鄰域搜尋的混合算法(GA+TS)求解作業工廠中的房間排程問題(JSP)-算法介紹
混合算法(GA+TS)求解作業工廠中的房間排程問題(JSP)-禁忌搜尋部分
代碼下載下傳請關注公衆号,背景回複【FJSPHA】即可,不包括【】
代碼架構
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SNidjNzQWOkdTNyEWZyIGOiN2YyEjMklTZjFGZzU2Ny8CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
代碼分為5個包,第一部分Data為用到的各類結構,第二部分GA為GA部分+第一個TS,第三部分主函數,第四、五部分是兩個TS。
算例放置在input檔案夾中,這裡準備了Mk系列算例,Kacem系列算例和論文中的簡單算例test.txt。
Main
算例輸入:
Main中還有一個輸出為CSV的函數,需要一個jar包,已經放在下載下傳連結裡了,不需要的同學也可以删除。
Data
一堆亂七八糟的結構。這裡簡單講一下Solution類和Graph類。
Solution類中包含多個print函數,比較重要的包括繪制甘特圖以及check解是否合法。
operationMatrix是解的主題,存放某個工件的某道工序的開始、結束時間,所在加工機器。
Graph類表示析取圖。nodeList是每台機器上的node。其中起始點、終止點我單獨提取出來設定了兩個類。Graph中還包含了擷取critical path的DFS和update starting time & end time的Bellman算法。
GA
MyHybridAlgorithm類是GA的主函數。小編在實作的時候進行了多種測試,比如疊代的noImprove次數達到limit時進行擾動:
選擇哪種Tabu:
讀者在閱讀的時候請自己注意。
算法相關的參數我都做了初始化,請自行查找修改:
交叉、變異等操作包含在ChromosomeOperation類中,計算适應度的函數在CaculateFitness類中,TabuSearch1類是基于編碼的tabu,這裡都不多展示了。
NeighbourSearch
這個包包含的是基于析取圖的tabu。NeighbourAlgorithms類相當于Main,包含解轉化為圖的函數:
TabuSearch2類為tabu主函數。NeighbourGraph類存放析取圖鄰域搜尋産生的解。
DeleteNeighbourGraph類為析取圖中暫時去掉某個點後的情況,PM、PJ、SM、SJ代表precede、succeed、machine、job四條邊對應的點,deleteNode為删去的點。
其中還有findLandR位置的二分查找函數,insert時的估值函數:
NeighbourSearch2
這個包為第三個基于甘特圖的tabu。
RTS類為tabu的主函數。解通過:ArrayList<ArrayList<Operation>> 的形式表示。
replan函數中包含了在甘特圖上進行swap操作後更新解的方法,有詳細注釋:
總結
到這裡已經大緻梳理了一遍代碼,但其中還有很多細節沒有講到,包括很多東西實作的不好,歡迎随時和我交流。
由于是自己研究時寫的代碼,其中很多東西會比較亂,但是代碼中做了很多注解,仔細閱讀應該能看得懂的!
下載下傳的壓縮包裡包括我學習過程中看過的大部分文獻,包括主要參考的文獻,大家可以進一步閱讀研究。