Groupe d’études et de recherche en analyse des décisions

G-90-36

On the Complexity of Preemptive Openshop Scheduling Problems

et

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

Ce cahier a été révisé en août 1991