Speed scaling for maximum lateness

Evripidis Bampis (1) , Dimitrios Letsios (2, 1) , Ioannis Z. Milis (3) , Georgios Zois (4, 1)

1 RO - Recherche Opérationnelle
2 IBISC - Informatique, Biologie Intégrative et Systèmes Complexes
3 DI NKUA - Department of Informatics and Telecomunications [Kapodistrian Univ]
4 Dept. of Informatics

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.

Keywords: Speed scaling; Release date; Power-aware; Polynomial-time algorithms; Linear combinations; Maximum lateness; On-line algorithms

Domains: Operations Research [cs.RO]

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⟩