Not all scheduling problems can be solved using greedy methods. A greedy algorithm is correct only when the problem has both the greedy-choice property (some optimal solution starts with the locally best choice) and optimal substructure (what remains is a smaller instance of the same problem).
The scheduling problems that have these properties include:
- Activity Selection Problem: Selecting the maximum number of non-overlapping activities by always picking the one that finishes earliest.
- Interval Partitioning: Minimizing resources (like rooms) needed by greedily assigning intervals to available resources, which is optimal because it matches the "depth" (maximum overlaps).
However, not all scheduling problems have the optimal substructure property. Examples include:
- Jobs with different processing times and deadlines, maximizing the profit of jobs finished on time: taking the most profitable job first can crowd out several smaller jobs that together earn more. This variant is NP-hard in general and is usually solved with pseudo-polynomial dynamic programming. (With unit-length jobs the greedy in Job Sequencing with Deadlines is optimal.)
- Weighted completion time: on one machine, shortest processing time first (SPT) is optimal for minimizing the plain sum of completion times, but not when jobs carry different weights; then jobs must be ordered by the ratio of processing time to weight (Smith's rule). SPT also stops being optimal once jobs have release times and cannot be preempted.
Thus, as with all other greedy algorithms, a proof of correctness is a step that cannot be skipped.
When greedy approaches fail, the best bet is to turn to dynamic programming.
Scheduling problems lead to canonical greedy algorithms. A simple illustrative case is minimizing the maximum lateness of jobs on one machine: processing jobs in order of earliest deadline is optimal, which an exchange argument proves by swapping any adjacent pair that is out of deadline order without increasing the maximum lateness.