# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Learning-Based Adaptive Algorithms  
Learning-based algorithms harness machine learning--via supervised prediction or reinforcement learning--and adapt over time using feedback from historical logs or live system metrics [157; 158; 159]. Rather than relying on fixed rules, these methods continually refine their policies as workload patterns evolve. Supervised prediction models: Predictive models are trained on job features--such as neural network architecture, input size, and user identity--to forecast metrics like runtime, memory footprint, or scaling behavior. A scheduler can then implement a data-driven SJF by ordering jobs according to predicted runtimes. To mitigate mispredictions, jobs that exceed their expected duration are demoted to a lower-priority queue, preserving fairness and robustness. In heterogeneous GPU clusters, models estimate performance across hardware types. [PERSON] benchmarks workloads to derive throughput estimates for A100 versus V100 GPUs, adapting classical policies to maximize efficiency in mixed environments [57]. Likewise, GENIE uses lightweight profiling to predict deep learning job latencies and throughputs, enabling a QoS-aware scheduler that meets latency and throughput targets [160]. Interference prediction further enhances sharing. Co-scheML profiles ML applications offline to learn co-location slowdown patterns and predicts whether a new job can safely share a GPU without degrading performance [161]. Remaining-time predictors leverage in-flight metrics--epochs completed or loss curves--to decide if a job should be allowed to finish or be preempted, as in SLAQ's loss-gradient prioritization [108]. Forecasting tools like Bamboo and Parcae anticipate spot-instance revocations, adjusting parallelism ahead of interruptions to maintain throughput [162]. By replacing conservative or user-provided estimates with learned predictions, supervised methods often outperform traditional backfilling--moderate accuracy alone can yield significant reductions in waiting time and improved resource utilization. Reinforcement learning-based scheduling: RL casts scheduling as a sequential decision problem: the scheduler (agent) observes the cluster state (job queue, GPU availability), takes actions (dispatch or preempt jobs), and receives rewards reflecting metrics like negative waiting time, throughput, or fairness. Over repeated interactions, the agent refines its policy to maximize cumulative reward. Early systems such as DeepRM [82] tame the combinatorial state by limiting the number of waiting jobs and discretizing time and resource slots. They encode the cluster as an \"image\" of resource occupancy plus job demands and train a neural network to output a scheduling distribution. [PERSON] extends this idea to DAG-structured workloads: a graph neural network embeds each job's task graph and a policy network selects which task or workflow to advance next, outperforming heuristics like SRTF and fair sharing under variable load [127]. Likewise, HeteroG applies a GNN-based RL agent to jointly learn device placement, parallelism, and communication strategies for DNN (deep neural network) training DAGs [163]. RL's flexibility also enables multi-objective rewards--for example, minimizing average slowdown minus a fairness penalty--which can reveal nuanced trade-offs beyond fixed heuristics. [PERSON] et al. [164] demonstrate this by training an LLM scheduler to avoid co-scheduling network-heavy jobs on the same switch, reducing contention and boosting throughput. Despite its promise, deploying RL on live clusters faces four intertwined challenges. Exploration-versus-exploitation tension forces policies to try suboptimal actions to improve over time, but this experimentation can disrupt tenants. As a result, most practitioners pre-train offline--using simulators or historical traces--and then periodically fine-tune as hardware or workloads evolve. State-space explosion occurs because real clusters manage hundreds of concurrent jobs.