求解Job-Shop调度问题的禁忌搜索算法的研究

Research on a Tabu Search Algorithm for Solving Job-Shop Scheduling

本文针对最小完工时间的Job-Shop调度问题提出了一种禁忌搜索算法,该算法使用插入算法构造尽可能好的初始解,然后用禁忌搜索算法改进当前解,在算法中对未被选中的候选解信息进行记忆,合理平衡了集中搜索与分散搜索。最后用基准实例进行仿真,实验结果表明该算法是可行的和有效的。

This paper presents a tabu search algorithm for solving the minimum makespan problem of Job-Shop scheduling. In the algorithm, an insertion method is used to create the initial solution and then the tabu search algorithm is applied to improve the last solution. The information of the unvisited candidate solutions is recollected, intensive search and dispersive search are reasonably balanced. Computer simulation experiments on a set of benchmark instances show that the algorithm is applicable and effective.