Lawler's algorithm

Lawler's algorithm is a powerful technique for solving a variety of constrained scheduling problems. The algorithm handles any precedence constraints. It schedules a set of simultaneously arriving tasks on one processor with precedence constraints to minimize maximum tardiness or lateness. Precedence constraints occur when certain jobs must be completed before other jobs can be started.

Objective functions

The objective function is assumed to be in the form [math]\displaystyle{ min \, max_{0\le i \le n} \, g_i(F_i) }[/math], where [math]\displaystyle{ g_i }[/math] is any nondecreasing function and [math]\displaystyle{ F_i }[/math] is the flow time. When [math]\displaystyle{ g_i (F_i) = F_i - d_i = L_i }[/math], the objective function corresponds to minimizing the maximum lateness, where [math]\displaystyle{ d_i }[/math] is due time for job [math]\displaystyle{ i }[/math] and [math]\displaystyle{ L_i }[/math] lateness of job [math]\displaystyle{ i }[/math]. Another expression is [math]\displaystyle{ g_i (F_i) = max {(F_i-d_i,0)} }[/math], which corresponds to minimizing the maximum tardiness.

Algorithm

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. Then it repeats this process until all jobs are scheduled.

The algorithm works by planning the job with the least impact as late as possible. Starting at [math]\displaystyle{ t = \sum p_j }[/math] that [math]\displaystyle{ p_j }[/math] is the production time of job [math]\displaystyle{ j }[/math].

[math]\displaystyle{ S }[/math] set of already scheduled jobs (at start: S = [math]\displaystyle{ \emptyset }[/math])
[math]\displaystyle{ J }[/math] set of jobs whose successors have been scheduled (at start: all jobs without successors)
[math]\displaystyle{ t }[/math] time when the next job will be completed (at start: [math]\displaystyle{ t = \sum p_j }[/math])
while[math]\displaystyle{ J \neq \emptyset }[/math] do
    select [math]\displaystyle{ j \in J }[/math] such that [math]\displaystyle{ f_j(t) = min_{k \in J}f_k(t) }[/math]
    schedule [math]\displaystyle{ j }[/math] such that it completes at time [math]\displaystyle{ t }[/math]
    add [math]\displaystyle{ j }[/math] to [math]\displaystyle{ S }[/math], delete [math]\displaystyle{ j }[/math] from [math]\displaystyle{ J }[/math] and update [math]\displaystyle{ J }[/math].
    [math]\displaystyle{ t = t - p_j }[/math]
end while

Example 1

Assuming there are three jobs: t1, t2, and t3, with the following precedence constraints:

• t1-> t2, t1 must finish before t2
• t1-> t3, t1 must finish before t3

And the following deadlines (due date in a month)

• t1: 2nd day
• t2: 5th day
• t3: 8th day

Now we construct the required set of jobs:

• S = {empty}, initially empty set of scheduled jobs
• J = {t2, t3}, the set of jobs whose successors have been scheduled or jobs without successors. t2 and t3 have no successors.

Repeat the following steps until J is empty:

• select a job j in J, so its due date is the latests, in this example, it is t3 with a due date 8th.
• move j from J to S's front, now J = {t2}, S={t3}.
• update J to add any new job whose successors have been scheduled. There is none this time.

Do the next round:

• select a job j in J, so its due date is the latests. It is t2 with due date 5th this time.
• move j from J to S's front, now J = {empty}, S={t2, t3}
• update J to add any new job whose successors have been scheduled, now J= {t1} since both t2 and t3 have been scheduled.

Do the next round:

• select a job j in J={t1}, so its due date is the latests. This example, it is t1.
• move j from J to S's front, now J = {empty}, S={t1, t2, t3}
• update J to add any new job whose successors have been scheduled. Nothing to add.

J is now empty. The end.

So the final schedule is t1 -> t2-> t3 as S = {t1, t2, t3}

Example 2

A more complex example, with simplified steps: The jobs and precedence constraints are shown below: a parent node --> child node in the tree.

      j1 
     (2) 
    /   \
   j2    j3 
  (2)    (4)
  / \     |
 j4 j5   j6
(3) (5)  (6)  

The due dates of jobs are shown underneath of each node of the tree in parentheses.

• j1: 2
• j2: 5
• j3: 4
• j4: 3
• j5: 5
• j6: 6

Now look at the set of jobs without any successors, find the one with latest due date, put it into the front of S:

• The S set would be { j1, j2, j4, j3, j5, j6}

Further reading

• Michael Pinedo. Scheduling: theory, algorithms, and systems. 2008. ISBN:978-0-387-78934-7
• Conway, Maxwell, Miller. Theory of Scheduling. 1967. ISBN:0-486-42817-6