# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Categorization of Models
Such models, however, typically abstract away critical factors like placement constraints and inter-GPU communication overheads. In real-world setups, jobs may require data locality or specialized hardware features (e.g., tensor cores) and can suffer performance degradation if spread across distant nodes -issues that a simple \(M/G/k\) framework cannot capture. To address these limitations, more sophisticated queueing formulations introduce multi-class networks: separate queues represent different GPU types or workload classes, and additional parameters model network delays in distributed training or inference. While these extensions better capture heterogeneity and locality, they trade off analytical tractability. Nonetheless, even simplified queueing approaches remain valuable for informing scheduler design--for instance, by quantifying the impact of FCFS versus priority-based service disciplines on average waiting times under varying load conditions [115]. Design takeawaysClassical queueing models such as \(M/G/k\) assume Poisson arrivals and light-tailed or exponential service time distributions--assumptions that do not hold for deep learning workloads. Empirical traces, such as Alibaba-GPU-2021 (90 th percentile \(\approx 3.5\times\) mean) and Google Borg (90 th percentile \(\approx 3\times\) mean), reveal heavy-tailed job durations. Fitting an exponential distribution to such data leads to systematic underestimation of tail latency. In particular, mis-specifying an \(M/G/k\) model under realistic load conditions (e.g., utilization \(\rho\approx 0.8\)) can significantly inflate p95 response times. As a result, when schedulers rely on queueing-theoretic insights, they should either incorporate heavy-tail parameter estimates or fall back to trace-driven simulations to avoid overly optimistic performance projections. Optimization-based models: A prevalent approach formulates GPU scheduling as a mixed-integer optimization problem. In time-indexed MILP formulations, binary variables \(x_{j,k,t}\) indicate whether job \(j\) runs on GPU \(k\) at time \(t\); alternative formulations introduce assignment variables \(x_{j,k}\) and ordering variables \(y_{j,t}\) to capture both placement and sequencing decisions [116; 117]. Common objectives include minimizing total (weighted) completion time or maximizing fairness, subject to constraints that enforce at most one job per GPU at any time and any job precedence relations. While these models afford exactness, their variable count grows with the product of jobs, GPUs, and time slots, making them computationally expensive for large instances. Consequently, MILP-based methods are most appropriate in offline settings for small to medium clusters or as benchmarks for heuristic algorithms, where modest problem sizes can often be solved to optimality [95]. To extend optimization into dynamic environments, some systems employ a rolling-horizon strategy: they repeatedly solve an MILP over the current queue or a short future window, then enact the resulting allocation before re-optimizing as new jobs arrive. For example, TetriSched (not GPU-specific) uses an MILP to allocate resources based on learned inference models [110], and Gavel recasts various scheduling policies into optimization problems tailored for heterogeneous clusters [57]. Alternatively, hybrid frameworks like Cynthia formulate a cost-minimization problem with performance guarantees and then apply a bounded-search heuristic guided by lightweight runtime predictions to efficiently discover near-optimal resource configurations in cloud-based DDNN (distributed deep neural network) provisioning [118]. Design takeawaysWhile pure MILP formulations offer exact solutions, their variable count scales with \(|\text{jobs}|\times|\text{GPUs}|\times|\text{time slots}|\), rendering them impractical for large-scale or highly dynamic clusters.