On the complexity of preemptive openshop scheduling problems
- Additional Document Info
- View All
We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functions, we define the concept of preempting job w.r. to a schedule, and state some general results for the preemptive openshop environment. These results are then used to show by reduction from the 3-Partition, that the n job-2 machine mean flow time problem with ready times and job preemption is unary NP-hard. © 1994.
author list (cited authors)
Sriskandarajah, C., & Wagneur, E.
complete list of authors
Sriskandarajah, C||Wagneur, E