✦ LIBER ✦

NP-complete scheduling problems

✍ Scribed by J.D. Ullman

Publisher: Elsevier Science
Year: 1975
Tongue: English
Weight: 423 KB
Volume: 10
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(75)80008-0

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the problem of finding an optimal schedule for a set of jobs is NPcomplete even in the following two restricted cases.

(1) All jobs require one time unit.

(2) All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Graham, Proc.

📜 SIMILAR VOLUMES

Certain NP-complete matching problems

✍ G. Loizou 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 311 KB

Complete problems for monotone NP

✍ Iain A. Stewart 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 768 KB

An NP-complete matching problem

✍ David A. Plaisted; Samuel Zaks 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 847 KB

Neural networks for NP-complete problems

✍ Marco Budinich 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 547 KB

combinatorial optimization is an active field of research in Neural Networks. Since the first attempts to solve the travelling salesman problem with Hopfield nets several progresses have been made. I will present some Neural Network approximate solutions for NP-complete problems that have a sound ma

A two-machine preemptive openshop schedu

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

✍ A.A. Gladky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 197 KB

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.

The NP-completeness of the n/m/parallel/

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

✍ T.C.E. Cheng; C.C.S. Sin 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 154 KB

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.