Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Frédéric Davesne <>
Submitted on : Friday, May 3, 2013 - 12:00:50 PM
Last modification on : Thursday, August 27, 2020 - 3:40:04 PM



Evripidis Bampis, Dimitrios Letsios, Ioannis Z. Milis, Georgios Zois. Speed scaling for maximum lateness. 18th Annual International Computing and Combinatorics Conference (COCOON 2012), Aug 2012, Sydney, NSW, Australia. pp.25--36, ⟨10.1007/978-3-642-32241-9_3⟩. ⟨hal-00820163⟩



Record views