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

程序猿声

代码黑科技的分享区

大家好，在上一篇文章中，我们介绍了FJSP问题以及HA算法的GA部分。这一篇文章主要介绍嵌套在其中的Tabu Search部分。

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

Tabu部分原论文没有很详细的描述，因此很多内容是小编收集各方资料，查阅其他相关文献总结出的结论，小编自己编写了三个tabu search，在这里分别分享介绍一下。如有专门研究这块的同学，欢迎随时指点交流！

代码会在下一期统一给出，请关注我们！

Tabu1-基于编码

在之前的文章中说过，算法对每一代子代的每一个个体，都需要decode成可行解，然后运用禁忌搜索优化解，再编码回GA编码，进入下一代。可想而知，如果tabu写的不好，算法的耗时肯定会很高。

论文中的tabu其实是以第二种为主体的。基于编码的tabu相对而言比较盲目，当初编写时也是基于试一试的心态。

前文提到，对一串合法的OS序列，无论进行怎样的交换、插入运算，都可以解码成可行解；对MS序列，在同一工件范围内任意交换顺序，也可以保证得到可行解。

因此，小编在代码中简单设计了两种邻域：

1. 对相邻的OS编码进行交换操作；

2. 对MS编码的每个位置分别采用GA中的变异操作。

swap很简单，再重复一下MS的变异：

随机选择MS中一半的数字，随机换为对应操作可以选择的某个机器。例如图中长度为6的MS String，随机选择三个位置，对O11而言，共有三个机器可选择，则随机选择1，2，3中一个数字替换掉原先的2。

邻域部分代码（开启了一个50%的采样）：

for (int i = 0; i < chromosome.gene_OS.length - 1; i += 2) 
 for (int j = i + 1; j < chromosome.gene_OS.length; j += 2) 
  if(r.nextDouble() < 0.5)
   OSs.add(swap(chromosome.gene_OS, i, j));

for (int i = 0; i < chromosome.gene_MS.length; i++) 
 if(r.nextDouble() < 0.5){
  int[] MS = chromosome.gene_MS.clone();
  MSs.add(chromOps.machineSeqMutation(MS));
 }

结论：这个邻域设计的比较随意，但经过小编的测试后发现效果不佳，小编在这里建议大家不要使用基于编码的邻域搜索。

Tabu2-基于析取图的k-insertion

析取图

对JSP和FJSP来说，除了用甘特图表示解意外，还有一个很重要的表示解的结构：析取图。

析取图是一张有向图。图中的点表示工序，边代表工序加工的顺序。

边有两种类型，一种是machine arc（也叫disjunctive arc），由同一机器上的前一道工序指向相邻的后一道工序。图中彩线部分表示machine arc。另一种是job arc（也叫conjunction arc），由同一工件上的前一道工序指向相邻的后一道工序。图中黑色实现部分代表job arc。两种边分别表示machine 和job的两个约束，因此一个点最多引申出4条边。

除此之外，图中还有两个超级源点，起始点和终止点（图中的0号start和10号finish）。他们是虚拟的点，代表加工开始和结束。Start点只有job arc，分别连向每个工件的第一道工序；Finish 点也只有job arc，从每个工件的最后一道工序连接到此点。（要注意边的顺序！）

图中的边上没有权值，权值存放在点上，代表加工时间。起始、终止点加工时间为0。

读到这里大家应该能感受到，一幅图实际上已经代表了一个解。点（即工序）的加工开始、结束时间都可以通过最长路算法得出。整个schedule的最大makespan（加工时间）就是起始点到终止点的最长路距离。如果这幅图里没有环，则解可行；否则为不可行解。

这里的最长路又称为critical path（关键路径），即图中粉色框框起的部分。

最长路的算法小编没有找到很好的资料，自以为可以用DFS写，如果在邻域算子后要进行全部工件starting time的更新，那么可以使用bellman-ford算法，这些在小编的代码里都有实现。

结论：很多JSP、FJSP论文的tabu search都是基于析取图进行的，因为可以使用图的特性，毕竟容易操作。

k-insertion

相较于JSP，小编能查到的FJSP的邻域较少，这一部分主要参考一篇2000年的论文 “Effective neighbourhood functions for the fexible job shop problem”，讲解其中的k-insertion邻域。

k-insertion其实就是一个insert操作，简单来说就是将critical path中的每一个操作，分别插入到其他可加工机器的某个位置，形成新解。这里强调，无论什么邻域搜索，一定要在critical path上做文章，才容易改变解的makespan。

实际上，并不是一个机器上的所有位置都需要插入的。如果一道工序由于job边约束，加工时间在考前的位置，那么插入某台机器靠后的位置显然不会使加工时间缩短。考虑到这一点，我们只需要挑出可能使结果更优的位置，执行插入操作。

论文中对每个机器上的工序根据starting time（开始加工的时间）进行排序，然后根据公式计算出两个边界：L_k， R_k。再通过二分查找找到这两个位置。经过证明，只有两者的并集（图中中间的部分）插入后可能优化结果。这里的计算公式需要定义一些新变量，难度不大但是不好讲清，想要深入研究的同学可以下载代码、论文进一步研究，这里暂时不多说了。

前面我们反复强调，我们的tabu是要嵌入到每一个个体中的，因此计算速度一定要快。如果对TS的每一个解都精确运算出makespan，速度会很慢（第一个tabu就是这样的）。因此，我们需要特殊的估值方法。

论文中的估值是一个上界。只需要根据前文定义的一些变量进行简单的加减乘除运算即可得出，极大优化了时间复杂度。这里同样不多解释。

然而，在实现析取图的k-insertion后，小编发现自己实现的速度依旧很慢，嵌入个体后算法根本跑不动。因此小编尝试了一下GA和TS的并行操作，用GA的初始解进行TS操作，发现结果却是有优化，但是时间还是太久。小编目前也找不到代码资料，只能自行编写，因此陷入瓶颈。有了解这块的同学可以和小编进一步交流！

这里再提一句，JSP、FJSP的tabu禁忌表可以用插入或交换前后的的位置，制作一个二维表来表示，用单纯的解作为禁忌对象会拖慢速度。

结论：Tabu2效果不错，但是可能是因为析取图部分没有写好，时间容易爆炸。

Tabu3-基于甘特图的JSP N1邻域

前面的tabu2是一种FJSP的邻域结构，搜索的是插入不同机器的解空间。如果不插入不同机器呢？

很显然，问题转化为JSP。

因此，小编在咨询了一些专业人士后，打算尝试加入JSP的tabu search。

JSP的tabu邻域比FJSP多一些，比较知名的有N1，N4，N5，N6等邻域（参考：A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem）。小编目前简单实现了N1的邻域，通过类似甘特图的形式作为解的结构。

在介绍N1之前还要提到一个critical block的概念。在critical path中，如果有若干个连续的工序是在同一机器上加工的，则称其为一个critical block。很多tabu邻域都是在critical block内进行操作，包括这里说的N1。

N1的邻域为：在所有critical block内，交换两个相邻工序在机器上的加工位置。

由于甘特图的形式表示解没有图的性质，因此计算makespan、更新starting time的方法和析取图中又有所不同。简单来说，需要像GA中查找空闲时间区间一样不断插入，然后更新时间。

简单实现后说下小编实现+测试后的结论：时间上勉强可以接受，不至于跑不出来；但是解的质量不够理想。但至少说明嵌入个体是可行的。

这里提供一个进一步改进的思路：将第三部分的JSP的tabu邻域和第二部分的k-insertion结合起来，因为我做第三部分的时候没有写成析取图，所以这部分没有做。结合之后还要将第二部分进一步改进，至少时间上要缩短，再嵌入到个体中。

Tabu部分大致就介绍到这里，剩下还会有一篇具体讲解小编实现的代码。讲解有些地方不够详细，要具体研究的小伙伴还是推荐好好研读论文。

参考

[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代码分享

记得点个在看支持下哦～