No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems

This paper deals with the no-wait job shop problem with a makespan objective. We present some new theoretical properties on the complexity of subproblems associated with a well-known decomposition approach. Justified by the complexity results, we implement a fast tabu search algorithm for the problem at hand. It is extensively tested on known benchmark instances and compares favorably to the best existing algorithms for the no-wait job shop as well as the no-wait flow shop. Copyright Springer-Verlag 2006