Openshops with jobs overlap Academic Article uri icon

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

  • 41

complete list of authors

  • Wagneur, E||Sriskandarajah, C

publication date

  • December 1993