The NP-completeness of the n/m/parallel/Cmax preemptive due-date scheduling problem

✍ Scribed by T.C.E. Cheng; C.C.S. Sin

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 154 KB
• Volume: 13
• Category: Article
• ISSN: 0895-7177
• DOI: 10.1016/0895-7177(90)90375-w

✦ Synopsis

We present a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the maximum job completion time subject to no jobs being tardy.