Speed Scaling for Maximum Lateness

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, under a given budget of energy. In the offline setting, our main contribution is a combinatorial polynomial time algorithm for the case in which the jobs have common release dates. In the presence of arbitrary release dates, we show that the problem becomes strongly NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {N}\mathcal {P}$\end{document}-hard. Moreover, we show that there is no O(1)-competitive deterministic algorithm for the online setting in which the jobs arrive over time. Then, we turn our attention to an aggregated variant of the problem, where the objective is to find a schedule minimizing a linear combination of maximum lateness and energy. As we show, our results for the budget variant can be adapted to derive a similar polynomial time algorithm and an NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {N}\mathcal {P}$\end{document}-hardness proof for the aggregated variant in the offline setting, with common and arbitrary release dates respectively. More interestingly, for the online case, we propose a 2-competitive algorithm.