Open Shop Scheduling to Minimize Finish Time

Abstract

A linear time algorithm to obtain a minimum finish time schedule for the two-processor open shop together with a polynomial time algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-complete.