Scheduling to Minimizing LatenessMinimizing lateness problem. Single resource processes one job at a time. Job j requires tj units of processing time and is due at time dj. If j starts at time sj, it finishes at time fj = sj + tj. Lateness: j = max { 0, fj - dj }. Goal: schedule all jobs to minimize maximum lateness L = max j.
Ex:
1 tj dj 3 6
2 2 8
3 1 9
4 4 9
5 3 14
6 2 15
lateness = 2
lateness = 0
max lateness = 6
d3 = 90 1
d2 = 82 3
d6 = 154 5 6
d1 = 67 8
d5 = 149 10 11 12
d4 = 913 14 15