前兩篇文章中，我們介紹了FJSP問(wèn)題，并梳理了一遍HA算法。這一篇文章對(duì)小編實(shí)現(xiàn)的（很亂很爛的）代碼進(jìn)行簡(jiǎn)單解讀。

往期回顧：

種群進(jìn)化＋鄰域搜索的混合算法（GA＋TS）求解作業(yè)車(chē)間調(diào)度問(wèn)題（JSP）－算法介紹

混合算法（GA＋TS）求解作業(yè)車(chē)間調(diào)度問(wèn)題（JSP）－禁忌搜索部分

代碼下載請(qǐng)關(guān)注公眾號(hào)，后臺(tái)回復(fù)【FJSPHA】即可，不包括【】

代碼框架

代碼分為5個(gè)包，第一部分Data為用到的各類(lèi)結(jié)構(gòu)，第二部分GA為GA部分＋第一個(gè)TS，第三部分主函數(shù)，第四、五部分是兩個(gè)TS。

算例放置在input文件夾中，這里準(zhǔn)備了Mk系列算例，Kacem系列算例和論文中的簡(jiǎn)單算例test．txt。

Main

算例輸入：

Main中還有一個(gè)輸出為CSV的函數(shù)，需要一個(gè)jar包，已經(jīng)放在下載鏈接里了，不需要的同學(xué)也可以刪除。

Data

一堆亂七八糟的結(jié)構(gòu)。這里簡(jiǎn)單講一下Solution類(lèi)和Graph類(lèi)。

Solution類(lèi)中包含多個(gè)print函數(shù)，比較重要的包括繪制甘特圖以及check解是否合法。

operationMatrix是解的主題，存放某個(gè)工件的某道工序的開(kāi)始、結(jié)束時(shí)間，所在加工機(jī)器。

Graph類(lèi)表示析取圖。nodeList是每臺(tái)機(jī)器上的node。其中起始點(diǎn)、終止點(diǎn)我單獨(dú)提取出來(lái)設(shè)置了兩個(gè)類(lèi)。Graph中還包含了獲取critical path的DFS和update starting time ＆ end time的Bellman算法。

GA

MyHybridAlgorithm類(lèi)是GA的主函數(shù)。小編在實(shí)現(xiàn)的時(shí)候進(jìn)行了多種測(cè)試，比如迭代的noImprove次數(shù)達(dá)到limit時(shí)進(jìn)行擾動(dòng)：

選擇哪種Tabu：

讀者在閱讀的時(shí)候請(qǐng)自己注意。

算法相關(guān)的參數(shù)我都做了初始化，請(qǐng)自行查找修改：

交叉、變異等操作包含在ChromosomeOperation類(lèi)中，計(jì)算適應(yīng)度的函數(shù)在CaculateFitness類(lèi)中，TabuSearch1類(lèi)是基于編碼的tabu，這里都不多展示了。

NeighbourSearch

這個(gè)包包含的是基于析取圖的tabu。NeighbourAlgorithms類(lèi)相當(dāng)于Main，包含解轉(zhuǎn)化為圖的函數(shù)：

TabuSearch2類(lèi)為tabu主函數(shù)。NeighbourGraph類(lèi)存放析取圖鄰域搜索產(chǎn)生的解。

DeleteNeighbourGraph類(lèi)為析取圖中暫時(shí)去掉某個(gè)點(diǎn)后的情況，PM、PJ、SM、SJ代表precede、succeed、machine、job四條邊對(duì)應(yīng)的點(diǎn)，deleteNode為刪去的點(diǎn)。

其中還有findLandR位置的二分查找函數(shù)，insert時(shí)的估值函數(shù)：

NeighbourSearch2

這個(gè)包為第三個(gè)基于甘特圖的tabu。

RTS類(lèi)為tabu的主函數(shù)。解通過(guò)：ArrayList＜ArrayList＜Operation＞＞ 的形式表示。

replan函數(shù)中包含了在甘特圖上進(jìn)行swap操作后更新解的方法，有詳細(xì)注釋?zhuān)?/p>

總結(jié)

到這里已經(jīng)大致梳理了一遍代碼，但其中還有很多細(xì)節(jié)沒(méi)有講到，包括很多東西實(shí)現(xiàn)的不好，歡迎隨時(shí)和我交流。

由于是自己研究時(shí)寫(xiě)的代碼，其中很多東西會(huì)比較亂，但是代碼中做了很多注解，仔細(xì)閱讀應(yīng)該能看得懂的！

下載的壓縮包里包括我學(xué)習(xí)過(guò)程中看過(guò)的大部分文獻(xiàn)，包括主要參考的文獻(xiàn)，大家可以進(jìn)一步閱讀研究。