In this paper, a well known NP-hard problem with parallel processors, precedence constraints, unit execution time task system, and the criterion of maximum lateness is considered. In the case when the graph representing the partially ordered set of tasks is an outforest, we show that if the number of processors is restricted the generalization of the Brucker–Garey–Johnson algorithm is a 2-approximation algorithm, and it produces an optimal schedule if the number of processors is sufficiently large. We also present another polynomial time algorithm, which enables us to obtain an optimal schedule when number of processors is two and precedence constraints are in the form of an outforest.
