Deconstructing Nowicki and Smutnicki's ii-TSAB tabu search algorithm for the job-shop scheduling problem

Over the last decade and a half, tabu search algorithms for machine scheduling have gained a near-mythical reputation by consistently equaling or establishing state-of-the-art performance levels on a range of academic and real-world problems. Yet, despite these successes, remarkably little research has been devoted to developing an understanding of why tabu search is so effective on this problem class. In this paper, we report results that provide significant progress in this direction. We consider Nowicki and Smutnicki's ii-TSAB tabu search algorithm, which represents the current state-of-the-art for the makespan-minimization form of the classical job-shop scheduling problem. Via a series of controlled experiments, we identify those components of ii-TSAB that enable it to achieve state-of-the-art performance levels. In doing so, we expose a number of misconceptions regarding the behavior and/or benefits of tabu search and other local search metaheuristics for the job-shop problem. Our results also serve to focus future research, by identifying those specific directions that are most likely to yield further improvements in performance.