关键词: Job-Shop调度 禁忌搜索 最小完工时间

Abstract:

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 candida  te 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.

Key words: （Job-Shop scheduling, tabu search;minimum makespan）