Title: Speed Predictions for Online Energy-Efficient Scheduling
Abstract: We consider the scheduling problem of online speed scaling where the goal is to minimize the energy consumption of a machine that controls the speed at which jobs are processed. Recent work has leveraged the learning-augmented framework, where the algorithm is provided with predictions about jobs that will arrive in the future, to manage power usage more efficiently.
We propose a novelprediction model for speed scaling where the predictions are about the machine speed (the output), instead of the jobs (the input). Machine speed predictions have multiple advantages. They are succinct and do not require knowledge of all the parameters of all the jobs. They can be provided dynamically, which allows them to incorporate data observed at runtime, instead of being provided up front. Finally, they lead to a natural definition of smoothness that does not require defining a measure of the prediction error.
We give an algorithm for dynamic machine speed predictions that is $(1+\epsilon)$-consistent and $O(1)$-robust. For offline machine speed predictions and job speed predictions, we provide an algorithm that achieves the stronger guarantee of $(1+\epsilon)$-smoothness, while maintaining $O(1)$-robustness. These guarantees are comparable to previous work on speed scaling with predictions, but without having to predict the entire input.
Bob Guo
Email