# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Categorization of Models
In offline settings on small to medium clusters, MILP can yield optimal schedules, but even rolling-horizon variants incur significant solver latency--ranging from tens of seconds to minutes--and may struggle to adapt when high-priority DL jobs arrive unexpectedly. Moreover, cost models (e.g., learned runtime predictions) are often noisy; optimization routines that depend on misestimated job characteristics can under-perform relative to simpler heuristics, especially under bursty workloads. In practice, MILP is most effective as a benchmarking tool or within tightly controlled batch environments, while latency-sensitive clusters benefit more from fast approximations or hybrid heuristic approaches. Optimization-inspired heuristicsProduction GPU schedulers often employ simple, fast heuristics that support real-time decision making and ease of deployment [79]. A canonical example is a shortest-remaining-processing-time (SRPT) first greedy policy, which assigns the smallest pending job to any free GPU immediately upon becoming available. While such rules do not guarantee global optimality, they offer high responsiveness and lend themselves to probabilistic analysis. For instance, modeling GPUs as bins and arriving jobs as items enables evaluation of first-fit and best-fit decreasing placement heuristics:  
1. First-fit: assign each job to the first available GPU or time slot. 2. Best-fit: assign each job to the GPU or slot that minimizes leftover capacity. Despite their simplicity, these heuristics draw on combinatorial optimization principles and are straightforward to simulate and analyze. Backfilling is a more advanced heuristic that boosts utilization by opportunistically scheduling smaller jobs ahead of larger, blocked jobs [119]. When the head-of-line job requires multiple GPUs and must wait, backfilling fills idle resources with shorter jobs, thereby reducing overall idle time. This approach is ubiquitous in HPC schedulers [120; 121] and has been effectively adapted for GPU clusters. Dynamic programming (DP) can precisely solve certain simplified scheduling problems using state-space recurrences, where each state represents the set of completed and running jobs. However, the exponential growth of the state space makes DP infeasible at cluster scale. The heterogeneous earliest-finish-time (HEFT) algorithm provides a practical alternative: it leverages DP-inspired analysis on a DAG of tasks, prioritizing and mapping jobs onto heterogeneous processors based on estimated finish times. This approach yields near-optimal schedules without the need for exhaustive enumeration [122; 123]. Hybrid methods combine optimization models with efficient combinatorial algorithms to balance solution quality and scalability. Alloy, for example, constructs a bipartite graph at each scheduling interval--pending jobs on one side, available resources on the other--with edge weights reflecting estimated completion times, and solves a minimum-cost matching to assign jobs so as to minimize overall delay [124]. By leveraging specialized matching algorithms rather than brute-force searches, these hybrid heuristics achieve practical performance at scale. Design takeawaysGreedy policies (e.g., shortest-job-first, first-fit, best-fit) and backfilling excel at minimizing overhead and enabling near-real-time decision-making. However, they can lead to starvation of large DL training jobs or violate fairness in multi-tenant environments. While backfilling boosts GPU utilization by filling idle GPUs with shorter jobs, it can also cause head-of-line blocking for critical workloads if reservation strategies are not carefully designed. DP-inspired approaches like HEFT are effective for DAG-structured tasks but do not generalize well to arbitrary job graphs or mixed training/inference workloads. Hybrid matching-based methods (e.g., bipartite matching in Alloy) strike a balance, achieving high GPU utilization while limiting solver time, but they still rely on accurate task duration estimates.