变异OS

OS的变异有两种方法，交换式和邻域式。

交换式即随机选择两点交换位置。

邻域式则是选择三个点，组成种情况，再随机选择其中一种。

选择

选择可以有多种方法。精英选择，锦标赛选择，轮盘赌选择。这里介绍论文里使用的前两种。（小编的代码中三种都有写）

精英选择：直接按适应度排序，取最优的几个。

锦标赛选择：每次随机选择k个子代（k一般在2～6之间，论文里采用k＝2），选出其中最优的一个。

论文里采用精英选择＋竞标赛选择的方法。

禁忌搜索算法部分

禁忌搜索算法部分是嵌套在GA中的。按原论文的说法，对每一代子代的每一个个体，都需要decode成可行解，然后运用禁忌搜索优化解，再编码回GA编码，进入下一代。（听起来就觉得时间复杂度蛮高的）

除了甘特图外，JSP ／ FJSP还有自己的一套表示解的方法，称为析取图。简单来说，就是把工序作为点，前后加工关系作为边，以此表示工序的加工顺序。

如前文所说，由于嵌套至每一个个体，算法的运行时间很容易爆炸，多写一个循环都会产生不可估量的后果。同时，原论文在这一部分没有很详细的描述，因此小编在复现这一部分的时候也没有处理的很好，来来回回写了多个Tabu Search。由于篇幅原因，这一部分暂时留到下期讲，后续应该还会对小编的代码进行简单讲解，请大家多多关注！

关于甘特图的画法，可以参照：

10分钟用Python或MATLAB制作漂亮的甘特图（Gantt）

参考

［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．