An iterative algorithm for scheduling UET tasks with due dates and release times.
A classical scheduling problem involving Unit Execution Time (UET) tasks is considered. A new polynominal-time iterative algorithm is presented for scheduling UET task system with 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.
scientific article; zbMATH DE number 1957046