On the complexity of preemptive openshop scheduling problems
Academic Article
-
- Overview
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
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.
citation count
complete list of authors
-
Sriskandarajah, C||Wagneur, E
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue