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.