# Permutation Predictions for Non-Clairvoyant Scheduling

arXiv: https://arxiv.org/abs/2202.10199 · HTML: https://mlsanity.com/paper/2202.10199/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 60 references that are in the map.
- First posted on arXiv 21 Feb 2022.

## Builds on (most cited first, 29 of 29)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Uniform Bounds for Scheduling with Job Size Estimates](https://mlsanity.com/paper/2110.00633/) (2021)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Queues with Small Advice](https://mlsanity.com/paper/2006.15463/) (2020)
- [Using Predicted Weights for Ad Delivery](https://mlsanity.com/paper/2106.01079/) (2021)
- [Learning-Augmented Algorithms for Online Steiner Tree](https://mlsanity.com/paper/2112.05353/) (2021)
- [Online Paging with a Vanishing Regret](https://mlsanity.com/paper/2011.09439/) (2020)
- [Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints](https://mlsanity.com/paper/1404.1097/) (2014)
- [SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors](https://mlsanity.com/paper/1404.1943/) (2014)
- [Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling](https://mlsanity.com/paper/1703.01634/) (2017)
- [Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times](https://mlsanity.com/paper/2102.06904/) (2021)

## Built on by (most cited first, 22 of 22)

- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Scheduling with Predictions](https://mlsanity.com/paper/2212.10433/) (2022)
- [Learning-Augmented Online Packet Scheduling with Deadlines](https://mlsanity.com/paper/2305.07164/) (2023)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Energy-Efficient Scheduling with Predictions](https://mlsanity.com/paper/2402.17143/) (2024)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management](https://mlsanity.com/paper/2604.26349/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)
- [Robust Non-Clairvoyant Scheduling with Classification Models](https://mlsanity.com/paper/2610.01343/) (2026)

## Abstract (arXiv)

In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model, which provides a relative order of jobs which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees and that they are learnable in both, theory and practice. We generalize the algorithmic framework proposed in the seminal paper by Kumar et al. (NeurIPS'18) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared to the previously suggested single-machine algorithms.