Scheduling Algorithms

Model the scheduling problem before naming an algorithm. The same label can hide different arrival, precedence, resource, and preemption assumptions.

Problem Contract

Record:

• jobs/tasks and arrival process;
• resource types, capacity, affinity, and heterogeneity;
• processing-time knowledge and uncertainty;
• precedence/DAG and communication cost;
• preemption, migration, replication, and failure rules;
• deadlines, priorities, fairness, and admission control;
• online/offline decision timing;
• primary objective and guardrails.

Typical objectives include response time, waiting time, slowdown, deadline misses, makespan, throughput, utilization, energy, cost, and fairness. Define units and aggregation; improving one can harm another.