Job $i$ has a length $t_i$ and a deadline $d_i$. The goal is to assign a starting time $s_i$ to each job such that each job is delayed as little as possible. A job $i$ is delayed if the finishing time $f_i > d_i$. The lateness of the job $i$ is $max(0, f_i - d_i)$. Show that the schedule has the least maximum lateness when $\forall{i,j}[s_i < s_j \implies d_i < d_j]$.

Suppose otherwise $i.e.$ given an optimal schedule with the least maximum lateness among all jobs, suppose there exists in this schedule job $i$ and $j$ with $s_i < s_j$ and $d_j < d_i$, and one of the two jobs has the maximum lateness in the schedule.

Case 1: suppose the earlier job $i$ has the maximum lateness in the schedule

Since $d_j < d_i$, the lateness of the next job $j$ must be greater than that of job $i$. A contradiction $i.e.$ case 1 is not possible.

Case 2: suppose job $j$ has the maximum lateness in the schedule

This means:

$$\begin{aligned} t_i - d_i < t_i + S + t_j - d_j \end{aligned}$$

where $S$ is the total delay in processing all the intervening jobs between $i$ and $j$, if any. If we swap the two jobs, we will now have $s_j < s_i$ and the lateness of job $j$ will be decreased by $t_i + S$, whereas the lateness of job $i$ will be increased by $S + t_j$, $i.e.$

$$\begin{aligned} t_i - d_i + (S + t_j) \end{aligned}$$

Comparing this to the maximum lateness before the swap:

$$\begin{aligned} t_i + S + t_j - d_j \end{aligned}$$

since $d_j < d_i$, the resultant increased lateness of job $i$ must be less than the original maximum. Therefore the new schedule has a least maximum lateness no greater than the original. $\Box$

# posted by rot13(Unafba Pune) @ 9:34 PM