# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Components of a Model
Gang scheduling is often assumed for multi-GPU jobs, meaning a job requiring \(g_{j}\) GPUs only starts when all \(g_{j}\) GPUs are free, and those GPUs remain dedicated until the job finishes [85; 86; 44; 87]. Some models ignore inter-GPU communication overhead, whereas others explicitly optimize job placement to minimize it [88; 89]. Finally, models differ in whether they assume cluster homogeneity or account for mixed GPU types and generations [44; 55]. Scheduling timeline: Scheduling models vary in their representation of time, adopting either discrete or continuous frameworks. Discrete-time formulations divide the schedule into uniform slots, which are well suited to [PERSON] decision processes and dynamic programming approaches [82]. Continuous-time models, by contrast, treat job arrivals and completions as asynchronous events, capturing finer temporal dynamics. Many models further simplify by assuming non-preemptive execution, where jobs run to completion once scheduled. Preemptive models--used for GPU time-sharing or when supporting checkpoint-and-restart--must quantify preemption overheads [90]. Finally, time-sharing frameworks introduce a _time quantum_, the fixed interval for which GPUs are leased to jobs before the scheduler reevaluates resource allocations [91]. Objectives: Let the system state be defined by the set of pending jobs and available GPUs. A scheduling model then specifies an objective function to optimize and a set of constraints to enforce. At a high level, the scheduler must decide which jobs to run, when, and on which GPUs to optimize metrics such as completion time or throughput. Formally, this becomes a combinatorial optimization problem: for example, binary variables \(x_{j,k,t}\in\{0,1\}\) can indicate whether job \(j\) starts on GPU \(k\) at time \(t\). Constraints ensure each GPU runs at most one job at a time, that job \(j\) occupies \(g_{j}\) GPUs for its processing time \(p_{j}\), and that allocations respect job demands and hardware limits (e.g., preventing over-allocation under multi-instance virtualization). Even simple objectives--such as minimizing makespan \(C_{\max}\) on \(m\) identical machines (problem \(P\parallel C_{\max}\))--are NP-hard for \(m\geq 2\)[92]. Similarly, minimizing total completion time \(\sum_{j}C_{j}\) or average waiting time is NP-hard [93; 94]. Consequently, exact optimization is intractable at scale, and most models instead provide a formal foundation for developing and analyzing heuristics and approximation algorithms [95]. A summary of common scheduling objectives appears in Table 3.  
Beyond the core objectives defined in Table 3, scheduling models often refine or combine multiple performance metrics. Many objectives are functions of a job's completion time \(C_{j}\), or related measures such as waiting time \(W_{j}=C_{j}-r_{j}-p_{j}\). Common examples include minimizing average waiting time, or maximizing throughput, i.e., the number of jobs completed per unit time [96]. Alternative objectives target the makespan \(\max_{j}C_{j}\), deadline compliance, or fairness metrics like slowdown--the ratio of a job's response time to its processing time--to prevent excessive delays for any job [81; 97]. Fairness is a central concern in many models. Schedulers may minimize the maximum slowdown across all jobs or ensure that each job's performance is at least as good as if it ran in isolation on an equal share of the cluster. Mechanisms such as dominant resource fairness (DRF) and its variants (e.g., implemented in Dorm) aim to allocate the dominant resource--GPUs--equitably among users over time [98; 99]. Energy efficiency is another critical objective. Some formulations incorporate constraints or multi-objective functions that trade-off performance and power consumption. Techniques like dynamic voltage and frequency scaling (DVFS) or powering down idle GPUs can be modeled to minimize total energy usage [100; 101; 102; 103; 104]. Energy-aware schedulers seek to reduce GPU power draw while still meeting performance SLOs [105; 106; 107].