Speed scaling for maximum lateness - Université d'Évry Access content directly
Conference Papers Year : 2012

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.
No file

Dates and versions

hal-00820163 , version 1 (03-05-2013)

Identifiers

Cite

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⟩
110 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More