Precedence constrained scheduling: A case in P

'Unit execution time' precedence constrained scheduling (UET) is an NP-comp lete 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-tim e: 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 whic h represent algebraic computations fall ordinarily in this category. Our al gorithm is based on a limited look-ahead technique which allows us to use i t 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.