# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Categorization of Models
In production, teams often augment these heuristics with lightweight prediction modules (e.g., runtime predictors or simple interference models) to mitigate misallocation caused by DL-specific variability. Learning-based models: Recent scheduling frameworks leverage machine learning to predict job characteristics or adaptively optimize decisions. These learning-based models are typically classified into three categories: _ML-assisted prediction models_, _reinforcement learning (RL) models_, and _hybrid learning models_. ML-assisted prediction models employ learned estimators to predict key job parameters--such as runtime or resource requirements--before scheduling. For each job \(j\), a predictor \(\hat{p_{j}}=f(\text{job features})\) (e.g., a linear regression, a neural network trained on historical logs, or user-provided estimates) approximates the true value \(p_{j}\)[125]. By incorporating \(\hat{p_{j}}\) into placement and ordering decisions, schedulers can significantly improve backfilling efficiency and reduce queueing delays in HPC clusters [126]. For example, Optimus probes performance across varying GPU counts to build an online throughput model, dynamically allocating GPUs to maximize aggregate throughput [66], while AlloX performs brief profiling runs on CPU and GPU, fits a linear per-iteration time model, and selects the optimal platform for each job [124]. Robust implementations must also include mechanisms to tolerate or adapt to prediction errors. RL models frame scheduling as a Markov decision process (MDP), where states encode resource utilization and queue lengths, actions correspond to dispatch or prioritization decisions, and rewards reflect metrics such as throughput or slowdown. An RL agent learns a dispatch policy by interacting with a simulated cluster or replaying historical traces. DeepRM, for instance, embeds both current and queued jobs in its state representation and dispatches batches to minimize average slowdown [82], while Decima incorporates a graph neural network to capture DAG-structured workloads and learns execution orderings that minimize end-to-end runtime [127]. These models can balance multi-objective goals--efficiency, fairness, QoS--through reward shaping, but their performance often hinges on the fidelity of the training environment. Recent multi-agent RL approaches extend this paradigm by treating GPUs or individual jobs as agents that coordinate to improve global performance [128]. Hybrid learning models combine the adaptability of ML with the predictability of classical heuristics. In these layered systems, ML components tune critical heuristic parameters--such as time-slicing intervals--while the final scheduling decisions rely on traditional rule-based mechanisms. Themis, for example, augments an auction-based scheduler by optimizing bid values through ML-driven models [85], and Pollux continuously adjusts per-job resource allocations (batch size and GPU count) based on observed throughput to steer training workloads toward optimal efficiency [68]. _Design takeaways_. ML-assisted prediction models can significantly reduce queuing delays by providing schedulers with accurate estimates of job runtime or throughput. However, their benefits diminish rapidly as prediction errors increase. In production DL clusters, factors such as data pipeline skew or cross-job interference often inflate these errors. As a result, robust systems must continuously audit estimator quality and fall back on conservative heuristics--such as adding safety margins--whenever error thresholds are exceeded. RL-based schedulers, including DeepRM, Decima, and various multi-agent variants, are well-suited for handling complex, multi-objective trade-offs. However, their effectiveness is heavily dependent on the fidelity of the training environment. Policies trained on synthetic or outdated traces often fail to generalize to live clusters, and achieving robust performance typically requires thousands of simulated episodes.