Applying tabu search to the job-shop scheduling problem

In this paper, we apply the tabu-search technique to the job-shop scheduling problem, a notoriously difficult problem in combinatorial optimization. We show that our implementation of this method dominates both a previous approach with tabu search and the other heuristics based on iterative improvements.Partially supported by research contracts MPI 40% and 60% of the Italian Ministry of University and Scientific Research.