Not all scheduling problems can be solved using greedy methods. Greedy algorithms work when there are optimal substructure properties.
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:
- General Job Sequencing with Deadlines: Picking the highest profit job first might block other profitable jobs that could have been scheduled, leading to a lower total profit than an optimal solution (which requires considering all possibilities).
- Shortest Processing Time (SPT) for all tasks: If the goal is to minimize total completion time, simply processing shortest jobs first isn't always optimal; it depends on the exact objective and constraints.
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 leads to canonical greedy algorithms. The proof of the greedy approach to a scheduling problem is outlined in A simple illustrative case is the scheduling problem. The greedy approach picks the task that has the earliest deadline..