Hello,

I'm reading about greedy algorithms in "Algorithm Design" by Jon Kleinberg and Eva Tardos. Specifically, the "scheduling to minimize lateness" example. Basically, the goal is to schedule jobs each with a deadline on a single resource so that the lateness, or the finish time - deadline time is minimized (lateness cannot be negative). The solution is to take the jobs in increasing deadlines with no idle time. The proof involves an "inversion"; a situation where job j is scheduled after job i even though the deadline for j is before the deadline for i. It was proved that if an inversion exists between job a and job b, then there must be an inversion between two jobs i and j who are scheduled back to back. The claim is that swapping the two jobs that make up the inversion, i and j, does not increase the overall lateness. This is where I am confused.... Consider this example.

Before:

| <-2-> | <-2-> | <-2-> | <----8----> |
d(j) d(i) JOB I JOB j

where d(x) is the deadline of job x. The total lateness of I+J is 4+14=18. This is clearly an inversion.

After the swap:

| <-2-> | <-2-> | <----8----> | <-2-> |
d(j) d(i) JOB j JOB i

The total lateness is 12+12=24.

Doesn't this show that an inversion does not always lower the lateness or it keep the same, and hence the proof is faulty? Am I missing something?

Thanks for the help,

Eric