# Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 2 Feb 2023.

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

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [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)
- [An Adversarial Model for Scheduling with Testing](https://mlsanity.com/paper/1709.02592/) (2017)
- [Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling](https://mlsanity.com/paper/1703.01634/) (2017)
- [Speed-Robust Scheduling -- Sand, Bricks, and Rocks](https://mlsanity.com/paper/2011.05181/) (2020)
- [Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times](https://mlsanity.com/paper/2102.06904/) (2021)
- [Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines](https://mlsanity.com/paper/1511.07826/) (2015)
- [Explorable Uncertainty in Scheduling with Non-Uniform Testing Times](https://mlsanity.com/paper/2009.13316/) (2020)
- [Improved Approximations for Unrelated Machine Scheduling](https://mlsanity.com/paper/2211.10398/) (2022)
- [Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations](https://mlsanity.com/paper/1707.08039/) (2017)

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

- [Out-of-Distribution-Aware Electric Vehicle Charging](https://mlsanity.com/paper/2311.05941/) (2023)
- [Energy-Efficient Scheduling with Predictions](https://mlsanity.com/paper/2402.17143/) (2024)
- [A Data-Driven Approach to Dataflow-Aware Online Scheduling for Graph Neural Network Inference](https://mlsanity.com/paper/2411.16342/) (2024)
- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

We consider online scheduling on unrelated (heterogeneous) machines in a speed-oblivious setting, where an algorithm is unaware of the exact job-dependent processing speeds. We show strong impossibility results for clairvoyant and non-clairvoyant algorithms and overcome them in models inspired by practical settings: (i) we provide competitive learning-augmented algorithms, assuming that (possibly erroneous) predictions on the speeds are given, and (ii) we provide competitive algorithms for the speed-ordered model, where a single global order of machines according to their unknown job-dependent speeds is known. We prove strong theoretical guarantees and evaluate our findings on a representative heterogeneous multi-core processor. These seem to be the first empirical results for scheduling algorithms with predictions that are evaluated in a non-synthetic hardware environment.