专栏首页程序猿声混合算法(GA+TS)求解作业车间调度问题代码解读+完整JAVA代码

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

代码框架

代码分为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操作后更新解的方法,有详细注释:

总结

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

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

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

参考

[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.

本文分享自微信公众号 - 程序猿声(ProgramDream),作者:舟寒丶

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    短短的路走走停停
  • 遗传算法求解混合流水车间调度问题(附C++代码)

    各位读者大家好,好久没有介绍算法的推文了,感觉愧对了读者们热爱学习的心灵。于是,今天我们带来了一个神奇的优化算法——遗传算法!

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

    一道工序一旦开始加工,就不能中断。每台机器一次只能加工一道工序。在初始加工时刻,所有工件和机器都是可用的。

    短短的路走走停停
  • 转载 | 遗传算法求解混合流水车间调度问题(附C++代码)

    各位读者大家好,好久没有介绍算法的推文了,感觉愧对了读者们热爱学习的心灵。于是,今天我们带来了一个神奇的优化算法——遗传算法!

    短短的路走走停停
  • 干货 | Tabu Search求解作业车间调度问题(Job Shop Scheduling)-附Java代码

    还是在朋友圈里一边喝着洗衣粉一边计划着晚上裸奔,想要出轨结果表白被拒,狠下心决定今晚谁追自己就答应谁?

    短短的路走走停停
  • APS智能排产+运筹优化算法=?

    供应链高级计划相关业务涉及预测计划,采购计划,产能规划,人力计划,MPS/MRP,主生产计划,工序计划,装车计划,配送计划等软件模块,覆盖中长期计划与...

    用户1621951
  • 作业车间调度JSP与遗传算法GA及其Python/Java/C++实现

    最近小编接触了遗传算法(Genetic Algorithm)。关于遗传算法,公众号内已经有多盘技术推文介绍:

    短短的路走走停停
  • 干货|遗传算法解决带时间窗的车辆路径规划问题(附java代码及详细注释)

    各位读者大家好,今天小编给大家分享如何用遗传算法求解带时间窗的车辆路径规划问题。算法的主要思想来自于论文:A simple and effective evol...

    用户1621951
  • TiDB 3.0 GA,稳定性和性能大幅提升

    TiDB 是 PingCAP 自主研发的开源分布式关系型数据库,具备商业级数据库的数据可靠性,可用性,安全性等特性,支持在线弹性水平扩展,兼容 MySQL 协议...

    PingCAP

扫码关注云+社区

领取腾讯云代金券