Greedy Scheduling and Queueing
Greedy algorithms make an irreversible local choice. Their value comes from the invariant proving that the choice cannot make the final answer worse.
Planned model
Schedule the same jobs by arrival time, duration, deadline, and priority. Display queue growth, completed work, lateness, and counterexamples.
Questions
- What exchange argument justifies the local choice?
- When does priority create starvation?
- How do fairness, throughput, and latency goals conflict?
Exercise
Choose a policy for a bounded worker queue and construct a workload on which a plausible alternative fails.