Lehrstuhl Mathematik & InformatikLinear Time Algorithms for two Special Problems
Abstract. The problem of scheduling unit execution time
tasks on a variable number of processors under arbitrary precedence
constraints is known to be NP-complete [7].
But the precedence constraints for procedures in a structured program
form very special dags, called p-rhombs and sp-rhombs in
this paper. It is shown that an optimal schedule can be found in
linear time, if the precedence constraints form a p-rhomb. The same
result holds for sp-rhombs, if we restrict ourselves to the
2-processor case.
In both cases optimal schedules result from a very simple 'deepest
first'-principle, which is known to be optimal for trees too [5].
References:
[5] T.C. Hu, Parallel Sequencing and
Assembly Line Problems, Operations Research 9, pp. 841-848, 1961.
[7] J.D. Ullman, NP-complete Scheduling
Problems, J. of Comp. and System Sciences 10, pp. 384 - 393, 1975.