It can schedule jobs on a single processor in a way that minimizes the maximum tardiness, lateness, or any function of them.
[2] Some special cases are: The algorithm builds the schedule back to front.
For each scheduling step, it looks only at the tasks that no other tasks depend on, and puts the one with the latest due date at the end of the schedule queue.
The algorithm works by planning the job with the least impact as late as possible.
Assuming there are three jobs: t1, t2, and t3, with the following precedence constraints: And the following deadlines (due date in a month) Now we construct the required set of jobs: Repeat the following steps until J is empty: Do the next round: Do the next round: J is now empty.
So the final schedule is t1 -> t2-> t3 as S = {t1, t2, t3} A more complex example, with simplified steps: The jobs and precedence constraints are shown below: a parent node --> child node in the tree.
The due dates of jobs are shown underneath of each node of the tree in parentheses.
Now look at the set of jobs without any successors, find the one with latest due date, put it into the front of S: