G-90-36
On the Complexity of Preemptive Openshop Scheduling Problems
et référence BibTeX
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.
Paru en août 1990 , 17 pages
Ce cahier a été révisé en août 1991