求解车间调度问题的双禁忌表禁忌搜索算法

刘胜辉　李小阳　张淑丽

摘要：针对车间调度问题的特点，为解决传统禁忌搜索算法容易陷入局部最优解的问题，提出一种求解车间调度问题改进的禁忌搜索算法一双禁忌表禁忌搜索算法，该算法通过建立双禁忌表避免在搜索最优解时出现循环的现象，通过该算法与TSAB算法进行比较可知，该算法具有较强的寻优能力。

关键词：车间调度；启发式算法；禁忌搜索；禁忌表；邻域

DOI：10.15938/j.jhust.2016.06.010

中图分类号：TP301

文献标志码：A

文章编号：1007-2683（2016）06-0050-05

0.引言

车间调度JSP（J0b Shop scheduling）问题是一种NP-hard问题，由于其本身问题比较复杂，加之要解决的问题规模比较大，有些问题不能求出一组最优解，只能求出次优解，或者近似最优解，启发式方法较适合求解这类问题，禁忌搜索算法是一种有效的求得全局最优解的启发式算法，其优点是有灵活记忆的功能，当搜索陷入局部最优解时能够跳出；其缺点是对初始解的依赖较强，一个好的初始解往往能够得出一个比较好的结果，当产生某一个最优解时，常常因为这个最优解产生循环，而此时我们要跳出循环，本文提出一种新的禁忌搜索算法一双禁忌表禁忌搜索算法，用以解决在产生最优解的同时容易出现循环的问题。

1.问题描述

JSP问题实际上是安排n个工件在m台机器上加工使工件的加工时间最短，而且每一个工件都有若干道工序，每道工序有指定的加工顺序，固定机器上工件的工序有各自的加工时问.每一个工件都是独立的，也就是说一个工件在某一时刻只能被一台机器加工，并且某一时刻每台机器只能加工一个一个工件，加工期间不允许被中断，每个工件不能在同一台机器上加工多次，最终的目标是使工件完工时间最小。更具体的，问题可以形式化描述成一种JSP调度模型，工件集：J={1，2，…，n}；机器集：M={1，2，…，m}；加工时间矩阵用T表示，机器j上工件i的加工时间用T表示；机器的加工顺序矩阵J_M，加工工件i第j个操作的机器编号用jm（i，j）表示，j_m（i，·）表示要工件i所有操作按优先级顺序加工的各机器号的排列；工件排列矩阵M_i，其中M_i（i，j）表示在机器i上加工的第，j个操作的工件号，M_i（i，·）表示在加工机器i上依次加工的各工件号的排列；工件i在机器，j上的完工时间C（i，j）

1）工件的加工时间矩阵T为常数矩阵，也就是说每个工件的各个操作加工时间T_tj是已知的，并且均为常数；

2）加工顺序矩阵J_M是已知的，也就是说加工每个工件各个工序的加工，必须在指定的机器上；

3）同一台机器上每个工件只能加工一次，也就是说同一台机器上不允许出现循环加工某个工件的现象；

2.算法设计

2.1邻域设计

本算法基于禁忌搜索算法，并采用两个禁忌表.由于当邻域规模比较大时，只试走一步，在规定的时间内，很容易陷入局部最优解，要采取一种策略使搜素的范围更广一些，并且所用的时间并不是很大.那么在规定一个可行解的情况下，对每两个连续的移动用禁忌搜索得到一个可行解，然后从这些可行解当中选一个最好的解，当作下一次迭代过程的起点，重复以上过程直到不能得到更好的调度解则停止，更具体的描述如下：

JSP问题的完工时间取决于关键路径长短，在一个可行调度解中如果工序之间的时间间隔为0，最长的路径被称为关键路径，我们的工作就是如何减少关键路径的长度.如图1中关键路径为（1，1）（2，1）（1，3）（1，4）（2，2）（3，2）（1，6），图1中调度为单一关键路径，当然可能出现多个关键路径.在关键路径上，有块的定义，在图1中有3个块分别是B1.B2.B3。

移动的定义每个关键块在Nowicki和Smutnicki的定义的基础上，有以下几点有所不同：

1）若关键块B是关键路径上第一个关键快，那么要交换的是关键块B上的最后两个工序61和62；

2）若关键块B是关键路径上的尾块，则要交换关键块B的前两个工序和α₁和α₁

3）另外的关键块B，交换前两道工序α₁和α₁和最后两道工序b₁和b₁，具体的操作如图1所示.

这些移动构成了移动集合p（s），令g（s，p）来表示通过对s运用一次移动而获得的一个可行解，那么s的邻域N（s）={g（s，p）：p∈p（s）}.之所以这样定义邻域的原因是，每个关键块只增加了两个移动，并没有极大的增加计算量。

2.2禁忌表

在传统的Ts算法中，禁忌表T所记录的是移动.也就是说在满足定义的邻域前提下，从一个可行解到下一个可行解的移动是交换工序i和j，那么有序对（i，j）被记录在禁忌表T中，它的意思是在接下来的一次移动中，不能再进行工序i和j的交换，禁忌表并不能把每一个可行解都保存，鉴于此设置一个禁忌表长度，禁忌表长度是指接下来的迭代不能再回到禁忌元素的最大步數，每一个新的移动都会被加到禁忌表最后的位置，随之最前面的移动被删除，但这就会形成一个问题，当某个移动被删除的时候，此移动还可能在某次迭代时被使用，因为此时该移动已经不在禁忌表中了，为了解决这一问题，采用双禁忌表的策略，两个禁忌表分别为SHORT-T和LONG-T（如图2所示），其中T₁，T₁…T_i，…T_n=（（α₁，α₂），（α₃，α₄））…（（α_i，α_i），α_m，α_n））表示移动，SHORT-T用来存放当前搜索到并且需要禁忌的解（移动），当满足迭代次数的迭代之后，并不是将所有禁忌的解直接释放，而是将普通的解从SHORT-T中释放，而通过移动产生最优解的移动则放入LONG-T中.LONG-T存储的是历史最优解，在LONG-T更新时，若当前解，与LONG-T中的解相同时，则说明出现了循环，可以允许出现一定的循环，但是循环达到一定次数的话，就要重新产生初始解而跳出循环.这么做的原因是，当通过迭代产生循环时，最容易产生循环的是产生最优解的移动而导致的循环，而且在最优解上产生的循环是不能容忍的，特别要强调的一点，SHORT-T存放的是移动，LONG-T存放的是历史最优解。

2.3逆排时技术

给定一个排时问题实例E和它的开工顺序，把工件的开工顺序和加工顺序倒过来得到另外一个可行解，例如给定的加工顺序（o（1），o（2）…，o（n）），计算得到倒转后的实例得到的加工顺序为（o（n）….，o（2），o（1），计算倒转后的每项工作的开始时间和最大完工时间。

举个例子，给定加工时间矩阵T_ij和加工顺序矩阵R_ij其中：

3.实例验证

算法在linux环境下使用c语言进行实验，实验环境为，CPU i3处理器，内存lG.Benchmark算例是国际上通用的算例，能够反映一个算法的优劣，对于35个Benchmark问题，将本文算法与TSAB算法进行比较计算得到makespan。

在合理的时间内，应用本算法有23个相同，并且是最优解，说明本算法对于大部分的算例能够计算出最优解是可行的，有10个优于TSAB算法得到的解更接近最优解，有两个与TSAB算法相比得到的解较差，从总体来说大部分的解都优于或者与TSAB算法的解相同，只有两个解稍差，说明本算法有一定的优越性，结果不同的算例为FTl0，LAl6，LA22，LA24，LA25，LA27，LA29，LA36-LA40，其中与TSAB算法对比makespan表不同的实例如表1所示。

衡量车间调度问题算法的优劣的标准一般有两个，分别是计算机时间和得到的最优解，本算法在计算时间上和TSAB算法基本相同，但是在寻优能力上比TSAB算法更强，由表1可画出如图6的折线图，从图6中可直观看出本算法更接近最优解，表明本算法有一定的寻优能力，并且可有效提高解的质量。

4.结论

本文通过从JSP问题的搜索邻域人手，提出了一种新的禁忌表的搜索算法，减少了算法在达到历史最优解的时候产生的循环，从而提高了禁忌搜索算法的优化效果，通过对benchmarks实例进行测试，验证了本文提出的设计算法有一定的寻优能力.当出现在作业车间调度中临时加入一些工件工序的情况是下一步研究的内容，同时在数据量非常大的情况下，如何提高效率是研究的另一个方向。