Scheduling to Minimize Lateness

Goal:

• Single resource processes one job at a time.
• Job $j$ requires $t_j$ units of processing time and is due at time $d_j$.
• If $j$ starts at time $s_j$, it finishes at time $f_j=s_j+t_j$.
• Lateness: $l_j=\max (0,f_j-d_j)$
• Goal: Schedule all jobs to minimize maximum lateness

Algorithm: Ascending order of deadline