Flowshop and Jobshop Schedules: Complexity and Approximation

Abstract

We show that finding minimum finish time preemptive and non-preemptive schedules for flow shops and job shops is NP-complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained.