# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Summary of Scheduling Algorithms and Their Applicability Concerns  
We conclude by summarizing which classes of scheduling algorithms are best suited to different operating conditions and then discuss the practical challenges of deploying custom policies in real-world GPU clusters. Applicability by scenario: The suitability of a scheduling strategy hinges on the information hierarchy, workload stochasticity, and cluster composition that prevail at deployment time. In offline deterministic settings--where every job's size and precedence constraints are known up front--exact algorithms such as MILP or DP achieve provably optimal schedules, while even well-tuned greedy heuristics can deviate sharply from the optimum. Conversely, many production clusters operate online under heavy-tailed arrival processes: DL training queues, for instance, exhibit unknown and highly skewed job sizes; here, queueing-theoretic disciplines like the Gittins index or LAS strike a principled balance between fairness and mean slowdown [74]. When the stream instead comprises predictable, quasi-periodic jobs--for example, regularly recurring inference or analytics tasks--static reservations or SJF rules already approach the optimum, with dynamic SJF closing the remaining gap whenever runtime estimates are accurate. Heterogeneity introduces a further axis: clusters sporting multiple GPU generations benefit from throughput-normalized allocators such as Gavel [188], or from two-stage schemes that first match jobs to device classes (via ML prediction or bipartite matching) and then apply a standard scheduler within each class. In multi-tenant cloud environments, the dominant concern shifts to inter-tenant fairness and performance isolation; partial-auction mechanisms (e.g., Themis) or fair-share frameworks such as DRF are therefore layered atop latency-oriented inner loops like SJF to harmonize efficiency with service guarantees. Finally, incorporating PDE-driven scientific workloads (Section 3.6) broadens the taxonomy without altering its conclusions. Their low runtime variance and regular all-reduce cadence make classical bin-packing and communication-aware MILP approaches nearly optimal--much like in stable, single-tenant inference farms. In contrast, reinforcement learning-based schedulers offer little advantage under such steady-state conditions, reinforcing the view that learning-based methods are most effective in bursty, multi-tenant environments. Practical integration and operational challenges: Rolling out a bespoke GPU scheduler is ultimately an exercise in system integration: it must interoperate cleanly with the cluster's resource manager, accommodate the execution models of both distributed batch and interactive jobs, and leverage GPU-specific control APIs without disrupting user workflows. At the control-plane layer, real-time visibility into free and allocated devices is obtained through scheduler extenders or plugins--Kubernetes, for example, exposes a well-defined gRPC interface that many custom schedulers hook into [189]. Multi-node jobs add further complexity: platforms such as Slurm currently lack fine-grained GPU preemption, so any dynamic rescheduling logic must reconcile whole-node allocations across potentially hundreds of ranks. Equally important is tight coordination with deep-learning frameworks such as TensorFlow or PyTorch, whose runtime assumptions favor stable device assignments; enabling preemption therefore entails wiring checkpoint hooks and aligning interruptions with iteration boundaries to achieve \"graceful\" pause-and-resume semantics [190; 191]. Finally, modern devices expose features--NVIDIA's MIG partitions, per-SM utilization counters, or power-limiting knobs--that a scheduler can exploit only by invoking vendor-specific APIs, adding another integration axis. Beyond plumbing, three operational dimensions shape day-to-day viability.