Scheduling to Minimise Lateness

Input $n$ jobs consisting of pairs of (duration, deadline).

Output Schedule of jobs that minimises maximum lateness.

The algorithm needs to determine the start time of and interval, $s(i)$. The finish time, $f(i)$ is then given by $s(i) + t_i$ where $t$ is the duration. The lateness of a request is given by $l_i = f(i) - d_i$ where $d$ is the deadline. The goal of the algorithm is to schedule the jobs in order to minimise the maximum lateness of all jobs, $L$.

Greedy rules for minimising maximum lateness

  1. Schedule the jobs in order of increasing length $t_i$ to get the short jobs done quickly. This is not optimal, as a job with a shorter time and very long deadline will be scheduled before a job with duration = deadline.
  2. Let the slack time of a job be given by $d_i - t_i$. Scheduling the jobs by smallest slack time does not work. Consider jobs $t_1 = 1$, $d_1 = 2$ and $t_2 = 10$, $d_2 = 10$. Using minimum slack, job 2 will be scheduled first, giving total lateness 9, whereas scheduling job 1 first will give total lateness 1.
  3. Earliest deadline first - This is the optimal rule.

The pseudocode for this algorithm is as follows:

sort jobs by earliest deadline first
let f = s
for each job i
    assign job i to time interval s(i) = f to f(i) = f + t_i
    let f = f + t_i
return the set of scheduled intervals [s(i), f(i)]

Proof of optimality

Consider a schedule $A$ output by the algorithm and an optimal schedule $O$. It is possible to transform $O$ into $A$ without affecting its optimality using an exchange argument.

A schedule is said to have an inversion if a job $i$ with deadline $d_i$ is scheduled before another job $j$ with earlier deadline $d_j < d_i$. By definition $A$ does not contain any inversions. It is then possible to show that all schedules with no inversions and no idle time have the same maximum lateness.

$A$ is optimal if it can be shown an optimal schedule with inversions can be converted into $A$ without increasing the maximum lateness.

If $O$ has an inversion, there is a pair of adjacent, inverted jobs $i$ and $j$. Swapping these jobs decreases the number of inversions by 1. It is then possible to prove the new swapped schedule has a maximum lateness no larger than that of $O$.

For the schedule $O$, let each request $r$ be scheduled for the interval $[s(r), f(r)]$ with lateness $l'_r$. Let $L' = \max_rl'_r$ denote the maximum lateness of $O$.

Let $\bar{O}$ denote the swapped schedule and $\bar{s}_r, \bar{f}_r, \bar{l}_r$ and $\bar{L}_r$ denote the corresponding properties.

The finish time of $j$ before the swap is exactly equal to the finish time of $i$ after the swap. Therefore all other jobs finish at the same time in both schedules. As $j$ finishes earlier in $\bar{O}$ and $d_i > d_j$ the swap can't increase the lateness of $j$.

After the swap, job $i$ finishes at time $f(j)$. If job $i$ is late in $\bar{O}$, then its lateness is $\bar{l}_i = \bar{f}(i) - d_i = f(j) - d_i$. Since $d_i > d_j$, $\bar{l}_i = f(j) - d_i < f(j) - d_j = l'_j$. The lateness in $O$ is $L' \geq l'_j > \bar{l}_i$, so the swap does not increase the maximum lateness of the schedule. Therefore any optimal solution with inversions can be transformed into $A$ without increasing the maximum lateness, so $A$ is optimal. $\blacksquare$

Complexity

Sorting is $O(n\log n)$ and iteration is $O(n)$ giving $O(n\log n)$ overall.