1 Introduction

In classical scheduling an important measure of the Quality of Service (QoS) of a schedule is the maximum lateness [8]. Every job, among other characteristics, is associated with a due date and the lateness of a job, with respect to a particular schedule, is defined as the difference of the job’s completion time minus its due date, while the maximum lateness is computed as the maximum over all jobs. In this paper, we propose to optimize this QoS objective in the context of power management, where the operating system may change the speed of the processor(s) in order to save energy. In general, high processor speeds imply high performance with respect to the QoS criterion (here the maximum lateness) at the price of high energy consumption.

Formally, an instance of our problem consists of a set of n jobs J={1,2,…,n}, where every job i is associated with a release date r i , a work w i and a delivery time q i , that have to be executed non-preemptively on a single speed-scalable processor. Note that in this setting, where jobs are associated with delivery times instead of deadlines, different jobs may be delivered simultaneously. For a given schedule the lateness of job i is defined as L i =C i +q i , where C i is the completion time of job i and the maximum lateness is defined as \(L_{\max }=\max _{1\leq i\leq n}\{L_{i}\}\). Jobs that attain the maximum lateness in a schedule are referred as critical jobs.

At a given time t, if a processor runs at speed s, then its power consumption is P(s)=s α, where α>2 is a constant. By integrating the power over time we can compute the processor’s energy consumption. That is, if a processor operates at a constant speed s, it executes an amount of work w in w/s time units and consumes an amount of energy E=w s α−1.

As maximum lateness minimization and energy savings are conflicting objectives, we consider two variants: In the, so called, budget variant, we aim in minimizing \(L_{\max }=\max _{i\in J}\{L_{i}\}\) for a given budget of energy. Using the classical three field notation [10], we denote such a problem by \(S1~|~r_{i}~|~L_{\max }(E)\), where S1 denotes a single speed scalable processor. In the second approach, that we call aggregated variant, our objective is to minimize a linear combination of maximum lateness and energy, that is \(S1~|~r_{i}~|~L_{\max }+\beta E\), where β≥0 is a given parameter that specifies the relative importance of energy versus maximum lateness (see [4] for a motivation of the aggregated approach).

In this context, a schedule σ has to specify for every job the time interval during which it is executed as well as its speed over time. It is well known, e.g. [16], that there is an optimal schedule where each job i is executed at a constant speed; this is a consequence of the convexity of speed-to-power function.

Related Work and our Results

Yao, Demers and Shenker, in their seminal paper [16] proposed an optimal polynomial time algorithm for finding a feasible preemptive schedule on a single processor for a set of jobs with release dates and deadlines minimizing the energy used. They also proposed two online algorithms for the same problem (OA and AVR).

Bunde [6] studied the budget variant of the non-preemptive makespan minimization problem for the single-processor case and the multiple processor case with jobs of unit work. He also proved the \(\mathcal {N}\mathcal {P}\)-hardness of the multiprocessor case whenever the jobs have arbitrary works. Pruhs et al. [14] studied the budget variant of the non-preemptive multiprocessor makespan minimization problem in the presence of precedence constraints, and proposed an approximation algorithm. They also gave a PTAS for the case with no precedence constraints.

Albers et al. [3] were the first to consider an aggregated variant for a power-aware scheduling problem by studying online and offline versions of the non-preemptive problem of minimizing the sum of flow times of the jobs plus energy, with jobs of unit work. The flow time of a job is defined as the difference between its completion time and its release date. It has to be noticed that Pruhs et al. [13] have studied the budget variant of this problem. Bansal et al. [4] proved that there is no O(1)-competitive algorithm, for the budget variant, even if all jobs have unit works.

The interested reader may find recent reviews on power-aware scheduling in [1, 2].

In this paper we consider the maximum lateness criterion in the power-aware context. For the budget variant we propose an optimal algorithm for the non-preemptive single processor case with common release dates, while in Section 3 we prove that the problem, in the presence of release dates becomes strongly \(\mathcal {N}\mathcal {P}\)-hard and it does not admit any O(1)-competitive deterministic algorithm. In Section 4, we move to the aggregated variant, and we give an optimal algorithm for the single processor problem with common release dates and a strongly \(\mathcal {N}\mathcal {P}\)-hardness proof for arbitrary release dates. Moreover, we propose a 2-competitive algorithm for the latter case.

2 Budget Variant with Common Release Dates

In this section we present a polynomial-time algorithm for the S1 | | L m a x (E) problem. Our algorithm is based on a number of structural properties of an optimal schedule, deduced by formulating our problem as a convex program and applying the KKT (Karush, Kuhn, Tucker) conditions.

2.1 General form of KKT Conditions

Next, we describe the general form of the KKT conditions for convex programs (see e.g., [5]). Assume that we are given the following convex program:

$$\begin{array}{@{}rcl@{}} \min f(x) \\ g_{i}(x)\leq0, & \qquad\qquad\qquad 1\leq i\leq q \\ h_{j}(x)=0, & \qquad\qquad\qquad 1\leq j\leq r \\ x\in \mathbf{R}^{n} \end{array} $$

Suppose that the program is strictly feasible, i.e. there is a point x such that g i (x)<0 and h j (x)=0 for all 1≤i≤q and 1≤j≤r, where all functions g i and h j are differentiable at x. Let λ i and μ j be the dual variables associated to the constraints g i (x)≤0 and h j (x)=0, respectively. The Karush-Kuhn-Tucker (KKT) conditions are:

$$\begin{array}{@{}rcl@{}} g_{i}(x)\leq0, & \qquad\qquad\qquad 1\leq i\leq q \end{array} $$
(1)
$$\begin{array}{@{}rcl@{}} h_{j}(x)=0, & \qquad\qquad\qquad 1\leq j\leq r \end{array} $$
(2)
$$\begin{array}{@{}rcl@{}} \lambda_{i}\geq0, & \qquad\qquad\qquad 1\leq i\leq q \end{array} $$
(3)
$$\begin{array}{@{}rcl@{}} \lambda_{i}g_{i}(x)=0, & \qquad\qquad\qquad 1\leq i\leq q \end{array} $$
(4)
$$\begin{array}{@{}rcl@{}} \nabla f(x)+\sum\limits_{i=1}^{q}\lambda_{i}\nabla g_{i}(x)+\sum\limits_{j=1}^{r}\mu_{j}\nabla h_{j}(x) =0 \end{array} $$
(5)

KKT conditions are necessary and sufficient for solutions x∈R n, λ∈R q and μ∈R r to be primal and dual optimal, where λ=(λ 1,λ 2,…,λ q ) and μ=(μ 1,μ 2,…,μ r ). We refer to the conditions (1) and (2) as primal feasible, to the (3) as dual feasible, to the (4) as complementary slackness and to the (5) as stationarity conditions, respectively.

2.2 A Convex Programming Formulation

A convex programming formulation of our problem stems from two basic properties of an optimal schedule. First, because of the convexity of the speed-to-power function, each job i runs at a constant speed s i . Second, jobs are scheduled according to the EDD (Earliest Due Date First) rule, or equivalently in non-increasing order of their delivery times; this can be easily shown by a standard exchange argument. Hence, we propose the following formulation where all jobs are considered to be released at time zero and numbered according to the EDD order:

$$\begin{array}{@{}rcl@{}} &\min L \\ C_{i}+q_{i} &\leq& L, \qquad\qquad 1\leq i\leq n \end{array} $$
(6)
$$\begin{array}{@{}rcl@{}} \frac{w_{1}}{s_{1}} &\leq & C_{1}, \end{array} $$
(7)
$$\begin{array}{@{}rcl@{}} C_{i-1}+\frac{w_{i}}{s_{i}} &\leq & C_{i}, \qquad\qquad 2\leq i\leq n \end{array} $$
(8)
$$\begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{n}w_{i}s_{i}^{\alpha-1} &\leq & E \end{array} $$
(9)
$$\begin{array}{@{}rcl@{}} L, C_{i}, s_{i} &\geq & 0, \qquad\qquad 1\leq i\leq n \end{array} $$
(10)

Our objective is to minimize the maximum lateness, L, among all feasible schedules. Constraints (6) ensure that the lateness of each job is at most L, constraints (7) and (8) enforce the jobs to be scheduled according to the EDD rule in non-overlapping time intervals, constraint (9) does not allow to exceed the given energy budget E and constraints (10) ensure that the maximum lateness, the completion times and the speeds of jobs are non-negative. Constraint (9), for α>2, and constraints (7) and (8) are convex, while constraints (6) and (10) and the objective function are linear. Thus, our mathematical program is indeed convex.

This convex program already implies a polynomial algorithm for our problem, as convex programs can be solved to arbitrary precision by the Ellipsoid algorithm [12]. Since the Ellipsoid algorithm is rather impractical, we will exploit this convex program to derive a fast combinatorial algorithm.

2.3 Properties of an Optimal Schedule

In what follows we deduce a number of structural properties of an optimal schedule by applying the KKT conditions to the above convex program.

Lemma 1

For the maximum lateness problem with an energy budget E, the following properties are necessary and sufficient for optimality of a feasible schedule.

  1. (i)

    Each job i runs at a constant speed s i .

  2. (ii)

    Jobs are scheduled according to the EDD rule.

  3. (iii)

    There are no idle periods in the schedule.

  4. (iv)

    The last job is critical, i.e., L n =L max .

  5. (v)

    Every non-critical job i has equal speed with the job i+1, i.e., s i =s i+1 .

  6. (vi)

    Jobs are executed in non-increasing speeds, i.e., s i ≥s i+1 .

  7. (vii)

    All the energy budget is consumed.

Proof 1

In order to apply the KKT conditions to the convex program, we associate to each set of constraints from (6) up to (9), dual variables β i ,γ 1,γ i ,δ, respectively. W.l.o.g. the variables L,C i and s i are positive and, by the complementary slackness conditions, the dual variables associated to the constraints (10) are equal to zero.

Stationarity conditions give that

$$\begin{array}{@{}rcl@{}} \nabla L + \sum\limits_{i=1}^{n}\beta_{i}\nabla\left(C_{i}+q_{i}-L\right) + \gamma_{1}\nabla\left(\frac{w_{1}}{s_{1}}-C_{1}\right)\\ + \sum\limits_{i=2}^{n}\gamma_{i}\nabla\left(C_{i-1} + \frac{w_{i}}{s_{i}}-C_{i}\right) + \delta\nabla\left(\sum\limits_{i=1}^{n}w_{i}s_{i}^{a-1}-E\right) & = & 0\,\, \Rightarrow\\ \left(1-\sum\limits_{i=1}^{n}\beta_{i}\right)\nabla L + \sum\limits_{i=1}^{n-1}\left(\beta_{i}-\gamma_{i}+\gamma_{i+1}\right)\nabla C_{i}\\ +\left(\beta_{n}-\gamma_{n}\right)\nabla C_{n} + \sum\limits_{i=1}^{n}\left(-\gamma_{i}w_{i}s_{i}^{-2}+(a-1)\delta w_{i}s_{i}^{a-2}\right)\nabla s_{i} & = & 0 \end{array} $$

Equivalently, we obtain the following equalities.

$$\begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{n}\beta_{i} &=& 1 \end{array} $$
(11)
$$\begin{array}{@{}rcl@{}} \beta_{i} &=& \gamma_{i}-\gamma_{i+1} 1\leq i\leq n-1 \end{array} $$
(12)
$$\begin{array}{@{}rcl@{}} \beta_{n} &=& \gamma_{n} \end{array} $$
(13)
$$\begin{array}{@{}rcl@{}} (\alpha-1)\delta &=& \frac{\gamma_{i}}{s_{i}^{\alpha}} \qquad 1\leq i\leq n \end{array} $$
(14)

The complementary slackness conditions give that

$$\begin{array}{@{}rcl@{}} \beta_{i}(C_{i}+q_{i}-L) = 0 & 1\leq i\leq n \end{array} $$
(15)
$$\begin{array}{@{}rcl@{}} \gamma_{1}\left(\frac{w_{1}}{s_{1}}-C_{1}\right) = 0 \end{array} $$
(16)
$$\begin{array}{@{}rcl@{}} \gamma_{i}\left(C_{i-1}+\frac{w_{i}}{s_{i}}-C_{i}\right) = 0 & 2\leq i\leq n \end{array} $$
(17)
$$\begin{array}{@{}rcl@{}} \delta\left(\sum\limits_{i=1}^{n}w_{i}s_{i}^{\alpha-1}-E\right) = 0 \end{array} $$
(18)

First, we will show that the properties are necessary for optimality. That is, there is always an optimal schedule satisfying them.

  1. (i)-(ii)

    They have been already discussed above.

  2. (iii)

    First, note that δ≠0. If δ=0 then by (14), we get that γ i =0 for each 1≤i≤n. This, combined with (12) and (13) yields that \({\sum }_{i=1}^{n}\beta _{i}=0\), which is a contradiction because of (11). Since δ≠0, we get by (14) that γ i ≠0 for each 1≤i≤n. Then, equations (16) and (17) give that there is no idle time in any optimal schedule since \(C_{1}=\frac {w_{1}}{s_{1}}\) and \(C_{i}=C_{i-1}+\frac {w_{i}}{s_{i}}\), for 2≤i≤n, respectively.

  3. (iv)

    Since δ≠0, by (14), it follows that γ n ≠0 and finally, because of (13), β n ≠0. So, the last job to finish is always a critical job, by (15).

  4. (v)

    Note that for every non-critical job i, it holds that C i +q i <L and (15) implies that β i =0 for every such job. Hence, if a job i is non-critical \(\beta _{i}=0\Rightarrow \gamma _{i}=\gamma _{i+1}\Rightarrow s_{i}=s_{i+1}\), by (12) and (14), respectively.

  5. (vi)

    By the dual feasibility conditions and the (12) and (14) we get, respectively, that \(\beta _{i}\geq 0\Rightarrow \gamma _{i}\geq \gamma _{i+1}\Rightarrow s_{i}\geq s_{i+1}\). Thus, the jobs are executed with non-increasing speeds.

  6. (vii)

    If the energy budget is not entirely consumed, then by (18), δ=0, which is a contradiction, since, as we have already proved, δ≠0.

Next, we will show that the properties are also sufficient for optimality. That is, any feasible schedule satisfying them must be optimal. In order to show this, it suffices to prove that, given any feasible schedule satisfying the properties, we can always give values to the dual variables such that the KKT conditions are satisfied.

Consider a feasible schedule and let s i and C i be the speed and the completion time of the job i, 1≤i≤n, respectively. Moreover, let L be the maximum lateness of the schedule. We give values to the dual variables as follows.

$$\begin{array}{@{}rcl@{}} \delta &=& \frac{1}{(\alpha-1)s_{1}^{\alpha}}\\ \gamma_{i} &=& \frac{s_{i}^{\alpha}}{s_{1}^{\alpha}}, \quad\quad\quad\quad 1\leq i\leq n\\ \beta_{i} &=& \frac{s_{i}^{\alpha}-s_{i+1}^{\alpha}}{s_{1}^{\alpha}}, \quad 1\leq i\leq n-1\\ \beta_{n} &=& \frac{s_{n}^{\alpha}}{s_{1}^{\alpha}} \end{array} $$

We, now, observe that these values of the dual variables together with the values of the primal variables satisfy the KKT conditions.

Note that

$$\begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{n}\beta_{i} &=& \sum\limits_{i=1}^{n}\frac{s_{i}^{\alpha}-s_{i+1}^{\alpha}}{s_{1}^{\alpha}}=\frac{s_{1}^{\alpha}}{s_{1}^{\alpha}}=1\\ \beta_{i}&=&\frac{s_{i}^{\alpha}-s_{i+1}^{\alpha}}{s_{1}^{\alpha}}= \frac{s_{i}^{\alpha}}{s_{1}^{\alpha}}-\frac{s_{i+1}^{\alpha}}{s_{1}^{\alpha}}= \gamma_{i}-\gamma_{i+1} 1\leq i\leq n-1\\ \beta_{n} &=& \frac{s_{n}^{\alpha}}{s_{1}^{\alpha}}=\gamma_{n}\\ (\alpha-1)\delta &=& \frac{1}{s_{1}^{\alpha}} = \frac{s_{i}^{\alpha}}{s_{1}^{\alpha}}\frac{1}{s_{i}^{\alpha}}=\frac{\gamma_{i}}{s_{i}^{\alpha}} \quad 1\leq i\leq n \end{array} $$

So the stationarity conditions are satisfied.

Consider now a job i, 1≤i≤n. If i is critical, then C i +q i =L. Else, by property (v) we have that, for 1≤i≤n−1,

$$s_{i}=s_{i+1}\Leftrightarrow \frac{s_{i}^{\alpha}}{s_{1}^{\alpha}}=\frac{s_{i+1}^{\alpha}}{s_{1}^{\alpha}} \Leftrightarrow \beta_{i}=0 $$

Thus, (15) is satisfied. By property (i i i), we have that \(C_{1}=\frac {w_{1}}{s_{1}}\) and \(C_{i}=C_{i-1}+\frac {w_{i}}{s_{i}}\), for 2≤i≤n. Therefore, equations (16) and (17) are also satisfied. Furthermore, by property (v i i), all the energy budget is consumed and the equation (18) holds. Hence, the complementary slackness conditions are satisfied.

Finally, in order to complete our proof, it remains to show that the values of all the dual variables are non-negative. The only case for which this is not straightforward, is for the values of variables β i , for 1≤i≤n−1. But, it must be the case that β i ≥0 for all 1≤i≤n−1, because of the property (v i) and the theorem follows. □

We refer to any schedule satisfying the properties of Lemma 1 as a regular schedule. By Lemma 1, every optimal schedule is regular and vice versa; however, there might be feasible, but not optimal, non-regular schedules. By (i,j) we denote a sequence of consecutive jobs i,i+1,…,j. Any regular schedule can be partitioned into groups of jobs, of the form (i,j), where the jobs i−1 and j are critical and the jobs i,i+1,…,j−1 are not. By Lemma 1 (v), all jobs of such a group are executed at the same speed. We denote this common speed by s j and the total amount of work of jobs in (i,j) by \(w(i,j)={\sum }_{k=i}^{j}w_{k}\). Then, the next proposition follows easily from Lemma 1.

Proposition 1

Let i,j, be two consecutive critical jobs of a regular schedule. The speed of each job in the group (i+1,j) equals to \(s_{j}=\frac {w(i+1,j)}{q_{i}-q_{j}}\).

Proof 2

Assume without loss of generality that i completes before j. Since i and j are both critical, they attain equal maximum latnesses, i.e. L i =L j . Moreover, in any regular schedule, by Lemma 1 (iv), there is no idle period between jobs i,i+1,…,j. Furthermore, all jobs i+1,i+2,…,j−1 are non-critical and, by Lemma 1 (vi), they are all executed with speed equal to that of job j. Hence, we get, respectively, that

$$L_{i}=L_{j}\Rightarrow C_{i}+q_{i}=C_{j}+q_{j}\Rightarrow\sum\limits_{k=1}^{i}\frac{w_{k}}{s_{k}}+q_{i} =\sum\limits_{k=1}^{j}\frac{w_{k}}{s_{k}}+q_{j}\Rightarrow s_{j}=\frac{w(i+1,j)}{q_{i}-q_{j}}. $$

Clearly, given that L i =L j and C i <C j , it must be the case that q i ≠q j . □

2.4 An Optimal Combinatorial Algorithm

So far, by proving that the properties of a regular schedule are necessary and sufficient for optimality, we have derived a clear image of the structure of an optimal schedule for the S1 | | L m a x (E) problem. Next, we propose Algorithm BUD which constructs such a schedule in polynomial time. Note that a regular schedule is fully specified by the speeds of the jobs. The rough idea of our algorithm is the following: First, it constructs a preliminary schedule by finding groups of jobs running in non-increasing speeds without taking care of the energy consumption. Second, the algorithm manages the energy consumption w.r.t. the energy budget E and determines the final speeds of all jobs. Let E ′ be the energy consumption of the current schedule at any point of the execution of the algorithm.

Algorithm BUD needs the jobs to be ordered/numbered according to the EDD rule and an initial sorting step is required. Once this step is performed, it starts from job n which is always a critical job and considers all jobs but the first, in reverse order. When a job i, 2≤i≤n, is considered for the first time, its speed s i is set according to Proposition 1, assuming that jobs i−1 and i are critical. If s i ≥s j , for i+1≤j≤n, then s i is called eligible speed and it is assigned to job i; by definition, the speed \(s_{n} = \frac {w_{n}}{q_{n-1}-q_{n}}\) is considered to be eligible. If speed s i is not eligible, i is a non-critical job and it is merged with the (i+1)’s group. More specifically, if c is the last job of this group, then the speeds of jobs i,i+1,…,c are calculated by applying Proposition 1, assuming that i−1 and c are critical while i,i+1,…,c−1 are not. Next, the algorithm examines whether the new value of s i is eligible. If this is the case, then it considers the job i−1. Otherwise, a further merging of the i’s group with the (c+1)’s group, is performed, as before. That is, if \(c^{\prime }\) is the last job of the (c+1)’s group, all jobs \(i,i+1,\ldots ,c^{\prime }\) are assigned the same speed assuming that jobs i−1 and \(c^{\prime }\) are critical, while \(i,i+1,\ldots ,c^{\prime }-1\) are not. This speed, according to the Proposition 1, is equal to \(s_{c^{\prime }} = \frac {w(i,c^{\prime })}{q_{i-1}-q_{c^{\prime }}}\). Note that the job c is no longer critical in this case. This merging procedure is repeated until job i is assigned an eligible speed. In a degenerate case, jobs i,i+1,…,n are merged into one group. When the algorithm has assigned an eligible speed to all jobs 2,3,…,n, it sets s 1=s 2 and its first part completes. Note that s 1 becomes also eligible. An example of the first part of our algorithm is given in Fig. 1i.

Fig. 1
figure 1

The execution of Algorithm BUD for an instance of 3 jobs, without release dates, works 10, 2, 2, delivery times 5, 4, 2, α=3 and E=20

Full size image

Next, Algorithm BUD takes into account the available budget of energy E. If \(E-E^{\prime }\geq 0\), the current schedule’s energy consumption does not exceed the budget of energy, and the surplus E−E ′ is assigned to the first job. Otherwise, the current schedule is regular, except that it consumes an amount of energy greater than E. Then, the algorithm reduces the consumed energy until it becomes equal to E. In fact, it decreases the speed of the first group, by merging subsequent groups with it, if necessary. This merging procedure is different from the one of the first part of the algorithm and it is as follows: let i be the critical job of maximal index with s i =s 1 in the current schedule. Observe that s i >s i+1. The algorithm sets the speed of jobs 1,2,…,i equal to s i+1. This causes a reduction to \(E^{\prime }\) and there are two cases to distinguish: either \(E^{\prime }\leq E\) or \(E^{\prime }>E\). In the first case, the algorithm adds an amount of energy \(E-E^{\prime }\) to jobs 1,2,…,i by increasing their speeds uniformly, i.e. so that they are all executed with the same speed. In the second case, at least one further merging step has to be performed. When the algorithm terminates, it is obvious that \(E^{\prime }=E\). For an example of the second part of our algorithm see Fig. 1ii and iii.

figure a

Theorem 1

Algorithm BUD is optimal for the S1 | | L max (E) problem.

Proof 3

We shall prove that the algorithm satisfies the properties of Lemma 1, i.e., it produces a regular schedule. For convenience, we distinguish two parts in the algorithm: Part I, corresponding to lines 1-6 and Part II, corresponding to lines 7-16, respectively.

Property (i)-(ii): :

The algorithm gives a single constant speed to each job and keeps their initial EDD order.

Property (iii): :

In Part I, the speeds of jobs are assigned according to Proposition 1. Specifically, the algorithm fixes two consecutive critical jobs i and j, i<j, with, potentially, some non-critical jobs between them. Then the speed of the non-critical jobs and the one of the critical job j is defined such that there is no idle period between the jobs. In Part II, no idle period is added between any jobs.

Property (iv) - (v): :

When the speed of job n is initialized, this is done by assuming that it is critical. Next, consider the current schedule just after the completion of Part I. This schedule can be partitioned into sequences of jobs, a+1,a+2,…,b, with a≥1, such that the jobs of each sequence are executed with the same speed which has been assigned by applying Proposition 1, assuming that the jobs a and b are critical. In fact, jobs a and b attain equal lateness. In order for such a sequence to be a group, we should also prove that all but the last jobs are non-critical while the last job is critical.

Let a+1,a+2,…,b be a sequence of jobs. We claim that L i <L b , for a+1≤i≤b−1. Assume, by contradiction, that there exists a job j, where a+1≤j≤b−1, such that L j ≥L b , or equivalently, \(q_{j}-q_{b} \geq {\sum }_{i=j+1}^{b}\frac {w_{i}}{s_{b}}\). Since the last job of a sequence attains equal lateness with the last job of the sequence that follows, we have that L a =L b . This yields that \(q_{a}-q_{b}={\sum }_{i=a+1}^{b}\frac {w_{i}}{s_{b}}\). Therefore, \(q_{a}-q_{j} \leq {\sum }_{i=a+1}^{j}\frac {w_{i}}{s_{b}}\).

Obviously, for any job i, a+1≤i≤b−1, we must have a speed \(s_{i} >\frac {w_{i}}{q_{i-1}-q_{i}}\), since otherwise, it wouldn’t have been merged with another group. That is, \(q_{i-1}-q_{i} > \frac {w_{i}}{s_{i}}\). If we sum the last inequalities for a+1≤i≤j, we get that \(q_{a}-q_{j} >{\sum }_{i=a+1}^{j}\frac {w_{i}}{s_{b}}\), a contradiction.

At this point, we have showed that when Part I completes, if a job i, 2≤i≤n, is critical, then it must be the right extremity of a sequence. Moreover, among all jobs 2,3,…,n, the last jobs of all sequences, including job n, attain equal lateness and the remaining jobs attain smaller lateness. In addition, job 1 attains equal lateness with the last job of the sequence that follows. Recall that, at this point, we set s 1=s 2. Job 1 would have equal lateness with the last job of the sequence that follows for any s 1>0 since the speed of the second group is set by applying Proposition 1, assuming that 1 is critical. So, at the end of Part I, job 1, job n and every last job of a sequence are critical. Therefore, after Part I finishes, Properties (iv) and (v) hold.

In Part II, if no merging step is performed, then the processing time of job 1 is decreased by some t≥0 and its lateness decreases by t, while the processing times and speeds of the other jobs are not modified. So, the lateness of every other job also decreases by t. Hence, the Properties (iv) and (v) hold.

If at least one merging step is performed, then the speed of the jobs in the first group decreases and their processing time increases. Then, in the first group, every non-critical job i has equal speed with the job i+1 that follows, while the speeds of the jobs in other groups remain unchanged. Now, let t i be the total increase in the processing time of job i, 1≤i≤n. Note that this quantity is positive only for jobs belonging to the first group of the current schedule. Then, the lateness of any job i, 1≤i≤n, increases by \({\sum }_{j=1}^{i}t_{j}\); if c 1 is the critical job of the first group, it remains critical after the merging step since its lateness and the lateness of every other job that follows, increase by the same quantity, equal to \({\sum }_{j=1}^{c_{1}}t_{j}\). Note, that if a further merging step is performed, we consider the first two groups as one group. Moreover, the lateness of any job increases by no more than the increase of the lateness of job n, and thus, in the final schedule, job n remains critical and Property (iv) holds. Furthermore, each non-critical job has equal speed with the job that follows and Property (v) holds as well.

Property (vi): :

At the end of Part I, the speeds of jobs are non-increasing since otherwise, a merging step would be performed. Moreover, during Part II, no speed of a job becomes less than the speed of a subsequent job.

Property (vii): :

Recall that \(E^{\prime }\) is the total energy consumed when Part I completes. If \(E^{\prime }\) is less than the energy budget, then the energy of the first job increases until the schedule consumes exactly E units of energy, while if \(E^{\prime }\) is greater than the energy budget E, then the energy consumption of the schedule is gradually decreased until it becomes equal to E.

Let us now consider the complexity of the algorithm. Initially, jobs are sorted according to the EDD rule in \(O(n\log n)\) time. The first part of the algorithm may take O(n 2) time since each merging step takes O(n) time and there can be O(n) merging steps. Also, the algorithm’s second part takes O(n 2) time since the speed of each job may change at most O(n) times. Therefore, the overall complexity of the algorithm is O(n 2).

□

3 Budget Variant with Arbitrary Release Dates

We now consider the budget variant of the maximum lateness problem, where the jobs have arbitrary release dates, i.e., S1 | r j | L m a x (E) and we show that it becomes strongly \(\mathcal {N}\mathcal {P}\)-hard. Moreover, we show that there is no O(1)-competitive algorithm for its online version, even when all jobs have unit works.

3.1 NP-hardness

We reduce 3-PARTITION to the S1 | r j | L m a x (E) problem. 3-PARTITION problem is a well known \(\mathcal {N}\mathcal {P}\)-hard [7] problem where, we are given a positive integer B and a set of 3n positive integers A={a 1,a 2,…,a 3n }, where B/4<a i <B/2 and \({\sum }_{a_{i}\in A}a_{i}=nB\), and we ask if there exists a partition of A into n disjoint sets A 1,A 2…,A n such that, for each 1≤k≤n, \({\sum }_{a_{i}\in A_{k}}a_{i}=B\).

Our reduction is inspired by the \(\mathcal {N}\mathcal {P}\)-hardness proof for the classical 1 | r j | L m a x problem [11], where we are given a set of jobs with each job i having a release date r i , a due date d i and a processing time p i and we seek a schedule minimizing the maximum lateness; note that, the feasibility version of this later problem is also known as the SEQUENCING WITHIN INTERVALS problem [7].

The 1 | r j | L m a x problem can be viewed as a variant of our problem where the speed of each job is part of the instance. Specifically, we consider that each job i has an amount of work w i =p i and it is executed at a constant speed s i =1. Based on this idea, we extend the existing \(\mathcal {N}\mathcal {P}\)-hardness reduction by fixing an energy budget, so that all jobs have to be executed at the same speed s i =1 in order to get a feasible schedule.

Theorem 2

S1 | r j | L max (E) problem is strongly \(\mathcal {N}\mathcal {P}\) -hard.

Proof 4

We construct an instance of S1 | r j | L m a x (E) from an instance of 3-PARTITION as follows. The instance is depicted in Table 1.

  • For each integer a i , 1≤i≤3n, we create a job i with w i =a i , r i =0 and q i =0.

  • We introduce n−1 gadget jobs, where the gadget job i, 3n+1≤i≤4n−1, has w i =B,r i =(2i−6n−1)B and q i =(8n−2i−1)B.

  • We set E=(2n−1)B.

Table 1 An instance of S1 | r j | L m a x (E) reduced from an instance of 3-Partition
Full size table

We shall prove that there is a feasible schedule σ with L m a x =(2n−1)B and total energy consumption E=(2n−1)B if and only if there exists a 3-PARTITION of A.

(\(\Leftarrow \)) For the first direction, assume that A 1,A 2…,A n is a partition of A, where \({\sum }_{a_{i}\in A_{k}}a_{i}=B\) for 1≤k≤n. Then, consider the schedule σ where: (i) each job i corresponding to an integer a i ∈A k , 1≤k≤n, is scheduled during the time interval [2(k−1)B,(2k−1)B], (ii) each gadget job i, 3n+1≤i≤4n−1 is scheduled during the time interval [(2i−6n−1)B,(2i−6n)B], and (iii) all jobs are executed at constant speed s i =1. The schedule σ (see Fig. 2) is feasible and attains maximum lateness equal to L m a x =(2n−1)B. The total energy consumed is \(E={\sum }_{i=1}^{4n-1}w_{i}s_{i}^{\alpha -1}={\sum }_{i=1}^{4n-1}w_{i}=(2n-1)B\).

Fig. 2
figure 2

A feasible schedule σ for S1 | r j | L m a x (E) that attains maximum lateness equal to L m a x =(2n−1)B

Full size image

(\(\Rightarrow \)) For the opposite direction, assume that σ is a feasible schedule with L m a x =(2n−1)B and total energy consumption E=(2n−1)B. In σ, each job i, 1≤i≤3n, must have completion time C i ≤(2n−1)B and each gadget job i, 3n+1≤i≤4n−1, must have completion time C i ≤(2i−6n)B, since L i ≤(2n−1)B for every job i. For notational convenience, let W=(2n−1)B be the sum of works of all jobs. Let also p i be the execution time of job i, 1≤i≤4n−1.

It holds also that the completion time of (the last job of) schedule σ is C m a x =(2n−1)B. To see this, assume for the sake of contradiction that C m a x <(2n−1)B. Then, by the convexity of speed-to-power function, it follows that the total energy consumption in σ will be

$$E(\sigma) = \sum\limits_{i=1}^{4n-1}w_{i}s_{i}^{\alpha-1}=\sum\limits_{i=1}^{4n-1}w_{i} \left(\frac{w_{i}}{p_{i}}\right)^{\alpha-1}\geq W\left(\frac{W}{C_{max}}\right)^{\alpha-1} > (2n-1)B $$

which is not possible because the energy budget is exceeded. With a similar argument, it can be shown that there will be no idle time during the interval [0,(2n−1)B] in σ. Moreover, due to the convexity of the speed-to-power function, among the schedules with makespan C m a x =(2n−1)B which have no idle period during [0,(2n−1)B], only the ones in which all the jobs are executed with speed equal to s j =1 have energy consumption not greater than E=(2n−1). Clearly, σ must be one of these schedules. Hence, every gadget job i, 3n+1≤i≤4n−1, is executed within the whole time interval [(2i−6n−1)B,(2i−6n)B] in σ.

So far we have shown that every gadget job i, 3n+1≤i≤4n−1, spans in σ the time interval [(2i−6n−1)B,(2i−6n)B], while the other jobs i, 1≤i≤3n, span the time intervals [2(k−1)B,(2k−1)B], 1≤k≤n. Therefore, during any interval [2(k−1)B,(2k−1)B], 1≤k≤n, there will be executed a set of jobs with total amount of work B. This execution defines a 3-PARTITION for A. □

3.2 The On-Line Case

Let us now turn our attention to the online version of the S1 | r j | L m a x (E) problem. Bansal et al. [4] gave an adversarial strategy for proving that there is no O(1)-competitive algorithm for the problem of minimizing the total flow of a set of unit work jobs on a single speed-scalable processor. This adversarial strategy consists of batches of jobs, B 1,B 2,…,B k , with all the jobs in batch B i released after the online algorithm has finished all the jobs in B i−1. Following a similar strategy it can be proved that the makespan minimization problem, for a given budget of energy, i.e. the problem S1 |r j , w j =1| C m a x (E), does not admit an O(1)-competitive algorithm. Note that the makespan minimization is a special case of our lateness problem (with q i =0, 1≤i≤n).

Theorem 3

There is no O(1)-competitive algorithm for the online version of the S1 | r j | C max (E) problem, even when jobs have unit works.

Proof 5

In order to prove the theorem, we assume the existence of a ρ-competitive algorithm \(\mathcal {A}\), where ρ>1 is a constant. Then, we reach a contradiction by showing that there is an instance of the problem that cannot be feasibly solved by \(\mathcal {A}\).

We consider a set of jobs consisting of batches B 1,B 2,…, B ℓ , where the batch B i , 1≤i≤ℓ, contains n i =2i−1 unit work jobs which all arrive at the same time; the jobs of the batch B 1 are released at the time r 1=0 while the jobs of the batch B i , 1≤i≤ℓ, are released at time r i . We assume that r i is large enough so that the algorithm \(\mathcal {A}\) has completed the jobs in the batches B 1,…,B i−1 by r i .

We denote by \(C_{max,k}^{\ast }\), 1≤k≤ℓ, the value of the makespan that the optimal offline algorithm achieves for the instance that consists exactly of the jobs in the batches B 1,B 2,…, B k . The term \(C_{max,k}^{\ast }\) is upper bounded by the makespan of the schedule in which all the jobs in B 1,B 2,…, B k are assigned equal speeds such that their energy consumption is equal to the energy budget E and they are executed continuously starting at time r k . Therefore,

$$ C_{max,k}^{\ast}\leq r_{k}+\left(\frac{\left({\sum}_{i=1}^{k} n_{i}\right)^{\alpha}}{E}\right)^{\frac{1}{\alpha-1}} $$
(19)

As \(\mathcal {A}\) is a ρ-competitive algorithm, it must complete all jobs of the batches B 1,B 2, …,B k not later than \(\rho \cdot C_{max,k}^{\ast }\) independently of the number of batches that our original instance contains. Otherwise, it wouldn’t be ρ-competitive for the instance of the problem that consists only of the batches B 1,B 2,…,B k . Let C m a x,k be the completion time of the jobs in batches B 1,B 2,…,B k in \(\mathcal {A}\)’s schedule. Then, it must be the case that

$$ C_{max,k}\leq\rho\cdot C_{max,k}^{\ast} $$
(20)

Let E k be the energy consumption of the jobs in batch B k in \(\mathcal {A}\)’s schedule. Due to the convexity of the speed-to-power function, we have that

$$ E_{k}\geq\frac{n_{k}^{\alpha}}{(C_{max,k}-r_{k})^{\alpha-1}} $$
(21)

By combining inequalities (19), (20), (21) and the fact that \(r_{k}\leq C_{max,k}^{\ast }\), we obtain that

$$E_{k}\geq\frac{n_{k}^{\alpha}}{\left({\sum}_{i=1}^{k}n_{i}\right)^{\alpha}}\frac{E}{(2\rho-1)^{\alpha-1}} $$

Since n i =2i−1 for 1≤i≤k, we conclude that

$$E_{k}\geq\frac{E}{2^{\alpha}(2\rho-1)^{\alpha-1}} $$

Thus, if the number of batches ℓ is large enough, i.e. \(\ell \rightarrow \infty \), the algorithm will run out of energy after having completed ⌈2α(2ρ−1)α−1⌉ batches, so it won’t be able to finish the batches that follow. □

4 Aggregated Variant

In this section, we turn our attention to the aggregated variant of the maximum lateness problem, where our objective is to minimize L m a x +β E, for some β>0. For this variant, in the online case, we are able to overcome the impossibility of obtaining constant-factor competitive algorithms (Theorem 3). Initially, we consider instances in which the jobs have a common release date and we describe how to obtain an optimal offline algorithm for the aggregated variant by slightly modifying our algorithm and its analysis for the budget variant in Section 2. For instances with arbitrary release dates, we explain why our \(\mathcal {N}\mathcal {P}\)-hardness proof for the budget variant implies that the aggregated variant is also \(\mathcal {N}\mathcal {P}\)-hard. Last, we turn our attention to the online case of the aggregated problem in which the jobs arrive over time and we propose a 2-competitive algorithm which schedules the jobs into batches, by repeatedly applying our optimal offline algorithm for jobs with a common release date.

Common Release Dates

When all jobs are released at the same time, S1 | | L m a x +β E, we are able to derive a polynomial algorithm, by using Algorithm BUD in the following way: suppose that we are given the energy consumption E ∗ of an optimal schedule minimizing L m a x +β E. Then, in order to construct such an optimal schedule, it suffices to apply the optimal algorithm for the budget variant with an energy budget equal to E ∗. This means that the optimal schedule for the aggregated variant is a regular schedule, satisfying the properties of Lemma 1 (with budget E ∗). However, in order to construct the optimal schedule minimizing L m a x +β E, we need to compute E ∗. One approach, which has been already suggested in the literature for the total flow time criterion (see [3, 4]), would be to perform a binary search procedure in the interval of all possible energy levels. Here, we describe an alternative approach which resembles to the one we followed for the budget variant.

We first formulate the aggregated variant as a convex program similar to the one for the budget variant. Now, we do not introduce a constraint on the total energy consumption, since it is added in the objective function. By applying the KKT conditions, we obtain almost the same structure (properties) of an optimal solution with one single difference: the energy consumption is not specified by a given budget of energy, but it results from the fact that the speed of the first job should always be equal to a fixed value. Specifically, the Property (vii) of Lemma 1 is replaced by the fact that “the job executed first runs at speed \(s_{1}=\left (\frac {1}{(\alpha -1)\beta }\right )^{\alpha }\) ”. Therefore, in order to obtain an optimal schedule for the aggregated variant, it suffices to do the following: Run lines (1)-(6) of Algorithm BUD. Let σ be the schedule produced. Find the highest-index critical job, i, i≠1, in σ, such that its corresponding sequence, (k,i), has speed s i <s 1. Modify σ such that all jobs 1,2,…,k−1 are executed at speed s 1.

Arbitrary Release Dates

It is not hard to see that if we are given an optimal algorithm for the aggregated variant, then we can obtain an optimal polynomial algorithm for the budget variant by using binary search on the possible values of β and stopping at a value β ∗ such that the energy consumption of the schedule minimizing L m a x +β ∗ E is equal to the energy budget. Since, by Theorem 2, the budget variant is \(\mathcal {N}\mathcal {P}\)-hard to solve, we conclude that the aggregated variant is also \(\mathcal {N}\mathcal {P}\)-hard.

Now, we turn our attention in the online version of the aggregated variant and we derive a 2-competitive online algorithm for the S1 | r j | L m a x +β E problem. The algorithm schedules the jobs in a number of phases by repeatedly applying the optimal offline algorithm for the S1 | | L m a x +β E problem. This approach was introduced in [15]. We denote by σ ∗(J,t) the optimal schedule of a set of jobs J with a common release date t.

Algorithm ALE

Let J 0 be the set of jobs that arrive at time t 0=0. In phase 0, jobs in J 0 are scheduled according to σ ∗(J 0,0). Let t 1 be the time at which the last job of J 0 is finished, i.e., the end of phase 0, and J 1 be the set of jobs released during (t 0,t 1]. In phase 1, jobs in J 1 are scheduled as in σ ∗(J 1,t 1) and so on. In general, if t i is the end of phase i−1, we denote J i to be the set of jobs released during (t i−1,t i ]. Jobs in J i are scheduled by computing σ ∗(J i ,t i ). Next, we analyze the competitive ratio of the algorithm.

Theorem 4

Algorithm ALE is 2-competitive for the online version of the S1 | r j | L max +βE problem.

Proof 6

Assume that Algorithm ALE produces a schedule in ℓ+1 phases. Recall that the jobs of the i-th phase, i.e., the jobs in J i , are released during (t i−1,t i ] and scheduled as in σ ∗(J i ,t i ). Let L m a x,i +β E i be the cost of σ ∗(J i ,t i ), where L m a x,i is the maximum lateness among the jobs in J i and E i be the energy consumed by the jobs of J i . The objective value of the algorithm’s schedule is

$$ SOL=\max_{0\leq i\leq\ell}\{L_{max,i}\}+\beta\sum\limits_{i=0}^{\ell}E_{i} $$
(22)

Now, we consider the optimal schedule. To lower bound the objective value OPT of an optimal schedule, we round down the release dates of the jobs; the release dates of the jobs in phase i, are rounded down to t i−1. Let \(\sigma _{d}^{\ast }\) and O P T d be the optimal schedule for the rounded instance and its cost, respectively. Clearly, any feasible schedule for the initial instance is also feasible for the rounded one. Thus, O P T≥O P T d .

To lower bound O P T d we consider a restricted speed-scaling scheduling problem, i.e., a problem where each job can only be executed by a subset of the available processors. The instance of this problem consists of ℓ+1 available speed-scalable processors M 0,M 1,…,M ℓ and the set of jobs J, with their release dates rounded down, as before. Jobs in J 0 can only be assigned to the processor M 0 and every job in J i can only be executed by one of the processors M 0 or M i , 1≤i≤ℓ. Moreover, it is required that all jobs in J i , 0≤i≤ℓ, are executed by the same processor. Let \(\sigma _{m}^{\ast }, OPT_{m}\) be the optimal schedule and its cost, respectively, for this restricted problem. Obviously, O P T d ≥O P T m since \(\sigma _{d}^{\ast }\) is feasible for the restricted scheduling problem.

Let us now describe an optimal schedule \(\sigma _{m}^{\ast }\). Through a simple exchange argument, it can be shown that the jobs of J i , 0≤i≤ℓ, in an optimal schedule, are executed by the processor M i . Moreover, jobs in J i , for 1≤i≤ℓ, are scheduled according to σ ∗(J i ,t i−1), while for i=0, according to σ ∗(J 0,t 0). Assume that the maximum lateness of the above schedule, is attained by a job of the set J k , 0≤k≤ℓ, in the processor M k . So, let \(L_{max}^{\ast }=L_{max,k}^{\ast }\), where \(L_{max}^{\ast }\), \(L_{max,k}^{\ast }\) is the maximum lateness of the schedules \(\sigma _{m}^{\ast }, \sigma ^{\ast }(J_{i},t_{i-1})\), respectively. Let \(E_{i}^{\ast }\) be the energy consumption of schedule σ ∗(J i ,t i−1). Then,

$$ OPT_{m} = L_{max,k}^{\ast} + \beta{\sum}_{i=0}^{\ell} E_{i}^{\ast} $$
(23)

By considering the schedules σ ∗(J i ,t i−1) and σ ∗(J i ,t i ), it can be easily shown that \(L_{max,i}^{\ast } = L_{max,i} - (t_{i}- t_{i-1})\) and \(E_{i}^{\ast } = E_{i}\). Then, by (22) and (23) it yields that O P T m =S O L−(t k −t k−1). Note that t k −t k−1 is the total processing time of the jobs in J k−1, in the schedule produced by ALE, which is equal to the processing time of the jobs in J k−1 in \(\sigma _{m}^{\ast }\). Recall also that the last job of each set J i attains L m a x,i . Thus, \(t_{k}-t_{k-1}\leq L_{max,k-1}^{\ast }\leq OPT\). Therefore, S O L≤2O P T and Algorithm ALE is 2-competitive for the S1 | r j | L m a x +β E problem. □

5 Concluding Remarks

We presented positive and negative results for the offline and online power-aware versions of the classical maximum lateness scheduling problem. These results, along with the existing literature on power-aware versions of other problems, like makespan and total flow time, form a strong evidence for the complexity of the power-aware scheduling problems: they are in the same complexity class (polynomial or \(\mathcal {N}\mathcal {P}\)-hard) as their classical versions. For polynomial algorithms, the most promising approach consists of deducing strong structural properties of optimal schedules by applying the KKT conditions on a convex programming formulation of the problem. For \(\mathcal {N}\mathcal {P}\)-hardness results, existing \(\mathcal {N}\mathcal {P}\)-completeness reductions of the corresponding classical problems can be adapted, by forcing all jobs to be executed with speed equal to one and considering the processing times as works. An interesting direction for future work concerns the use of resource (energy) augmentation (see [9, 14]) for the online case of the budget variant of the problem, in order to overcome the fact that there is no O(1)-competitive deterministic algorithm (see Theorem 3). It is also interesting to improve the competitive ratio of Algorithm ALE, in Section 4, for the aggregated variant.