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

Alexander Lindermayr; Nicole Megow; Martin Rapp

cs.DSFeb 2, 2023

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

Authors: Alexander Lindermayr, Nicole Megow, Martin Rapp

Organizations: University of Bremen, Faculty of Mathematics and Computer Science, Germany · Faculty for Informatics, Karlsruhe Institute of Technology, Germany

Abstract

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.

Figures & tables

Figure 1: The execution time and speedup of the big over LITTLE cores on an Arm big.LITTLE heterogeneous processor varies strongly between jobs and different input data. Variations of the speedup w.r.t. input data are large for some jobs (e.g., water-nsquared ) but small for others (e.g., fmm ).

Figure 2: Real experiments on a HiKey 970 board. The experiments are each repeated 3 times with the same workload but different random noise for speed predictions. Shaded areas show the standard deviation.

Figure 3: Distribution of the system load with speed-ordered Round Robin ( Algorithm 5 ).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Synthetic experiments. The experiments are each repeated 20 times with different random workloads.

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

Learning-Augmented Online Scheduling with Parsimonious Preemption
May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrCombinatorial Optimization Learning-Augmented Algorithms
University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.
Robust Non-Clairvoyant Scheduling with Classification Models
Oct 1, 2026Anthony Dugois, Vincent Fagnon, Giorgio LucarelliRobust Optimization Learning-Augmented Algorithms
Univ. Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F-25000 Besançon, France · Université de Lorraine, LCOMS, Metz, France
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosCombinatorial Optimization Learning-Augmented Algorithms
The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

May 22, 2026J/K move · Enter open · S save

Learning-Augmented Online Scheduling with Parsimonious Preemption

Mugen Blue, Sungjin Im, Alexander Lindermayr

University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.

Combinatorial Optimization Learning-Augmented Algorithms

Open paper AskPDF arXiv

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include

O(1)

-competitive algorithms for single and unrelated parallel machines with only

O(1)

preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.

Abstract

Combinatorial Optimization

Explore similar work

Learning-Augmented Online Scheduling with Parsimonious Preemption

Robust Non-Clairvoyant Scheduling with Classification Models

Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling