Precedence Constrained Scheduling: A Case in P
Konstantinos Politopoulos · The Computer Journal · 2001
‘Unit execution time’ precedence constrained scheduling (UET) is an NP-complete problem with very few special cases known to be solvable in P-time. In this article we present a practically useful case of UET solvable in P-time: we show that if the task graph is given in levels that are ‘locally’ of in-degree two and of ‘width’ more than 1.55 times the number of processors (plus 1), then an optimal schedule can be found in P-time. Task graphs which represent algebraic computations fall ordinarily in this category. Our algorithm is based on a limited look-ahead technique which allows us to use it in an on-line fashion. In the appendix we give two short NP-completeness proofs which suggest that both ‘width’ and ‘degree’ restrictions are needed to get a polynomially solvable subcase.