Recall the Scheduling to Minimize Lateness problem. The input is a list of jobs each of which requires a length of time t_i and has a deadline d_i. A schedule is an ordering (permutation) of the jobs, to be done one right after another, and s(i) and f (i) denote the start and finish times of job i under a particular schedule. The lateness _i is defined to be f (i) d_i if job i is late (i.e., f (i) > d_i) or 0 if job i is not late. We proved that a greedy algorithmwhich simply sorts the jobs in increasing order of deadlineminimizes the maximum lateness over all jobs (max_ii).

Now we consider a variant of the problem, with two changes. First, we redefine the lateness

_i to be f (i) d_i regardless of whether job i is late (so _i is negative if job i is early). Second, we consider the total lateness (the sum of i, _i) rather than the maximum. Thus, one job being finished

early can offset another job being late.

4a. Find an input with two jobs on which the earliest deadline first greedy algorithm fails to find an optimal schedule.

4b. Use an exchange argument to prove that the shortest job first greedy algorithm actually produces an optimal schedule. That is, assuming the jobs have been renumbered so t₁ t₂ t_n, show that this algorithms schedule A = (1, 2, . . ., n) is at least as good as any other schedule B. The analysis is structured just like the exchange argument we saw in class: Imagine Bubble Sorting B to A by repeatedly picking a consecutive inversion and swapping it, and argue that in each step the total lateness doesnt increase. To be precise, consider any step where a consecutive inversion (i, j) is being swapped (so i > j but i was scheduled immediately before j), and for each job k let s(k), f' (k), _k be its start time, finish time, and lateness in the before the swap" schedule, and similarly s''(k), f'''(k), l''_k in the "after the swap" schedule. Then s'(i) = s''(j) and f'(j) = f''(i), and for each k other than i and j, job k's contribution to the total lateness doesn't change in this step since f'(k) = f''(k). Thus, it just remains to show that '' + '' ' + '.