Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
Alexander Lindermayr, Nicole Megow, Martin Rapp
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.
BibTeX
@inproceedings{icml2023_speedobliviouson,
title = {Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary},
author = {Alexander Lindermayr and Nicole Megow and Martin Rapp},
booktitle = {ICML 2023},
year = {2023}
}