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

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

是在家摆瓜子呢：

还是在数羊呢：

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

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

开 · 始 · 学 · 习 吧！

有一个可恶的老板觉得一直写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代码。