Scheduling precedence graphs of bounded height |
| |
Authors: | Danny Dolev Manfred K Warmuth |
| |
Affiliation: | IBM Research Laboratory, San Jose, California 95193 USA;Computer Science Department, University of California, Santa Cruz, California 95064 USA |
| |
Abstract: | The existence of a schedule for a partially ordered set of unit length tasks on m identical processors is known to be NP-complete (J. D. Ullman, NP-complete scheduling problems, J. Comput. System Sci., 10 (1975), 384–393). The problem remains NP-complete even if we restrict the precedence graph to be of height bounded by a constant. (J. K. Lenkstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Res., 26 (1978), 22–35; D. Dolev and M. K. Warmuth, “Scheduling Flat Graphs,” IBM Research Report RJ 3398, 1982). In these NP-completeness proofs the upper bound on the number of available processors varies with the problem instance. We present a polynomial algorithm for the case where the upper bound on the number of available processors and the height of the precedence graph are both constants. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|