Proof. Suppose jobs \(i\) and \(j\) are adjacent, \(i\) first, with \(p_i > p_j\), starting at time \(t\). Swapping them leaves all other completion times unchanged, and changes the completion times of \(i\) and \(j\) from \(t + p_i\) and \(t + p_i + p_j\) to \(t + p_j\) and \(t + p_i + p_j\), reducing the sum by \(p_i - p_j > 0\). So an optimal order has no such pair: it is SPT. For EDD, if \(d_i > d_j\) with \(i\) first, the later of the two finishes at \(t + p_i + p_j\) in either order; before the swap the lateness of \(j\) is \(t + p_i + p_j - d_j\), which is at least both latenesses after it, since \(d_j < d_i\) and the earlier job finishes sooner. So swapping does not increase the maximum lateness. □

Sketch. The makespan of an order is \(\max _k\bigl (\sum _{i \leq k}a_{(i)} + \sum _{i \geq k}b_{(i)}\bigr )\), the longest path through the grid of operations, where \((i)\) is the \(i\)th job. If two adjacent jobs \(i\) then \(j\) satisfy \(\min (a_j, b_i) < \min (a_i, b_j)\), swapping them does not increase any of these path lengths. Johnson’s order is exactly an order with no such adjacent pair (jobs placed early are those with small \(a\), so that machine \(2\) starts soon, and jobs placed late are those with small \(b\), so that it finishes soon), and every order can be brought to it by such swaps. □