求解车间作业调度问题的快速禁忌搜索算法

Fast taboo search algorithm for solving job shop scheduling problems

针对车间作业调度问题的难解性 ,提出了一种求解该问题的快速禁忌搜索算法 .该算法是按照禁忌搜索算法的一般步骤来进行设计的 ,在设计过程中对于算法所涉及到的初始解问题、邻域构造问题以及禁忌表长度的选取等问题给出了旨在减少算法计算时间 ,提高算法优度的解决方案 .该算法找到了所测试的 2 1个标准算例中 1 8个算例的精确最优解 ,而且在PⅡ 2 3 3的计算机上每个算例的计算时间不超过 2s.

The fast taboo search algorithm was designed according to steps of the taboo search algorithm. As for the initial solution problem, neighborhood structure problem and taboo table length problem, the solution was made to decrease the compute time of the algorithm. The taboo search algorithm could solve 18 instances among 21 instances tested, and each instance took no more than 2 seconds on a personal computer with a PⅡ 233 CPU.