# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Comparative Analysis of Models
Their main drawback is the absence of worst-case performance guarantees: under adversarial or highly skewed arrivals, a naive greedy policy may repeatedly starve large jobs or incur significant delays for certain job classes if fairness constraints are not carefully enforced. By contrast, formal methods (e.g., integer linear programming or dynamic programming) can compute provably optimal schedules under a given model, ensuring that no better solution exists within the specified assumptions. However, their exponential time complexity generally precludes application to large or highly dynamic clusters except in offline calibration or small subproblem contexts. Furthermore, an \"optimal\" schedule derived from a simplified model may falter in practice if it omits factors such as communication overhead or variability in service times. Consequently, state-of-the-art GPU schedulers often adopt a hybrid design: lightweight heuristics handle real-time, large-scale decision-making, while occasional formal optimizations tune parameters or solve constrained subproblems. This blended approach preserves the speed and robustness of heuristics, ensuring, for example, that GPUs are never over-subscribed and no job is indefinitely starved, while leveraging formal analyses to verify and improve the scheduler's performance in controlled scenarios. Learning-based models vs. rule-based models: A growing trend is to infuse schedulers with machine learning, for instance, via reinforcement-learning-derived policies or predictive models that estimate job runtimes and performance across GPU types. Such learning-based schedulers can adapt automatically to workload dynamics and capture complex, nonlinear interactions (e.g., shifting bottlenecks between CPU, network, and GPU) that static heuristics often miss. In principle, as they accrue experience or improve their predictive accuracy, these models can converge toward near-optimal scheduling decisions. However, learning-based approaches introduce significant overheads and operational challenges. Training an RL agent or regression model demands large historical datasets and substantial compute for simulation or model fitting, and there is frequently a _coldstart_ phase during which performance may lag behind established baselines [134]. In production contexts, this initial under-performance can be unacceptable. Learned policies also tend to be opaque, making them difficult to interpret, debug, or formally verify factors that can undermine operator trust in high-stakes environments. Moreover, without careful regularization or retraining, models risk overfitting to past patterns and may fail to generalize when workloads or hardware configurations evolve (e.g., when new job types or GPU architectures are introduced). By contrast, traditional rule-based schedulers--simple heuristics or parameterized policies--require no training data, are immediately operational, and degrade predictably only if their underlying assumptions are violated. They are straightforward to debug and tune by human operators and offer stable behavior even under unanticipated conditions. Recognizing the strengths and weaknesses of both paradigms, recent work often adopts hybrid strategies: using ML to fine-tune heuristic parameters (such as backfill thresholds or time quanta) or delegating only specific subdecisions (e.g., selecting an optimal GPU type via a performance predictor) to learned components, while retaining overall rule-based control. Such hybrids aim to harness the adaptability of learning-based methods without surrendering the reliability and interpretability of established heuristics. Model selection: Scheduling models are most effective when aligned with the characteristics of their target environment. In batch-oriented HPC clusters--where hardware is homogeneous and throughput dominates--simple priority queues and backfilling heuristics remain the de facto standard.