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．