# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Comparative Analysis  
In this subsection, we evaluate the major categories of scheduling algorithms according to four key dimensions: computational complexity, performance characteristics, scalability, and the environments in which they excel. Complexity and decision speed: Classical heuristics--such as greedy or rule-based methods--offer extremely low decision latency, often operating in \(O(\log n)\) time when using priority queues. Consequently, they can react to job arrivals and completions almost instantaneously relative to typical runtime durations. By contrast, ILP- and MILP-based approaches incur substantially greater computational cost: solving a moderately sized MILP can require seconds or even minutes, rendering these methods impractical for real-time scheduling events. Nevertheless, they remain viable for coarse-grained optimization tasks--for example, computing an optimal allocation hourly. Metaheuristics like GA and SA similarly demand considerable time to converge, making them better suited for offline analysis or periodic batch scheduling rather than real-time decision-making. Queueing-theoretic policies (e.g., LAS or Gittins index) perform lightweight per-job updates--such as tracking cumulative service--at negligible expense. Likewise, RL policies, once trained, execute scheduling decisions with minimal overhead: neural network inference or table lookups typically complete in milliseconds or less on contemporary hardware. Overall, heuristics, queueing strategies, and trained RL models scale efficiently to thousands of jobs with low runtime overhead, whereas ILP formulations and iterative optimization techniques struggle to scale beyond a few hundred jobs without substantial simplification. For instance, DynamoML integrates fractional GPU sharing, workload-aware gang scheduling, and SLA-driven auto-scaling as Kubernetes operators, yet still achieves per-event decision times under 100 ms while managing hundreds of concurrent jobs in real clusters [172]. Quality of schedule: When ranked by theoretical proximity to optimal performance, exact ILP solutions remain unsurpassed within their modeling assumptions, although they often omit system-level factors such as preemption costs and workload heterogeneity. RL schedulers can empirically approach optimality when supplied with abundant training data and expressive policies, yet formal convergence guarantees are rare and highly sensitive to the training regime. Lightweight greedy heuristics deliver strong average-case results but can deviate markedly from optimality on adversarial inputs, while queueing-theoretic rules--most notably the Gittins index--offer provable optimality for specific objectives (e.g., minimizing mean slowdown in a single-server queue) but may sacrifice utilization or strict fairness in broader settings. Empirical evidence thus reveals inherent trade-offs: policies that aggressively pack GPUs to maximize utilization often prolong waits for small jobs, whereas LAS-like time sharing improves responsiveness at the cost of resource efficiency. Hybrid methods attempt to reconcile these goals, mitigating under-utilization while preserving fairness and interactivity. Choosing a concrete algorithm therefore hinges on the dominant performance goal. To minimize average job-completion time (JCT), size-based disciplines such as SRPT or Gittinsindex scheduling are theoretically optimal when job sizes (or their distributions) are known, and in practice shortest-job-first (SJF) supplemented with accurate runtime predictions achieves comparable gains [74]. To maximize utilization, dense-packing strategies--best-fit placement, bin-packing heuristics, and non-preemptive FCFS or backfilling--maintain high GPU occupancy and limit idle gaps. To ensure fairness, time-sharing mechanisms such as LAS or round-robin prevent starvation, while cluster-level systems like Themis employ auction-based allocation to provide explicit fairness guarantees at the cost of additional coordination overhead [85].