Group for Research in Decision Analysis

G-90-36

On the Complexity of Preemptive Openshop Scheduling Problems

and

We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functions, we show that the minimum mean flow time problem with ready times and job preemption is unary NP-hard, in the two machine case.

, 17 pages

This cahier was revised in August 1991