A priority list based heuristic for the job shop problem: part 2 tabu search

Abstract

Following a recent paper by the same author, a priority list-based tabu search heuristic is compared with the leading schedule-based tabu search heuristic of Nowicki and Smutnicki. More search neighbourhoods are required to achieve a given average makespan, but each priority list neighbourhood is searched much faster than the corresponding neighbourhood in the space of feasible schedules. Priority list-based tabu search therefore outperforms schedule-based tabu search in terms of elapsed CPU time.

Keywords:

• scheduling
• heuristics
• job shop problem
• tabu search
• priority lists