Group for Research in Decision Analysis


On the Complexity of Preemptive Openshop Scheduling Problems


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