混合算法(GA+TS)求解作业车间调度问题代码解读+完整JAVA代码

程序猿声

共 2359字,需浏览 5分钟

 ·

2020-08-11 15:27


程序猿声

代码黑科技的分享区

 


前两篇文章中,我们介绍了FJSP问题,并梳理了一遍HA算法。这一篇文章对小编实现的(很乱很烂的)代码进行简单解读。


往期回顾:

种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍

混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分


代码下载请关注公众号,后台回复【FJSPHA】即可,不包括【】


代码框架



代码分为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> 的形式表示。


replan函数中包含了在甘特图上进行swap操作后更新解的方法,有详细注释:



总结


到这里已经大致梳理了一遍代码,但其中还有很多细节没有讲到,包括很多东西实现的不好,欢迎随时和我交流。


由于是自己研究时写的代码,其中很多东西会比较乱,但是代码中做了很多注解,仔细阅读应该能看得懂的!


下载的压缩包里包括我学习过程中看过的大部分文献,包括主要参考的文献,大家可以进一步阅读研究。


参考


[1]Li, Xinyu , and L. Gao . "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem." International Journal of Production Economics 174.Apr.(2016):93-110.

[2]Zhang, Chao Yong , P. G. Li , and Y. R. Zailin Guan . "A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem." Computers & Operations Research 34.11(2007):3229-3242.

[3]Mastrolilli, Monaldo , and L. M. Gambardella . "Effective Neighbourhood Functions for the Flexible Job Shop Problem." Journal of Scheduling 3.1(2015):3-20.

[4]Zhang, Guohui , L. Gao , and Y. Shi . "An effective genetic algorithm for the flexible job-shop scheduling problem." Expert Systems with Applications 38.4(2011):3563-3573.


推荐阅读:

干货 | 想学习优化算法,不知从何学起?

干货 | 运筹学从何学起?如何快速入门运筹学算法?

干货 | 学习算法,你需要掌握这些编程基础(包含JAVA和C++)

干货 | 算法学习必备诀窍:算法可视化解密

干货 | 模拟退火、禁忌搜索、迭代局部搜索求解TSP问题Python代码分享

记得点个在看支持下哦~
浏览 29
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报