Openshops with jobs overlap
Academic Article
-
- Overview
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
We consider the complexity status of scheduling n jobs in an openshop with m machines, when overlapping of jobs is permitted, for some classical objective functions. In particular we show that optimal schedules for a regular performance measure are permutation schedules. Then we prove that the maximum completion time and the maximum tardiness are polynomial, that the number of late jobs problem is binary NP-hard in the two-machine case, and that the sum of completion times and the total tardiness problems are unary NP-hard for m ≥ 2. We also give polynomial time algorithms, or heuristic algorithms, for all the problems considered. © 1993.
author list (cited authors)
-
Wagneur, E., & Sriskandarajah, C.
citation count
complete list of authors
-
Wagneur, E||Sriskandarajah, C
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue