 |
Conference papers
Speed scaling for maximum lateness
Abstract : We consider the power-aware problem of scheduling non-preemptively a set of jobs on a single speed-scalable processor so as to minimize the maximum lateness. We consider two variants of the problem: In the budget variant we aim in finding a schedule minimizing the maximum lateness for a given budget of energy, while in the aggregated variant our objective is to find a schedule minimizing a linear combination of maximum lateness and energy. We present polynomial time algorithms for both variants of the problem without release dates and we prove that both variants become strongly -hard in the presence of arbitrary release dates. Moreover, we show that, for arbitrary release dates, there is no O(1)-competitive online algorithm for the budget variant and we propose a 2-competitive one for the aggregated variant.
https://hal.archives-ouvertes.fr/hal-00820163
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Friday, May 3, 2013 - 12:00:50 PM
Last modification on : Friday, January 8, 2021 - 5:48:02 PM
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Friday, May 3, 2013 - 12:00:50 PM
Last modification on : Friday, January 8, 2021 - 5:48:02 PM
