专栏首页程序猿声干货 | Tabu Search求解作业车间调度问题(Job Shop Scheduling)-附Java代码

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

假期突然多出好多天,大家有没有感觉特别无聊?

是在家摆瓜子呢:

还是在数羊呢:

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

不如和小编一起,做一个安静的美男子,

开 · 始 · 学 · 习 吧!

有一个可恶的老板觉得一直写TSP、VRP问题非常无聊,打算引入一个新问题:作业车间调度问题(Job shop scheduling problem, JSP) 。前两天其实已经提到过JSP,这次小编再详细解读一下JSP,带来一段禁忌搜索算法求解JSP的Java代码,帮大家消磨这段 无 · 聊 的时间~

01

作业车间调度问题

问题描述

一个加工系统共有m台机器,需要加工n个加工顺序不同的工件。

已知:(1) 工件集 ,其中为第个工件,;

(2) 机器集为第j号机器,j=1,2,…,m;

(3) 工序集为工件的工序序列。为第i个工件的第k道工序使用的机器号,表示工件在第k道工序不加工,

(4) 每个工件使用每台机器的时间矩阵为第个工件使用第台机器的时间。表示工件不使用机器j。

JSP需要满足下列约束条件: (1) 每个工件使用每台机器不多于1次; (2) 每个工件利用每台机器的顺序可以不同,即可以有; (3) 每个工件的工序必须依次加工,后工序不能先于前工序;(4) 任何工件没有抢先加工的优先权,应服从任何生产顺序; (5) 工件加工过程中没有新工件加入,也不临时取消工件的加工。

调度目标通常是最小化最大完工时间,即。式中表示工件的完工时间。对于以上描述的调度问题,调度算法的任务就是在许可的计算时间内得到最优或是较优的加工顺序。

问题模型

令表示作业的第个工序。和分别表示的加工起始时刻和加工时间。表示是否在第台机器上加工:如果在第台机器上加工,;否则,,为第台机器的完工时间,则问题的数学模型如下:

公式(1)为目标函数,即优化目标,系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。

哎,小编看到数学公式就难受的毛病又犯了。

没关系,我们接下来举个栗子。

举个栗子

假如此时有3个工件需要再3台机器上加工,不同工件所需的加工工序及加工时间可以用以下公式表示:

在这个例子中,作业有3道工序:它的第1道工序上标注有(0,3),表示第1道工序必须在第0台机器上进行加工,且需要3个单位的加工时间;它的第2道工序上标注有(1,2),其表示第2道工序必须在第1台机器上进行加工,且需要2个单位的加工时间;余下的同理。总的来说,这个实例中共有8道工序。

下图用甘特图表示了一种可行解:

相信大家看了这个栗子后,大概能明白JSP要求的是什么了。这时候再注意一下前文问题描述中的几个点,就可以开始动手解决啦!

02

禁忌搜索算法

有关禁忌搜索算法的内容,公众号内有详细教程:

干货 |【算法】禁忌搜索算法(Tabu Search,TS)超详细通俗解析附C++代码实例

干货 | 到底是什么算法,能让人们如此绝望?

禁忌搜索算法求解带时间窗的车辆路径规划问题详解(附Java代码)

大家可以点击超链接回顾相关知识,这里就不再细说了。

一般而言,用禁忌搜索算法解决问题时,需要注意的点无非就是以下几个:初始解的生成;禁忌对象的选择;邻域动作算子的选择。

我们简单介绍代码中使用的算子:

Neighbor1类:对同一机器上的两道相邻工序,交换两道工序的前后顺序。例如交换图例中中和的顺序。交换后,上的加工顺序为{}。

NeighborA类:对同一机器上的三道不同的工序,满足和相邻,或与相邻。找到最早开始加工的工件的位置,按的顺序加入处。例如图例中的三道工序,交换后的加工顺序为{}。

禁忌表为「工序总数*工序总数」大小的二维表。对Neighbor1,禁忌边();对NeighborA,禁忌边。

如果所有边都被禁忌,随机选择某一组工序进行变换。

若执行邻域动作后的新解优于历史最优解,则不会被禁忌表禁忌。

03

代码展示

代码是github上的开源代码,作者是Thiebout Dewitte。具体代码比较长,讲解需要花很长的篇幅,但是注解比较详细,因此就不在此展示了。我们简单介绍一下输入输出,感兴趣的朋友可以文末看到下载方式,自行下载研究。

输入部分

输入算例格式如下:

第一行为注释部分,第二行数字分别为工件数、机器数。

输出部分

运行代码时,可以多种运行方式:

在Main.java文件内选择所需运行模式,算例设置也在同一文件中。

测试单一算例:使用opendeurdagKulak()方法。将测试算例路径放入Main.java中:

测试算例附带在代码内。 结果生成在编译器内部:

前三行按照机器顺序排列,cost表示总耗时,最后一行表示最长耗时的加工顺序。

测试多个算例,分别生成table1、2:

在上方输入算例所在文件夹,下方输入输出部分文件名。 table输出可放置在LaTeX环境中,在此就不展示了。

代码下载

进入公众号输入【JSPTS】不带【】,即可下载对应Java代码。

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货 | 到底是什么算法,能让人们如此绝望?

    今天的任务是去给山顶的人家化斋,在爬山算法的帮助下,终于顺利爬到了最高点!阿弥陀佛~~⬇⬇⬇

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

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

    短短的路走走停停
  • 10分钟教你Python爬虫(下)--爬虫的基本模块与简单的实战

    各位看客老爷们,新年好。小玮又来啦。这次给大家带来的是爬虫系列的第二课---爬虫的基本模块与简单的实战。

    短短的路走走停停
  • 遗传算法求解混合流水车间调度问题(HFSP)一:问题介绍

    混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP)是车间调度中的一类经典问题。混合流水车间调度问题,在一...

    mwangblog
  • PHP 使用 ElasticSearch 做搜索

    lasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsearc...

    双面人
  • ssdb 主从同步复制配置详细步骤

    有时我们在使用数据库时,像mongodb,redis和一些关系行数据,为了使数据更加安全,作为备份使用我们经常习惯使用主从复制架构,当主机上的数据出现问题时...

    用户5166556
  • Golang leetcode 476. Number Complement.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175283...

    anakinsun
  • WPF 列表自动换行

    本文告诉大家如何在 ListView 或 ListBox 使用 WrapPanel 让里面的控件自动换行

    林德熙
  • 智商145!比利时神童9岁读完大学,成史上最年轻大学毕业生

    9岁的时候你在做什么?说出来可能会暴露年龄,我们这一代9岁的时候还在玩捉迷藏、看“大风车”呢。

    昱良
  • 教你如何在 IDEA 远程 Debug ElasticSearch

    之前在 源码阅读环境搭建文章 中写过我遇到的一个问题迟迟没有解决,也一直困扰着我。问题如下,在启动的时候解决掉其他异常和报错后,最后剩下这个错误一直解决不了:

    zhisheng

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动