# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Comparative Analysis
Finally, when multiple objectives must be balanced, heuristic frameworks blend metrics through weighted composite priorities, and RL policies achieve similar trade-offs via reward shaping or exploration strategies such as the \"power of two choices,\" dynamically discovering schedules that balance responsiveness, utilization, and equity. Scalability and heterogeneity: Lightweight scheduling algorithms naturally scale to large clusters, since event rates--job arrivals, completions, and preemptions--are typically limited by job runtimes. Even in a busy 1000-GPU deployment, only tens of scheduling events occur per second, allowing a single-threaded priority-queue or placement update to keep pace. At web-scale (e.g., Google's Borg, managing millions of jobs), however, centralized schedulers become a throughput bottleneck, prompting distributed or hierarchical designs that partition the cluster into independently managed cells. Most academic proposals assume one scheduler handling a few hundred to a few thousand machines, a regime where heuristics and RL policies remain practical; by contrast, ILP and metaheuristic methods incur prohibitive computation at this scale. RL approaches can scale in principle, but only if the policy efficiently summarizes system state. Naively encoding all jobs and resources leads to state-space explosion. To mitigate this, many RL schedulers use fixed-size job subsets, recurrent or attention-based networks, or other compact representations. Some systems train on small clusters and transfer policies to larger ones, though such generalization often demands careful architecture design and retraining. Heterogeneity in GPU types, network bandwidths, and workload characteristics further complicates scaling. Heuristics and queueing frameworks adapt readily--by maintaining per-resource queues or weighting priorities by expected slowdown on each GPU class. ILP formulations can model heterogeneity via extra constraints, but at the cost of larger variable counts and slower solves. RL methods can encode resource types directly in the state, yet typically require retraining to master a heterogeneous environment. Notwithstanding this engineering overhead, recent work such as HeterPS demonstrates that RL can effectively learn in diverse cluster settings [171]. Overall, simple heuristics offer the greatest flexibility for rapid deployment, while RL and optimization-based techniques, once tuned or trained, can yield superior performance in large, heterogeneous clusters. Other performance metrics: fault tolerance, interpretability, explainability, and transparency: Simpler scheduling algorithms are inherently easier to make fault-tolerant. For example, after a crash or restart, a greedy or rule-based scheduler can rebuild its internal state--essentially a queue of pending jobs--by querying the current cluster status. RL agents, by contrast, do not carry over internal state between decisions (beyond what the environment encodes); their policies must simply be persisted to avoid retraining, which is generally straightforward since they remain static during deployment. Optimization-based methods (ILP/MILP) present greater recovery challenges. Any change in system state may force the solver to restart from scratch to compute a new solution, a process that can be time-consuming. In the event of infrastructure failures--such as a GPU or node outage--most schedulers treat these incidents as preemptions: the affected job is re-queued or scheduled elsewhere. Heuristic approaches often include built in fallback rules (e.g., deprioritizing unreliable nodes), whereas learning-based methods can fold failure events into their training or apply online policy updates to adapt over time. Interpretability and transparency are also critical in multi-tenant clusters, where users' trust depends on understanding scheduling decisions. Rule-based and heuristic policies are simple to explain--\"short jobs first,\" \"equal GPU shares per user\"--enabling clear mental models and reducing frustration.