Name
Abstract | ||
|---|---|---|
A set of unit-time tasks has to be processed on identical parallel processors subject to precedence constraints and unit-time communication delays; does there exist a schedule of length at most d? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for d = 3 and is NP-complete for d = 4. The second variant is solvable in polynomial time for d = 5 and NP-complete for d = 6. As a consequence, neither of the corresponding optimization problems has a polynomial approximation scheme, unless P = NP. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0167-6377(94)90024-8 | Oper. Res. Lett. |
Keywords | Field | DocType |
unit-time task,unit-time communication delay,corresponding optimization problem,complexity,communication delays,polynomial approximation scheme,identical parallel processor,polynomial time,makespan,approximation,precedence constraints,identical parallel processors | Mathematical optimization,Job shop scheduling,Polynomial,Scheduling (computing),Parallel computing,Arithmetic,Transmission time,Time complexity,Optimization problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
16 | 3 | Operations Research Letters |
Citations | PageRank | References |
45 | 3.80 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. A. Hoogeveen | 1 | 520 | 50.29 |
| J. K. Lenstra | 2 | 1689 | 329.39 |
| Bart Veltman | 3 | 194 | 16.86 |