Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
This addresses scheduling efficiency in heterogeneous computing environments, offering practical solutions with theoretical backing, though incremental in applying predictions to a known bottleneck.
The paper tackles online scheduling on heterogeneous machines without precise speed knowledge, showing impossibility results and overcoming them with competitive learning-augmented algorithms using predictions and speed-ordered models, achieving strong theoretical guarantees and empirical evaluation on a real multi-core processor.
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.