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