No-wait shop scheduling: Computational complexity and approximate algorithms

In this paper some of the recent results in deterministic no-wait shop scheduling are presented. In no-wait manufacturing environment, products or jobs must be processed, from their start to their completion, without any interruption on or between machines. This restriction may be due to the absence of intermediate storage capacity, or may be due to the processing technology itself. A number of shop models and objective functions have been considered in the paper in relation to the no-wait shop scheduling problem. The computational complexity of the various no-wait shop scheduling problems has been investigated. Approximate algorithms for the hard problems are presented and the worst case performance of these algorithms is discussed.