# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Comparative Analysis of Models  
No single modeling approach is universally superior; each entails its own set of trade-offs. In what follows, we contrast the different models in terms of their information requirements, computational tractability, and practical applicability. Offline models vs. online models: Offline models assume full knowledge of the workload in advance and can, at least in principle, compute schedules that are near-optimal for that fixed-job set. They shine in static or batch-processing contexts (for example, nightly jobs), where one can afford to spend significant computation time to derive an optimal plan. However, these approaches often struggle with both scalability and adaptability: a schedule that is optimal for a predetermined collection of jobs may perform poorly when faced with unexpected arrivals or delays. By contrast, online models make decisions as jobs arrive, eschewing any prescience of future workloads [132]. Their primary goal is to sustain high utilization and low latency in dynamic environments. Lacking complete information, they typically employ heuristics or approximation algorithms; truly optimal online policies exist only under highly idealized assumptions. In practice, systems adopt robust \"good-enough\" rules that deliver reliable average performance. The strength of online models lies in their realism and flexibility--qualities essential for perpetually running services such as shared GPU clusters--although this comes at the expense of weaker theoretical guarantees. In short, offline models are most valuable for controlled experiments or as benchmarking baselines, whereas online models are indispensable for real-time scheduling, trading some optimality for responsiveness and robustness in the face of uncertainty. Queueing-theory-based models vs. optimization-based models: Queueing-theoretic approaches provide elegant analytical insights under stochastic assumptions (e.g., Poisson arrivals and exponential service times) [74; 113]. In these simplified settings, they can identify optimal policies, such as SRPT or the Gittins index in an \(M/G/1\) queue, and offer probabilistic performance guarantees (for example, bounds on average delay or queue-overflow probability). However, the abstractions that enable tractability often overlook key complexities: multi-GPU coordination, non-negligible setup times, and the heavy-tailed service distributions typical of ML training workloads. By contrast, optimization-based models (e.g., MILPs or min-cost flow formulations) can encode detailed system characteristics without relying on simple stochastic assumptions. Taking deterministic inputs--whether point estimates or worst-case values--they capture GPU memory constraints, precedence relations in multi-stage jobs, fairness budgets, energy caps, and more. Their chief limitation is computational: they rarely scale to large, dynamic workloads without heuristic approximations or periodic re-solving, which may be impractical for real-time decision-making. In essence, queueing models excel at providing probabilistic guarantees within idealized frameworks, while optimization models deliver high-fidelity scheduling at the expense of scalability. Many production systems, therefore, combine both: leveraging queueing theory to establish high-level priority rules and employing optimization solvers to handle subproblems (such as packing jobs onto GPUs) at discrete intervals. Heuristic approaches vs. formal methods: In practice, many GPU schedulers rely on fast, rule-based heuristics--such as greedy allocation to the best-fitting job or back-filling small jobs into idle slots--to make scheduling decisions with minimal overhead and implementation complexity [133]. These methods can be tuned via parameters (e.g., backfill aggressiveness or priority weightings) to match specific workload patterns or policy goals.