Abstract:
A priority algorithm is presented for the maximum lateness
problem with parallel identical processors, precedence
constraints, and preemptions. The algorithm calculates a
task's priority by constructing a schedule for the set of its
successors. It is shown that the presented algorithm constructs
an optimal schedule for the problem with two processors
and arbitrary precedence constraints, and for the problem
with an arbitrary number of processors and precedence
constraints in the form of an in-tree. The proof also indicates
that this algorithm allows the best worst-case ratio currently
known for the problems with precedence constraints.
