✦ LIBER ✦

A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness

✍ Scribed by A.A. Gladky

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 197 KB
Volume: 103
Category: Article
ISSN: 0377-2217
DOI: 10.1016/s0377-2217(96)00249-4

No coin nor oath required. For personal study only.

✦ Synopsis

This paper deals with a two-machine preemptive openshop system processing a set of jobs with different ready dates. The problem of minimizing the mean flow time is known to be strongly NP-complete. We reprove this fact in an elementary way. @ 1997 Published by Elsevier Science B.V.