Proof of optimality of a greedy solution to job sequencing

The optimality of the greedy solution can be seen by an exchange argument as follows. Without loss of generality, assume that all profits are different and that the jobs are sorted in decreasing order of profits.

Fix a solution S. From this solution, delete every job that misses its deadline. As by this transformation every job finishes within its deadline, the resulting solution S1 is still optimal. For job i, consider the interval I_i:=[0,min(n,deadline(i))] (as in the greedy algorithm). In this interval, to the right of job i, there are only jobs with larger processing time (if not, they either would have been considered earlier by our ordering, or they could be exchanged witout violation of their deadlines). Place job i to the rightmost position possible in I_i.

In total, we have the following statement.

Each solution S can be transformed into a solution S' with the following propoerties.

1. S' contains every job of S which finishes before its deadline.
2. For every job i in S, all jobs after i in I_i have a larger processing time.
3. For every job i in S, there is no idle time after i in I_i.
4. S' has the same objective value as S.

In particular, there exists an optimal solution S* with the properties above. Let S be the algorithm generated by the greedy algorithm. Note that S also has the properties 2 and 3 above. Let i be the first job which occurs in S but not in S*. Let pos be the time slot of i in S. If pos was empty in S*, S* could be improved by adding i, in contradiction to the optimality of S*. If pos was not empty in S*, the job i'at pos in S* cannot be of larger profit than i, since otherwise the greedy algorithm would have chosen i' to be at pos in S. Hence, it must be of lower profit than i. This means that it can be deleted and replaced by i in S*, which also contradicts the optimality of S*.