We consider the maximum lateness problem in which all tasks have the same execution time and must be processed on m > 1 parallel identical processors subject to precedence constraints. All tasks and all processors are available at time t = 0, and each task has a due date. If all due dates are zero, the maximum lateness problem converts to the makespan problem, which is known to be NP-hard. We present a polynomial time algorithm that enables us to obtain an optimal schedule for the case m = 2 and gives an approximate solution for the general case. The upper bound for this algorithm is derived and proved to be tight. If all due dates are zero, then the upper bound obtained coincides with the upper bound for the Coffman–Graham algorithm, which is the best known for the makespan problem.
