# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Classical Optimization Algorithms
Consider a job set \(J\) with release times \(r_{j}\), deadlines \(d_{j}\), and processing times \(p_{j}\) on a single GPU. Define \(U_{j}=1\) if the job \(j\) is finished by its deadline and \(U_{j}=0\) otherwise. The feasibility problem \(1|r_{j},d_{j}|\sum_{j}U_{j}\)--selecting the largest subset of jobs that meet their deadlines--admits an \(O(2^{|I|},|J|)\) state-space DP, while its non-preemptive and preemptive generalizations can be solved in \(O(n^{7})\) and \(O(n^{10})\) time respectively [144]. When deadlines and processing times are small integers, a time-indexed DP yields a pseudo-polynomial algorithm, making it practical for moderate-scale instances. Although full DP is often infeasible at large scale, it is optimal for key cases. For example, earliest-deadline-first (EDF) is provably optimal for preemptive scheduling with deadlines on a single machine [145]. In the non-preemptive setting, DP can enumerate subsets in increasing order of \(d_{j}\) to maximize throughput exactly, but its exponential term confines its use to small job sets. Beyond ordering, DP also applies to resource-allocation subproblems: it can jointly optimize GPU-count assignments, batch sizes, or parallelization granularity for individual jobs by exploring all allocation states [137]. In production GPU schedulers, DP is often invoked selectively within hybrid frameworks. For instance, OASiS embeds a polynomial-time DP inside an online primal-dual algorithm to determine worker/parameter-server allocations that maximize aggregate utility under time-varying capacities [146]. The DP runs only for a small set of high-priority jobs, while lower-priority jobs revert to greedy heuristics. This \"bounded DP \(+\) greedy\" approach achieves near-optimal throughput with per-decision latencies below 100 ms on real cluster traces. ILP/MILP formulations and solvers: MILP provides a general framework for scheduling: introduce a binary decision variable \(x_{j,k,t}\) for each job \(j\), GPU \(k\), and start time \(t\); add linear constraints for assignment, capacity, and makespan; and use a MILP solver to search for the optimal solution. For identical GPUs and makespan minimization \(P\|C_{\max}\), define  
\[J=\{1,\ldots,n\},\quad G=\{1,\ldots,m\},\quad T=\{0,\Delta,2\Delta,\ldots,H\},\]  
and  
\[x_{j,k,t}= \begin{cases}1&\text{if job $j$ starts on GPU $k$ at time $t$}\\ 0&\text{otherwise}\end{cases} \]  
Then the time-indexed MILP is  
\[\min C_{\max}\] subject to \[\sum_{k\in G}\sum_{t\in T}x_{j,k,t}=1 \forall j\in J\] (assign) \[\sum_{j\in I}\sum_{\tau=\max\{0,t-p_{j}+\Delta\}}x_{j,k,\tau}\leq 1 \forall k\in G,t\in T\] (capacity) \[t+p_{j}x_{j,k,t}\leq C_{\max} \forall j\in J,k\in G,t\in T\] (makespan) \[x_{j,k,t}\in\{0,1\}\] \[C_{\max}\geq 0\]  
This formulation uses \(O(n,m,|T|)\) binary variable and is strongly NP-hard even for \(m=2\)[147]. Generic branch-and-bound solvers (Gurobi, CPLEX) typically handle up to \(\sim 50\) jobs and \(\sim 10\) GPUs before runtimes become prohibitive. Two common relax-and-round strategies mitigate this:  
1. Continuous relaxation: Replace \(x_{j,k,t}\in\{0,1\}\) with \(0\leq x_{j,k,t}\leq 1\), solve the LP, then round the fractional solution. List-scheduling rounding: Sort jobs by LP-derived completion times \(\hat{C}_{j}\) and assign greedily to the earliest available GPU. When release times are present, online list-scheduling variants achieve a 2-competitive ratio [148; 149]. Although full MILP is rarely used online, it serves as a ground-truth oracle for benchmarking heuristics under simplified assumptions [57]. Structure-exploiting solvers: Special cases admit faster combinatorial algorithms. If preemption is allowed and communication costs are ignored, each scheduling epoch reduces to a bipartite matching problem, solvable via the Hungarian algorithm in \(O(n^{3})\) time [124].