An iterative algorithm for scheduling UET tasks with due dates and release times

Abstract

A new polynomial-time iterative algorithm is presented for the scheduling problem with a unit execution time task system, parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.