zbMATH — the first resource for mathematics

An iterative algorithm for scheduling unit-times tasks with precedence constraints to minimise the maximum lateness. (English) Zbl 0908.90178
Summary: 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.

90B35 Deterministic scheduling theory in operations research
Full Text: DOI