变邻域结构Tabu搜索算法及其在JobShop调度问题上的应用

本文针对最小化完工时间的Job Shop调度问题提出一种变邻域结构Tabu搜索算法,该算法使用的邻域结构随算法的进程而改变,不仅邻域规模小,而且仍保持了可达性这一重要的属性.对不同规模的实例进行了数值计算,计算结果表明,该算法具有非常高的效率,且初始解对算法的影响很小.

Tabu Search Algorithm with Varying Neighborhood and Its Application to Job Shop Scheduling Problem

This paper presents a tabu search algorithm with varying neighborhood for Job Shop scheduling problem of minimizing the makespan.The neighborhood used can be changed with the process of the algorithm,and the scale of the neighborhood is not only small,but also the reachability can be kept.The computational results of different scale problems show that the efficiency of the algorithm is high ,and that the influence of the initial solution on the algorithm is small.