# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Categorization of Models  
GPU scheduling problems can be modeled in various ways, each capturing different assumptions about job arrivals, system information, and analysis techniques. We categorize these models along several key dimensions and highlight their respective strengths and weaknesses. Offline and online scheduling models: A fundamental distinction is whether all jobs are known in advance (_offline scheduling_) or arrive over time (_online scheduling_). Offline models assume a fixed set of jobs \(J=\{1,2,\ldots,n\}\) with known runtimes and resource requirements. The goal is to compute a schedule--an assignment of start times and GPUs to each job--that optimizes a chosen objective (e.g., minimizing total completion time or the makespan). Offline scheduling can be formulated as a deterministic optimization problem, often reducing to NP-hard variants of classic machine scheduling problems [109]. With complete information, near-optimal or optimal schedules can be obtained for moderate-sized instances via integer programming or exhaustive search; however, these approaches do not scale to the large, dynamic workloads observed in real GPU clusters [110]. In contrast, online models treat scheduling as an ongoing process in which jobs arrive according to some distributions and decisions are made without knowledge of future arrivals. The scheduler reacts in real time to job arrivals and completions. Online algorithms are commonly evaluated via _competitive analysis_, proving performance bounds relative to an offline optimum--for example, guaranteeing a completion time at most \(c\) times the optimal (_c-competitive_) [111; 112]. Strong worst-case guarantees are often elusive for complex objectives, and without resource augmentation the competitive ratio may be unbounded. To obtain more meaningful metrics, many analyses instead assume stochastic workloads (e.g., Poisson arrivals with rate \(\lambda\), job sizes drawn from known distributions), which enables optimization of expected performance or derivation of steady-state results via queueing theory [113]. Classical queueing models such as the \(M/G/k\) system (Poisson arrivals, general service times, \(k\) servers) yield predictions for waiting times and queue lengths, and form the basis for many practical online GPU schedulers that serve jobs submitted unpredictably by users [74]. Some recent models further incorporate limited lookahead or predictions--using, for instance, user-provided runtime estimates or historical profiles--to blend online reactivity with partial future knowledge [114]. Design takeawaysOffline scheduling assumes complete knowledge of future job arrivals and service requirements--an assumption that rarely holds in real-world GPU clusters. In practice, even short look-ahead windows (e.g., tens of seconds) struggle to predict deep learning job runtimes accurately, due to variability in data pipelines and dynamic resource contention. Consequently, algorithms optimized for offline settings often overfit to idealized conditions and may perform poorly under unpredictable, real-time workloads. In production, practitioners typically rely on hybrid online heuristics that incorporate short-term forecasts or runtime profiling, rather than purely offline strategies. Queueing-theory-based models: Queueing-theoretic abstractions treat each GPU or collection of GPUs as a server and model jobs as customers, yielding analytic expressionsfor performance metrics such as mean waiting time or slowdown. Classical results underpin several scheduling policies: when job sizes are known, the shortest remaining processing time (SRPT) discipline minimizes mean completion time; when sizes are unknown, the Gittins index policy achieves optimal mean slowdown. Likewise, least attained service (LAS)--implemented in Tiresias via a time-slicing scheme--draws directly on these theoretical insights and operates effectively without explicit size estimates. At the scale of multi-GPU clusters, systems are often represented as an \(M/G/k\) queue with a central dispatcher [85].