# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Classical Optimization Algorithms  
Classical schedulers rely on deterministic rules or mathematical optimization, without any learning component. We begin with the simplest and still most widely deployed family. Greedy algorithms: Greedy algorithms make locally optimal choices--such as scheduling the \"best\" job first according to a specific heuristic--to drive strong overall performance. A canonical example is shortest-job-first (SJF), which prioritizes jobs with the smallest runtimes. For a job set \(J\) with known processing times \(\{p_{j}\}\) on a single GPU, SJF orders jobs by non-decreasing \(p_{j}\). Denote by \(C_{j}(\sigma)\) the completion time of job \(j\) under schedule \(\sigma\). It is well known that SJF minimizes the sum of completion times, \(\sum_{j\in J}C_{j}\), on a single GPU [140]. Despite its optimality for average completion time, SJF can starve long jobs [141]. Production systems typically counteract this by applying _aging_ or enforcing a cap on maximum waiting time. Backfilling: First-come-first-served (FCFS) with backfilling preserves arrival order for the head-of-queue job but allows smaller jobs to leapfrog when resources are idle [119]. If the front job \(h\) is blocked by insufficient GPUs, the scheduler reserves resources for \(h\) at its earliest start time, then scans the queue for a shorter job \(j\) that can complete before \(h\)'s reservation. This eliminates idle gaps while ensuring \(h\) is never delayed. Packing on multiple GPUs: When more than one identical GPU (\(m>1\)) is available, placement reduces to a bin-packing problem that is typically handled with simple list-scheduling heuristics. The first-fit (FF) strategy scans the job queue in order and assigns the earliest job whose demand \(g_{j}\) can be satisfied by the current set of free GPUs \(B\), whereas best-fit (BF) looks only at the jobs that fit and chooses the one that leaves the smallest residual capacity \(|B|-g_{j}\). Implemented with a heap, both heuristics run in \(O(|J|\log|J|)\) time, and [PERSON]'s classic bound guarantees that each achieves a \(\left(2-\frac{1}{m}\right)\)-approximation of the makespan for identical machines, with BF inheriting the same ratio by dominating FF [142]. Heterogeneous clusters: On clusters with diverse GPU types \(T=\{\tau_{1},\ldots,\tau_{8}\}\), naive FF/BF degrade because a job's throughput varies by device. [PERSON] [57] addresses this by probing each job's per-device throughput \(\phi_{j,\tau}\) and scheduling in the transformed space of _effective GPU-seconds_, thereby extending classical packing heuristics while preserving fairness. Scalability: All above heuristics maintain a priority queue or balanced tree, incurring \(O(\log|J|)\) overhead per scheduling event. This yields sub-millisecond decision latencies even with hundreds of queued jobs--critical for environments with frequent arrivals and completions. Their main limitation is the lack of worst-case guarantees beyond [PERSON]'s bound and potential starvation under pathological workloads. Nevertheless, empirical studies show that well-tuned greedy rules strike a favorable balance between utilization and responsiveness in production clusters (for deep learning supercomputers, MARBLE refines FF by dynamically resizing each job's GPU allocation using its empirical scalability curve, further boosting throughput [143]). Recent advances also target multi-GPU deep-learning workloads in HPC settings. For example, MARBLE [143] dynamically determines the optimal number of GPUs per job--based on pre-profiled scalability curves--and employs suspend/resume operations to co-schedule multiple jobs on the same node, exploiting non-linear scaling to reduce overall completion times on systems like Summit. Dynamic programming: When local heuristics are insufficient, researchers have explored exact but more computationally expensive methods, such as dynamic programming(DP). DP computes exact schedules for a variety of small-scale subproblems, at the cost of exponential or high-polynomial time.