Scheduling UET-UCT outforests to minimize maximum lateness

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 are restricted the generalization of the Brucker-Garey-Johnson algorithm presented in Oper. Res. Lett. 29 (1) (2001) 17 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 are two and precedence constraints are in the form of an outforest.