arXiv:1609.07354v1 [] 22 Sep 2016

Scheduling Under Power and Energy Constraints
Mohammed Haroon Dupty
mohammed.haroon@iiitb.org

Pragati Agrawal
pragati.a.in@ieee.org

Shrisha Rao
shrao@ieee.org

Abstract
Given a system model where machines have distinct speeds and
power ratings but are otherwise compatible, we consider various problems of scheduling under resource constraints on the system which place
the restriction that not all machines can be run at once. These can
be power, energy, or makespan constraints on the system. Given such
constraints, there are problems with divisible as well as non-divisible
jobs. In the setting where there is a constraint on power, we show
that the problem of minimizing makespan for a set of divisible jobs is
N P-hard by reduction to the knapsack problem. We then show that
scheduling to minimize energy with power constraints is also N P-hard.
We then consider scheduling with energy and makespan constraints
with divisible jobs and show that these can be solved in polynomial
time, and the problems with non-divisible jobs are N P-hard. We give
exact and approximation algorithms for these problems as required.
Keywords: computational sustainability, scheduling, power, makespan,
energy, N P-hard, computational complexity, approximation algorithms,
divisible jobs, non-divisible jobs

1

Introduction

For sustainability, it is highly desirable that every system of machines be
as eﬃcient as can be with regard to the resources that it consumes. This
also requires appropriate usage of machines within a larger system, in addition to proper design and operation of individual machines for good solo
performance. Of particular concern is the appropriate scheduling of jobs
over a system of machines. Scheduling of jobs can be considered eﬀective
when it meets stated goals such as minimal makespan (time to completion),
minimal energy consumed, and minimal cost incurred. Thus, it is necessary
to attempt to create eﬀective scheduling algorithms in line with such desirable goals. The concern for energy eﬃciency by scheduling can exist in
1

many types of systems, not just computing systems, hence the design and
analysis of such algorithms can be appropriately classiﬁed under the rubric
of computational sustainability.
General literature on scheduling [1, 2] has considered a multitude of objectives related to time, but has not considered energy and power in the
general setting. Some domain-speciﬁc literature [3] focuses on energy optimality, but calls on particular features and technologies of those domains
(such as DVFS), and does not consider the limits on scheduling due to power,
energy or makespan. Classical work on energy-eﬃcient scheduling, such as
by Yao et al. [4], has focused on the speciﬁc properties of computer processors, and this trend is also seen in recent work [5, 6, 7] which also discuss
energy eﬃciency issues in computing systems exclusively. Their approaches
and results bring few insights into questions concerning energy eﬃciency in
systems such as for chemical engineering [8], passenger transportation [9],
manufacturing processes [10], and electrical power plants [11], which are
controlled by computers but not amenable to analyses solely by framing the
problem as concerning computer processors and electronic components.
It is well known that energy costs are of great signiﬁcance not only in
data centers [12, 13], but in large industrial systems as well [14] as home
appliances, and that the energy consumed by idle machines (also called
“standby power” [15]) is responsible for a signiﬁcant part of their overall energy usage. Hence, the lack of attention to idle power in analyses concerning
energy eﬃciency in general systems is of concern. It is estimated [16] that
idle power constitutes 5–10% of usage in residential settings, and that it is
responsible for 1% of global CO2 emissions.
Even the literature on scheduling for meeting more than one goal, which
is called multi-objective scheduling [17, 18, 19], does not address these issues.
A recent paper by Mansouri et al. [20] takes an important ﬁrst step in
considering makespan as well as energy in general systems, but it considers
only a two-machine system; it does not seem to directly deal with idle power
consumption in machines, and also does not consider restrictions on power
available.
Additionally, however, it is also seen in practice that many if not most
systems also operate under constraints that may be externally or internally
imposed. These may be power, energy, or makespan constraints on the system. Systems connected to smart power grids can provide good examples
for power-constrained scheduling problems. Smart grids and usage characteristics such as demand-side management [21] or demand response [22]
necessitate that systems control their power usage to certain limits lest there
be penalties or other unwelcome consequences. Such concerns with power
2

usage are of course prevalent in conventional industrial systems [23], but
also in large computing systems [24, 25]. Additionally, many contemporary
systems are powered by multiple sources, which almost always have varying
associated energy capacities, as in cases of renewable sources like solar [26]
and wind [27]. Many performance optimization problems [28] for real-time
systems rely on a ﬁxed energy budget during an operation.
Similarly, other problems where there are hard deadlines may require
energy-minimal scheduling while respecting constraints on makespan. Therefore, it is necessary to consider the problems of how scheduling algorithms
can be designed to be eﬀective in terms of optimizing multiple quality parameters such as makespan and energy consumption, while running on systems
subject to diﬀerent kinds of resource constraints.
We consider these problems in the present paper, with a model of resource constrained systems whose machines are similar in their capabilities
but may have diﬀerent working and idle power ratings and working speeds.
Based on diﬀerent types of machines cooperatively running similar jobs, we
classify and analyze the problems of resource constrained oﬄine scheduling
with non-identical interconnected machines and independent jobs. Fundamentally, the jobs run on the machines can themselves be either divisible,
i.e., can be broken up in arbitrary ways into chunks of whatever sizes one
may wish, and non-divisible, in which case the jobs cannot be subdivided.
A little insight suggests that the problems of scheduling non-divisible jobs
are at least as hard as those of scheduling divisible jobs.
Our basic model is general (not domain-speciﬁc) and therefore extensible for more speciﬁc classes of systems. Our analyses with respect to power
and energy can also be translated for systems that consume any other resources (e.g., water, fuel), and are subject to similar constraints from sources
supplying the same.
The problem of minimizing the makespan (time to completion of a set
of jobs) under a power constraint is seen (Section 3) to be N P-hard [29]
even for divisible jobs, by reduction to the knapsack problem [30], a canonical problem in complexity theory. This implies that minimal-makespan
scheduling is hard also for non-divisible jobs.
Next, we consider power constrained energy-minimal scheduling, which
is known [31] to be at least as hard as minimum-makespan scheduling. Quite
obviously, this too turns out to be N P-hard (Section 4).
We then consider the problem of scheduling to minimize the makespan
given energy budget. Unlike other power-constrained scheduling problems,
this problem turns out to be solvable in polynomial time for divisible jobs.
For non-divisible jobs, the scheduling problem to minimize makespan is
3

known to be N P-hard even without any constraints. So with energy constraints, it should be N P-hard as well for non-divisible jobs (Section 5).
Last, we consider the problem of energy minimal scheduling under makespan
constraint. Like the problem of minimal-makespan scheduling under an energy constraint, this too turns out to be solvable in polynomial time for
divisible jobs and N P-hard for non-divisible jobs (Section 6).
These results suggest that many other interesting problems of eﬀective
scheduling under pairs of various resource constraints are computationally
intractable, i.e., unlikely to have optimal general solutions that can be computed eﬃciently. However, while we are essentially presenting negative results, we believe that doing so opens up the possibility for focused approaches
to ﬁnding approximation algorithms and other solutions to such problems.
We give approximation algorithms for divisible jobs given a power constraint: for minimizing makespan (Section 3), and for minimizing energy
consumption (Section 4). Each algorithm is seen to have a bound of (1 +
ǫ)OPT. We then give exact algorithms for minimal makespan and energy
scheduling under respective constraints of energy and makespan for divisible jobs; and approximation algorithms for non-divisible jobs (Section 5 and
Section 6).
In the next section we formally introduce our system model along with
the notations used in this paper.

2

System Model

Consider m machines c1 to cm forming a system C. The working power of
machine ci is denoted as µ(ci ), and the idle power as γ(ci ). The sum of
the idle powers of all the machines is given by Γ. The speed of machine
ci is denoted as υ(ci ). The speed (throughput of work per unit time) of a
machine is ﬁxed throughout its working tenure, and all machines process
identical jobs (so that any job can be run on any machine).
When υ(ci ) = 1, with 1 ≤ i ≤ m, then we can say that the machines
are identical in their working capacities or speeds, implying that they can
execute and complete any job given to them in equal time. And if in that
case all jobs are executed sequentially on one machine, then that time taken
is W .
All machines stay on for the duration of the makespan of the whole set of
jobs. (This is reasonable considering that in many systems the cycle time to
stop/restart a machine is large; however, it is not a restrictive assumption,
as stopping idle machines is equivalent to the idle power of those machines

4

being zero.)
All machines in the system work in parallel, and the maximum working
time of the system to execute a given set of jobs is T , which is the makespan
of the system for that set of jobs. All jobs are independent, meaning a
job need not wait for completion of any other particular job to start its
execution. This implies that
T = max ti , ∀i, 1 ≤ i ≤ m

(2.1)

If machine ci works only for time ti , then the idle time of machine ci is
given by T − ti . The amount of work done by machine ci is represented by
w(ci ).
w(ci ) = ti υ(ci )
(2.2)
The sum of
Pthe work done by all machines is equal to the total work to
be done, i.e., m
i=1 w(ci ) = W . E represents the energy consumption of the
complete system.
Since we consider the energy consumption in working as well as idle
states, the energy consumed by machine ci is the sum of the energy consumed in the working state and that consumed in the idle state. The energy
consumed by machine ci in the working state is given by µ(ci )ti , and the energy consumed in the idle state by γ(ci )(T −ti ), so the total energy consumed
by ci is given by µ(ci )τ (ci ) + γ(ci )(κ(ci )).
Overall, for the entire system C, we get, after simpliﬁcation:
E=

m 
X
w(ci )
i=1

υ(ci )

(µ(ci ) − γ(ci )) + γ(ci )T



(2.3)

where 1 ≤ i ≤ m.
The system C can have constraints like power budget P , , energy budget
E and makespan budget T . P and E are the maximum power and energy
that can be drawn altogether by all the machines of the system. T is the
maximum time the system is on.
Evidently, we have to assume that P > Γ + min(µ(ci ) − γ(ci )), i.e., the
power is enough to keep all the machines idle and let at least
machine
Pone
m
run a job. It is likewise necessary to assume that P <
i µ(ci ), i.e.,
that the power budget is not suﬃcient to run all machines at once. (For
it is suﬃcient, then the availability of power is no longer a constraint on
scheduling). Similar assumptions are to be made for other constraints also.
In considering the types of jobs to be executed by the system of machines,
the simplest kind are divisible jobs, which can be divided in arbitrary ways,
5

with it being possible to run chunks of any size on any machine [32]. This
is obviously something of an abstraction, but is satisﬁed to an extent in
practice with such tasks as pumping water. The other type of jobs are nondivisible jobs, which come in ﬁxed-size chunks that cannot be divided in
arbitrary ways.
It is of interest to note that scheduling of non-divisible jobs is certainly
no easier than the scheduling of divisible jobs; if a set of non-divisible jobs
can be scheduled eﬀectively (by whatever measure of eﬀectiveness one may
choose to apply in a certain context), then an equivalent set of divisible jobs
can also be scheduled eﬀectively by dividing them into the same chunk sizes
as those of the non-divisible jobs. Therefore, results about divisible jobs set
a baseline of diﬃculty for all jobs; if a certain class of problems is intractable
when the jobs are divisible, it is also that way with non-divisible jobs [2].
We formulate the following problems:
1. Scheduling to minimize makespan given a constraint on power (Section 3).
2. Scheduling to minimize energy given a constraint on power (Section 4).
3. Scheduling to minimize makespan given a constraint on energy (Section 5).
4. Scheduling to minimize energy given a constraint on makespan (Section 6).
We explore the ﬁrst two problems with divisible jobs only since these
are N P-hard even for divisible jobs. For the next two problems we consider
solutions for both divisible and non-divisible jobs. A short summary of the
results is given below along with bounds for the algorithms.

3

Scheduling to Minimize Makespan Under Limited Power

The ﬁrst problem we consider is to minimize the makespan (time to completion of a set of jobs) of system C, while under a power constraint.
Theorem 3.1. If the power budget for a system of machines is limited,
minimizing the makespan for a set of divisible jobs is an N P-hard problem.

6

Problem

Type of
Job

Minimize
makespan
given constraint on
power

Divisible

Minimize energy given
constraint on power

Divisible

Minimize
makespan
given constraint on
energy

Minimize energy given
constraint on makespan

Divisible
Nondivisible

Divisible
Nondivisible

Hardness

Type of
Algorithm

Time
Complexity

Bound

NPhard

Approx.

O(m2 ⌊ mǫ ⌋)

1+ǫ

NPhard

Approx.

O(m log m)

2

Exact

O(m log m)

-

Approx.

O(m2 n)

Exact

O(m log m)

-

Approx.

O(mn)

1+ ηηmax
min

Polynomial
time
NPhard
Polynomial
time
NPhard

19
12

+ǫ

Table 1: Summary of Results
Proof. Obviously, to minimize the makespan, we need to choose a subset of
machines from C to achieve the highest cumulative speed, given the power
constraint. This amounts to ﬁnding some
Pr r < m indices ir (the indices of
υ(ci ) is the greatest possible. In
the machines chosen to run) such that
Pr
υ(cir ), subject to the constraint:
other words, we wish to maximize
r
X

(µ(cir ) − γ(cir )) + Γ ≤ P

(3.1)

Γ can be moved to the right so that P − Γ is treated as one constant, say
Z, and µ(cir ) − γ(cir ) can be likewise
P treated as one variable, say dir . Then
the problem reduces to: maximize
υ(cir ) subject to:
r
X

dir < Z

(3.2)

which is an instance of the knapsack problem [29], a canonical N P-hard
problem.

7

It may be noted that this is a somewhat surprising result, because
minimum-makespan scheduling of divisible jobs in a system without a power
constraint is trivial—one has to just run all machines.
Given the lack of ease, as previously discussed, of scheduling non-divisible
jobs, the following obtains.
Corollary 1. If the power budget for a system of machines is limited, minimizing the makespan for a set of non-divisible jobs is an N P-hard problem.
Therefore, we may generally say that given a limited power budget,
scheduling jobs on a system is an N P-hard problem.

Approximation Algorithm
We give the following approximation algorithm for the objective of minimizing makespan. Without loss of generality, we assume the working and idle
power consumptions, and the speeds of machines to be integers.
As seen in the previous section, the problem of minimizing makespan,
given a constraint on power can be formulated as a knapsack problem. Here
we minimize T or maximize T1 .
maximize
subject to

Xr

υ(cir )
(3.3)

r
X

(µ(cir ) − γ(cir )) ≤ P − Γ

Considering υ(ci ) as proﬁt for component i (machine ci ) and (µ(ci ) −
γ(ci )) as weight of component i (machine ci ), we get the classical knapsack
formulation. Hence we can apply approximation algorithm from the large
set of algorithms developed for knapsack problem.
We use a suitably
modiﬁed version of the well known fully polynomial time approximation
scheme (FPTAS) for the knapsack problem [33]. Let V be the speed of the
fastest machine, i.e., V = maxi υ(ci ). Then mV is a trivial upper-bound on
the speed that can be achieved by any solution. For each i ∈ {1, . . . , m}
and υ ∈ {1, . . . , mV }, let Si,υ denote a subset of {c1 , . . . , ci } whose total
speed is exactly υ and whose total power requirement is minimized. Let
A(i, υ) denote the total power requirement of the set Si,υ (A(i, υ) = ∞ if no
such set exists). Clearly A(1, υ) is known for every υ ∈ {1, . . . , mV }. The
following recurrence helps compute all values A(i, υ) in O(m2 V ) time.

8

A(i + 1, υ) =
(
min{A(i, υ), (µ(ci+1 ) − γ(ci+1 )) + A(i, υ − υ(ci+1 ))},
A(i + 1, υ) = A(i, υ),

if υ(ci+1 ) < υ
otherwise

The maximum speed achievable by the machines with total power bounded
by P is max{υ|A(m, υ) ≤ P }. We thus get a pseudo-polynomial algorithm
for minimizing makespan under power constraints.
If the speeds of machines were small numbers, i.e., they were bounded by
a polynomial in m, then this would be a regular polynomial time algorithm.
To obtain a FPTAS we ignore a certain number of least signiﬁcant bits
of speeds of machines (depending on the error parameter ǫ), so that the
modiﬁed speeds can be viewed as numbers bounded by a polynomial in
m and 1ǫ . This will enable us to ﬁnd a solution whose speed is at least
(1 − ǫ)OPT in time bounded by a polynomial in m and 1ǫ .
Algorithm 1: FPTAS for makespan
input : Set of machines (C), number of machines (m), working
power of machines (µ(ci )), idle power of machines (γ(ci )),
sum of idle power of all the machines (Γ), speed of machines
(υ(ci )), power constraint (P )
output: Working set (R)
1 V ← max∀iǫ{1...m}
υ(ci )
˙
ǫV
2 Given ǫ > 0, let K = m .
3
4

5

i)
For each machine ci deﬁne υ ′ (ci ) = ⌊ υ(c
K ⌋.
With these as speeds of machines, using the dynamic programming
algorithm, ﬁnd the set of machines with maximum total speed, say R.
Return R.

Theorem 3.2. If set R is output by the algorithm 1 and υ(R) denotes
P
∀i∈R υ(ci ) then, υ(R) ≥ (1 − ǫ)OP T .

Proof. Let O denote the optimal set. For any machine ci , because of rounding down, Kυ(ci ) can be smaller than υ(ci ), but by not more than K.
Therefore,
υ(O) − Kυ(O) ≤ mK.
The dynamic programming step must return a set at least as good as O
under the new proﬁts. Therefore,
υ(RR) ≥ Kυ(O) ≥ υ(O) − mK = OP T − ǫV ≥ (1 − ǫ)OP T,
9

where the last inequality follows from the observation that OPT≥ V . It
directly follows that minimum makespan T ≤ (1 + ǫ)OP T .

4

Scheduling to Minimize Energy Under Limited
Power

Minimizing the makespan for a set of jobs running on a system does not
guarantee that the energy consumed is minimized. To see why, we can
compare the problems as done in prior work [31].
If the idle power of every machine is equal to its working power, i.e., if
µ(ci ) = γ(ci ), we have the following from (2.3):
E =
=

m
X
[µ(ci )τ (ci ) + γ(ci )(T − τ (ci ))]

i=1
m
X

µ(ci )T

(4.1)
(4.2)

i=1

Thus, in this particular setting, the energy is minimized if the makespan
T is minimized. However, more generally, the idle power of machines may
be less than their working power, so that γ(ci ) = zi · µ(ci ), where 0 ≤ zi ≤ 1.
In this case, we get:
m
X
[µ(ci )τ (ci ) + γ(ci )(T − τ (ci ))]
E =

=
=

i=1
m
X

[µ(ci )τ (ci ) + zi µ(ci )(T − τ (ci ))]

i=1
m
X

µ(ci )[τ (ci ) + zi T − zi τ (ci )]

(4.3)
(4.4)
(4.5)

i=1

This in turn simpliﬁes to:
E=

m
X

µ(ci )[zi T + τ (ci )(1 − zi )]

(4.6)

i=1

Therefore, in this case, even minimizing T does not minimize E, and the
problem of energy-minimal scheduling is always at least as hard as that of
minimize makespan. This gives us the following.

10

Theorem 4.1. Minimal-energy scheduling of either divisible or non-divisible
jobs, given a power constraint, is N P-hard.
Even more simply, if it were possible to eﬃciently compute minimalenergy schedules, it would be possible to minimize the makespan simply
by using an energy-minimal schedule with µ(ci ) = γ(ci ), which contradicts
Result 3.1.
This too is a surprising result in a way, because it is known [34] that
energy-minimal scheduling of divisible jobs in a system without a power
constraint can be achieved in O(m), i.e., linear time.
Approximation Algorithm
The problem of minimizing energy subject to constraint on power is
harder than minimizing for makespan. To state the problem in more general
form, minimizing energy (E) can be easily seen as maximizing its inverse,
i.e., E1 . Hence the problem can be formally written as:
Pr
υ(cir )
maximize Pr
(µ(cir ) − γ(cir )) + Γ
subject to constraint

r
X

(µ(cir ) − γ(cir )) ≤ P − Γ

(4.7)

Here we cannot ﬁnd proﬁt per unit weight for each element, as the objective function is not a linear function of just one property of elements of
the set. When we need to minimize E, we arrange machines in an order
i )+Γ
and afsuch that the ﬁrst machine is the one with smallest µ(ci )−γ(c
υ(ci )
)−γ(ci )
terwards in non-decreasing order of µ(ciυ(c
, where, 1 ≤ i ≤ m. Since,
i)
here we need to maximize 1/E within power constraint, we need to arrange
machines in such an order that we give a machine more priority if it reduces
more energy consumption of system per unit increase of power consumption. Hence, we arrange machines in an order such that the ﬁrst machine
υ(ci )
and afterwards in non-increasing order
has highest (µ(ci )−γ(ci )+Γ)(µ(c
i )−γ(ci ))
υ(ci )
(µ(ci )−γ(ci ))2 ,

where, 1 ≤ i ≤ m.
Algorithm 2 for minimizing energy is based on this ordering.
The time complexity of Algorithm 2 is also O(m log m). Here the ﬁrst
υ(ci )
.
machine chosen is the one which has maximum (µ(ci )−γ(ci )+Γ)(µ(c
i )−γ(ci ))
Later machines are arranged in decreasing order of their proﬁt to weight
i)
ratio. The proﬁt is µ(ciυ(c
)−γ(ci ) , and weight remains same as previous algorithm, i.e., µ(ci ) − γ(ci ). Now we check the power consumption of machines
of

11

Algorithm 2: Approximation algorithm for reducing energy subject
to power constraint
input : Set of machines (C), number of machines (m), working power of
machines (µ(ci )), idle power of machines (γ(ci )), sum of idle power
of all the machines (Γ), speed of machines (υ(ci )), power constraint
(P )
output: Working set (R)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

for i = 1 to m do
υ(ci )
calculate (µ(ci )−γ(ci )+Γ)(µ(c
i )−γ(ci ))
end
υ(ci )
υ(c1 )
) ← max( (µ(ci )−γ(ci )+Γ)(µ(c
);
( (µ(c1 )−γ(c1 )+Γ)(µ(c
1 )−γ(c1 ))
i )−γ(ci ))
for i = 2 to m do
i)
calculate (µ(ciυ(c
)−γ(ci ))2
end
i)
max-sort ( (µ(ciυ(c
)−γ(ci ))2 );
α ← Γ;
R ← ∅;
A ← C;
for i = 1 to m do
if α < P then
margin ← P − α;
pi ← µ(ci ) − γ(ci );
)−γ(ci )
ei ← µ(ciυ(c
;
i)
ce ←

Γ+

P

(µ(ci )−γ(ci ))
i∈R
P
i∈R

υ(ci )

;

if (pi ≤ margin) ∧ (ce ≤ ei ) then
R ← R + {ci };
else
P
υ(ci−1 )
if (pi ≤ α) ∧ ( i∈R µ(ci−1
)−γ(ci−1 ) <
R ← ci ;
end
A ← C −P
R;
α ← Γ + i∈R (µ(ci ) − γ(ci ));
else
stop;
end
end
working set ← R;

12

υ(ci )
µ(ci )−γ(ci ) )

then

sequentially; if the power consumption of a particular machine is less than or
equal to the margin (the power remaining after already-scheduled machines
draw their power requirements) then we compare the energy of the current
machine with the current energy. When both conditions are satisﬁed, we
add this current machine to our working set R. If the power consumption of
a particular machine is not within the limit, then we compare the proﬁt of
this machine and the sum of proﬁt of machines in working set. If the proﬁt
of this machine is more, then we choose only this particular machine and
update R else we continue with same set R.
Theorem 4.2. The worst case bound for Algorithm 2 to maximize
so the energy consumed is at most twice the optimal.

1
E

is 12 ,

Proof. For the worst case, suppose there are only two machines in the sysυ(c2 )
1)
tem. Taking (µ(c1υ(c
)−γ(c1 )) = (µ(c1 )−γ(c1 )) = (µ(c2 )−γ(c2 )) = (µ(c2 )−γ(c2 )) =
k and P − Γ = 2k − 1. As the bound is given by current performance divided
by optimal performance, we have,
L=

υ(c1 )
Γ+(µ(c1 )−γ(c1 ))
υ(c1 )+υ(c2 )
Γ+µ(c1 )−γ(c1 )+µ(c2 )−γ(c2 )

(4.8)

(Γ + 2(µ(c1 ) − γ(c1 )))
2(Γ + (µ(c1 ) − γ(c1 )))

(4.9)

Γ
2(Γ + µ(c1 ) − γ(c1 )

(4.10)

Solving (4.8) we get:
L=

L=1−

Clearly the value of bound depends upon the power consumption speciﬁcations of the system. The bound depends on the total idle power consumption and value of the diﬀerence between working and idle power speciﬁcation
υ(ci )
is highest and whose inof the machine for which (µ(ci )−γ(ci )+Γ)(µ(c
i )−γ(ci ))
clusion does not violate power constraint. Since idle power will always be
less than working power, L ≈ 1 − 12 = 12 in the worst case, so the worst case
bound for minimization of energy is 2.

5

Minimizing Makespan Given Energy Budget

We analyse the problem of minimizing makespan given energy constraint
with divisible and non-divisible jobs.
13

5.1

Divisible Jobs

Contrary to the problems with power constraint, the problem of minimizing
makespan, given an energy budget with divisible job can be formulated as a
fractional knapsack problem. This is because unlike power fractional amount
of energy can be given to a machine to run for some part of the makespan
of the system. Here we minimize T or maximize T1 .
Xr
maximize
υ(cir )
subject to constraint

r
X
(µ(cir ) − γ(cir ))tir + ΓT ≤ E

(5.1)

Since υ(ci ) gives work done per unit time and power rating gives energy
required per unit time for the machine to operate, we can take their ratio
as a measure of eﬃciency. This will be a measure of amount of work done
per unit energy consumed. Based on this parameter we give an algorithm
to get the minimum makespan and the set of machines to be used.
Algorithm 3 takes Set of machines, working and idle power of machines,
speed of machines, energy constraint (E) and total work as input and gives
the minimum makespan and the subset of machines to be used as output. It
assumes energy is not suﬃcient to complete all work and ﬁnds the maximum
amount of work that can scheduled. The machines are sorted in the order
of their eﬃciency. Now, every machine is given work which the machine can
complete in makespan T . So the machines will be active for an equal amount
of time. This makespan is iteratively decreased based on the number of
machines added to the working set. When the energy constraint is violated
at an addition of a particular machine, that machine is given the fractional
amount of energy available so that all of available energy is used. The time
complexity of Algorithm 3 turns out to be O(m log m).

5.2

Non-divisible Jobs

Since even simple scheduling in multiple parallel machines with indivisible
jobs itself is N P-Hard, the problem of scheduling in parallel machines given
energy constraint is certainly harder. For this we give an approximation
algorithm designed in similar terms as previous algorithm but with indivisible jobs. Here we ﬁnd maximal set of machines which can work within the
Energy constraint. For this we sort the machines in terms of eﬃciency and
add them one by one to the working set if total energy requirement is within
14

Algorithm 3: Algorithm for minimizing makespan given energy budget
input : Set of machines (C), number of machines (m), working
power of machines (µ(ci )), idle power of machines (γ(ci )),
sum of idle power of all the machines (Γ), speed of machines
(υ(ci )), energy constraint (Ec ), total work (W )
output: Working set (R), Makespan (T )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

for i = 1 to m do
i)
calculate µ(ciυ(c
)−γ(ci )
end
i)
max-sort ( µ(ciυ(c
)−γ(ci ) );
R ← ∅;
W
;
To ← υ(c
1)
e ← [(µ(c1 ) − γ(c1 )) + Γ]T
for i = 1 to m do
T ← Ti
eprev ← e
P
e ← ij=1 [(µ(cj ) − γ(cj )) + Γ]T
if e < E then
r ← r + 1;
else
margin ← E − eprev
i)
ψ(pi ) ← margin ∗ ( µ(ciυ(c
)−γ(ci ) )
assign ψ(pi ) amount of work to machine ci .
break;
end
end
T ← Tro
R ← R ∪r+1
j=1 cj
Return T
Return R ∪ {cr+1 }

15

the constraint. We stop at the machine where energy requirement is violated. Now we give maximum amount of work to this machine to ﬁt within
the remaining energy margin. The remaining set of jobs are assigned to the
previously chosen machines by Longest Processing Time(LPT) algorithm.
In LPT algorithm the jobs are ﬁrst sorted in decreasing order of their size
and are assigned to the least loaded machine one by one to minimize the
makespan.
The time complexity of Algorithm 4 is O(m2 n).
19
Theorem 5.1. The worst case bound of Algorithm 4 is ( 12
+ǫ). So the worst
case makespan T for a set of parallel machines given Energy constraint with
non-divisible jobs is ( 19
12 + ǫ) OPT.

Proof. The problem is same as the previous one but with indivisible jobs.
When we sort machines in terms of their eﬃciencies, the last machine which
is added to the working set will be given only the marginal energy left.
So it can’t operate for full makespan. Ideally makespan will be least if we
have exact energy to be distributed among r set of machines proportionately
such that all machines will be active for the same time. But since this is
not always the case, the marginal energy left after selecting r − 1 machines
is allotted to machine r. Since time during which machine cr is active
is less than the makespan of the system, the Optimal solution will give
maximum amount of work possible within the energy margin available to
the machine r. Algorithm 4 uses the well known PTAS for subset sum
problem to take the maximum subset of jobs that can be assigned to the
machine r . So it will return (1 − ǫ)OP T subset size to be assigned to the
machine r. These extra jobs that optimal would have assigned to machine
r need to be accommodated in the r − 1 machines. In worst case this can
increase the makespan of the system by ǫ amount. For scheduling in the
r − 1 machines Algorithm 4 uses Longest Processing Time (LPT) algorithm.
[35] provided the bound of ( 19
12 )OPT for LPT algorithm applied to a system
of parallel machines with diﬀerent speeds. With this bound, the worst case
bound for Algorithm 4 can go up to ( 19
12 + ǫ) OPT.

6

Minimizing Energy Given Limit on Makespan

Here, given a constraint on makespan T , the problem is to ﬁnd the optimal
subset of machines so that energy consumed is minimized. We divide this
problem too between divisible and non-divisible jobs. We show that the
problem of minimizing energy given a limit on the makespan with divisible
16

Algorithm 4: Approximation algorithm for reducing makespan given
energy budget with indivisible job
input : Set of machines (C), number of machines (m), working power of machines
(µ(ci )), idle power of machines (γ(ci )), sum of idle power of all the
machines (Γ), speed of machines (υ(ci )), energy constraint (E), set of
jobs (P), weight of jobs (ψ(pi ))
output: Working set (R), makespan (T )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

for i = 1 to m do
i)
calculate µ(ciυ(c
)−γ(ci )
end
i)
max-sort ( µ(ciυ(c
);
)−γ(ci )
max-sort ψ(pi );
R ← ∅;P
W ← n
i=1 ψ(pi )
W
t(1) ← υ(c
1)
maxt ← 1;
e ← [(µ(c1 ) − γ(c1 )) + Γ]T
for i = 1 to m do
r←i
for j = 1 to n do
k ← argmin∀l∈{1...r} t(l)
ψ(p )

t(k) ← t(k) + υ(c j )
k
if (t(k) > t(maxt )) then
maxt ← k;
end
end
T ← t(maxt )
eprevP
←e
e ← ri=1 (µ(cj ) − γ(cj ))t(i) + ΓT
if e > E then
margin ← E − eprev
find max subset of {ψ(pi ) | ∀i = 1 . . . n} to fit in energy margin with
speed of machine cr
assign all jobs in the subset, to machine cr
r ←r−1
break;
end
end
T ←0
for j = 1 to r do
k ← argmin∀lǫ{1...r} t(l)
ψ(p )

t(k) ← t(k) + υ(k)j
assign the job with weight ψ(pj ) to machine ck
R ← R ∪ cj
if (t(k) > T ) then
T ← t(k);
end
end
Return R ∪ {cr+1 }
Return T

17

jobs is polynomially solvable whereas with non-divisible jobs it is N P-Hard.
We provide exact and approximation algorithms for these problems respectively.

6.1

Divisible Jobs

Like energy, amount of time given for a particular machine is also divisible,
i.e., the constraint parameter can be taken in fractions. Hence, it can be
formulated in terms of fractional knapsack problem.
Energy of the system is given by
E=

r
X
(µ(cir ) − γ(cir ))tir + ΓT

(6.1)

For energy minimality all machines should be given equal amount of time[34].
Then
r
X
[(µ(cir ) − γ(cir )) + Γ]T
E =

E =

r
X

[(µ(cir ) − γ(cir )) + Γ](

w(ci )
)
υir

(6.2)
(6.3)

Hence the problem can be written as
minimize
subject to constraint

r
X
w(ci )
[(υ(cir ) − γ(cir )) + Γ](
)
υir

(

w(ci )
)≤T
υi

(6.4)

We can see that if the jobs are non-divisible this problem becomes N PHard otherwise it is not, i.e., since jobs can be arbitrary divisible, this LP
formulation is perfectly solvable. If it is non-divisible then, it becomes an
integer linear program which is not polynomially solvable.
Algorithm 5 solves this problem in O(m) time. It ﬁrst sorts the machines
based on their eﬃciencies as described in the previous algorithms. Then
it iterates from the most energy eﬃcient machine to least eﬃcient machine
assigning maximum job that the machine can complete within the makespan
limit. The last machine in the subset of machines chosen is provided with
work job that can be ﬁnished before makespan for energy minimality.

18

Algorithm 5: Algorithm for minimizing energy given limit on
makespan with divisible job
input : Set of machines (C), number of machines (m), working
power of machines (µ(ci )), idle power of machines (γ(ci )),
sum of idle power of all the machines (Γ), speed of machines
(υ(ci )), Makespan limit (T )
output: Working set (R)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

for i = 1 to m do
i)
calculate µ(ciυ(c
)−γ(ci )
end
i)
max-sort ( µ(ciυ(c
)−γ(ci ) );
R ← ∅;
W ← total work
for i = 1 to m do
if ((W ≥ 0) ∧ (i ≤ m)) then
w(ci ) ← υ(ci ) ∗ T
Wprev ← W
W ← W − w(ci )
R ← R ∪ ci
if (W < 0) then
Wprev
ti ← υ(c
i)

assign Wprev amount of job to machine ci
end
else
STOP
end
end
Working Set ← R

6.2

Non-divisible Jobs

For non-divisible jobs, the problem formulation becomes an Integer Program which is not solvable in polynomial time. Hence we try to get an
approximation algorithm for the same.
As the makespan is ﬁxed, all machines in the working set should be
active for the maximum amount of time within this constraint. The optimal
algorithm will include least number of most eﬃcient machines from the
19

set of machines to the working set. This implies that any approximation
algorithm will include more number of machines than the optimal. If we
sort the machines based on their eﬃciencies and try to include least number
of these machines to our working set, we see that this problem reduces to a
variant of variable size bin packing problem (VSBP) which is a well studied
N P-Hard problem.
There are many variants of the standard one dimensional bin packing
problem. The most common is given n items with sizes a1 , . . . , an ∈ (0, 1],
ﬁnd a packing in unit-sized bins that minimizes the number of bins used.
Here all the bins are assumed to be of same size. The variant of this problem
is when bins of diﬀerent sizes are allowed. Since, in our problem of scheduling
to minimize energy given a limit on makespan, each machine is assumed to
have diﬀerent speeds, the time taken to complete a job in one machine may
be diﬀerent than the time taken by other machines to complete the same
job. Hence our problem resembles variable size bin packing problem. Hence
we model our approximation algorithm based on VSBP problem.
Algorithm 6 employs a variant of ﬁrst ﬁt decreasing algorithm but without sorting the machines based on their order of speed. In FFD algorithm,
both bins and jobs are sorted based on their sizes. Here jobs are sorted in
non-increasing order of their sizes but machines are sorted based on their efﬁciencies instead of speeds, which is required for energy minimality. Because
of this the bound on Algorithm 6 is not as small as FFD for VSBP. Once
sorted, a job is assigned to the most eﬃcient machine within the current
working set which can accommodate it within the time constraint. When
a job cannot be ﬁnished within the makespan limit by any machine in the
working set, the next machine is activated and included in the working set.
The time complexity of Algorithm 6 is O(mn).
Theorem 6.1. The worst case bound on the number of machines selected
by Algorithm 6 is 2.OP T
Proof. Proof is on the similar lines as with ﬁrst ﬁt decreasing algorithm[36].
But we get a higher bound because of not sorting machines based on their
speeds.
Let k be the number of machines chosen by the by the algorithm and
let k∗ be the optimal number of machines. We note that the jobs have been
sorted in non-increasing order. Let S be the number of most energy eﬃcient
machines which can complete all jobs such that all machines are active for
the complete makespan. So we have the trivial bound k∗ ≥ S. Let b ≤ k
be an arbitrary machine in the working set of algorithm 6. We will analyze

20

Algorithm 6: Approximation algorithm for reducing energy given
limit on makespan with indivisible job
input : Set of machines (C), number of machines (m), working
power of machines (µ(ci )), idle power of machines (γ(ci )),
sum of idle power of all the machines (Γ), speed of machines
(υ(ci )), makespan limit (T ), weight of jobs (ψ(pj ))
output: Working set (R), energy (E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

for i = 1 to m do
i)
calculate µ(ciυ(c
)−γ(ci )
ti ← 0
end
i)
max-sort ( µ(ciυ(c
)−γ(ci ) );

max-sort ψ(pj )
for j = 1 to n do
for i = 1 to m do
ψ(p )
if ( υ(cij) ≤ T − ti ) then
assign ψ(pj ) to ci
ti ← ti +

ψ(cj )
υ(ci )

R ← R ∪ ci
break;
end
end
end P
E ← iǫR [(µ(ci ) − γ(ci ))ti + ΓT ]
Return E
Return R

the following two cases: b is assigned a job which will take > T2 time on the
fastest machine of the system or it is not assigned a job of such size. If such
a job takes half the time of makespan on the fastest machine, then surely it
will take more time on other machines. Suppose b is assigned a job i which
will take T2 time on the fastest machine. Then the previously considered
jobs i′ < i all will take > T2 time in any machine and each machine b′ < b
must be assigned one of these jobs, so we have ≥ b jobs of size Tυmax
2 . No
two of these jobs can be assigned to the same machine in any assignment,
so optimal uses at least b machines, i.e., k∗ ≥ b.
21

Suppose b is not assigned a job of size > Tυmax
2 . Then no used machine
Tυmax
′′
b > b is assigned an item of size > 2 . But each of these machines must
be assigned atleast one job to be included in the working set. So the k − b
machines b, b + 1, . . . , k − 1 together are assigned ≥ (k − b) jobs. We know
that none of these jobs could have been assigned to any machine b′ < b. We
consider two sub-cases. If b ≤ (k − b), then we can imagine assigning to
every machine b′ < b one of these (k − b) jobs, which would give us b − 1
machines taking time more than the makespan constraint T . This implies
that S > b − 1. On the other hand, if b > (k − b), then we can imagine
assigning each of the (k − b) jobs to a diﬀerent machine b′ < b, giving us
(k − b) machines taking more than T time. Then S > (k − b). So for any b
we have in all cases that either k∗ ≥ b or k∗ ≥ (k − b). Now we choose b so
that it will maximize the minimum of b and (k − b) : Equating b = (k − b)
gives b = 12 k, and we take b = ⌈ 21 k⌉ to get an integer. Then we have that
k∗ ≥ ⌈ 12 k⌉ ≥ 12 k, or k∗ ≥ (k − ⌈ 12 k⌉) ≥ 21 k.Hence we have k ≤ 2k∗ .
Theorem 6.2. The worst case bound on energy E consumed by the working
set
 machines for non-divisible jobs with Algorithm 6 is given by
 of parallel
ηmax
i)
1 + ηmin EOP T where η(ci ) is µ(ciυ(c
)−γ(ci ) .

Proof. Energy consumed by the system of r parallel machines is given by
r
X
[(µ(ci ) − γ(ci ))]t(ci ) + ΓT
E=

(6.5)

i=1

which can be rewritten as
E=

r
X

[(µ(ci ) − γ(ci ))]

i=1

w(ci )
+ ΓT
υ(ci )

(6.6)

Let E represent energy consumed by Algorithm 6 and EOP T be the optimal
energy consumption of the system. Also, let ro denote the optimal number
of machines and r’ denote the number of machines selected by Algorithm 6.
We have seen that r ′ = 2ro in the worst case. Then
E
EOP T
E
EOP T

=

P ro

P2ro

i=1 [(µ(ci )

= Pr
o

i)
− γ(ci ))] w(c
υ(ci ) + ΓT

i=1 [(µ(ci ) −

w(ci )
i=1 [(µ(ci )−γ(ci ))] υ(ci ) +ΓT
Pro
wo (ci )
i=1 [(µ(ci )−γ(ci ))] υ(ci ) +ΓT

22

o (ci )
γ(ci ))] wυ(c
+ ΓT
i)

+

P2ro

w(ci )
i=ro +1 [(µ(ci )−γ(ci ))] υ(ci )
P ro
wo (ci )
i=1 [(µ(ci )−γ(ci ))] υ(ci ) +ΓT

(6.7)

(6.8)

The ﬁrst part of the equation covers the ﬁrst ro machines both in the
numerator and the denominator. So, the power and speed ratings are same.
Since wo (ci ) will be greater than w(ci ) in the numerator, as optimal algorithm will assign all the jobs within the ﬁrst ro machines, and the approximation algorithm will fail to assign all the jobs to those ro machines and
will need extra machines to schedule these jobs. Hence the ﬁrst part of the
equation can be upper bounded by 1.
P2ro
w(ci )
E
i=ro +1 [(µ(ci ) − γ(ci ))] υ(ci )
(6.9)
= 1 + Pr
o
EOP T
[(µ(ci ) − γ(ci ))] wo (ci ) + ΓT
i=1

υ(ci )

i)
Let η(ci ) denote µ(ciυ(c
)−γ(ci ) which is a measure of eﬃciency of the machine
ci , i.e., it is a measure of the amount of energy converted to useful work by
the machine. Then
P2ro
1
E
i=ro +1 ( η(ci ) )w(ci )
(6.10)
= 1 + Pr o
1
EOP T
i=1 ( η(ci ) )wo (ci ) + ΓT

Since ΓT is positive and to upper bound the ratio, we can ignore this term
in the denominator.
P2ro
1
E
i=ro +1 ( η(ci ) )w(ci )
(6.11)
≤ 1 + Pr o
1
EOP T
i=1 ( η(ci ) )wo (ci )

Because the machines are sorted, η is increasing from 1 to m.
P o
1
( ηmin
) 2r
E
i=ro +1 w(ci )
=1+
P
1
o
EOP T
( ηmax
wo (ci )
) ri=1

(6.12)

Now we are bothered about total size of work assigned to the i = (ro + 1) . . . 2ro
machines. If we divide the ratio by ro machines, we get the average size of
work assigned by the Algorithm 6 to i = (ro + 1) . . . 2ro machines and the
optimal average size.
E
EOP T

=1+

w(ci )
i=ro +1 ro
P o wo (ci )
1
) ri=1
( ηmax
ro

1
)
( ηmin

P2ro

(6.13)

Let us denote the average size ofPjobs assigned to each machine by any
w(ci )
o
optimal algorithm by X, i.e., X = ri=1
ro and average size of jobs assigned by Algorithm 6 to i = 1 . . . ro and i = (ro + 1) . . . 2ro machines as Y
and Z respectively.
ηmax Z
E
=1+
(6.14)
EOP T
ηmin X
23

If Z > X2 , then Y > X2 . Since we have extra ro machines, we can assign
Y to each machine in i = 1 . . . ro . But then the jobs will overﬂow the time
constraint. This means that optimally, ro machines will not be suﬃcient to
accommodate all the jobs which is a contradiction to our assumption that
ro is the optimal set of machines. Hence, Z ≤ X2 .
ηmax X2
EOP T
ηmin X

1 ηmax 
E = 1+( )
EOP T
2 ηmin
E

=1+

(6.15)
(6.16)

When all machines have same eﬀectiveness ratio, equation 6.16 reduces to
the bound of 32 for VSBP [36].

7

Conclusions

This paper provides a generic formulation of the problems of scheduling in
a system subject to pairs of constraint on various resources available to its
machines. While not going into the details of the speciﬁc machines and jobs
run by them, the model simply considers each machine to have a working
power and an idle power rating, which determines how much power the
machine draws, while working and while not. The behavior of the system
as a whole is governed by the power ratings of its machines, and the need
to run jobs eﬀectively.
A simple analysis shows that the problem of minimizing the makespan
on a power-constrained system is N P-hard even with divisible jobs. This in
turn implies that other interesting problems, and also scheduling problems
with non-divisible jobs, are N P-hard as well. We get similar results with
energy and makespan constraints with non-divisible jobs.
We can modify the system model a little to get other interesting problems. One such case could be a system model with multiple sources of
power, each of which has a diﬀerent capacity and cost. In such systems, it
is also of interest to minimize the overall cost incurred for running a set of
jobs. This is easily seen to be N P-hard because if an eﬃcient algorithm
for minimal-cost scheduling were to exist, then we could use the same for
energy-eﬃcient scheduling by considering only one source supplying power
at cost 1 per unit energy.
Given the previous results, it also follows that many complex objectives
that mix two or more simpler objectives are likewise intractable. The reason

24

this so is that it is certainly no easier to meet an objective when subjected
to a constraint, than it is to meet the objective without the constraint.
While this family of hardness results certainly puts paid to any hopes
of easy solutions to problems of scheduling for energy eﬃciency and other
desirable measures of eﬀectiveness, it opens up some interesting possibilities. One direction we think would be fruitful is to further analyze the
sub-classes of problems which may permit easy solutions; another would
be construct suitable approximation algorithms to achieve objectives within
known bounds of the optimal. We have pursued this particular avenue to
some extent, and suggest that there is much scope for further work along
the same lines.

References
[1] J. W. Herrmann (Ed.), Handbook of Production Scheduling, Vol. 89 of
(International Series in Operations Research & Management Science),
Springer, 2006.
[2] M. L. Pinedo, Scheduling: theory, algorithms, and systems, Springer,
2012.
[3] A. Y. Zomaya, Y. C. Lee (Eds.), Energy-Eﬃcient Distributed Computing Systems, Wiley-IEEE Computer Society, 2012.
[4] F. Yao, A. Demers, S. Shenker, A scheduling model for reduced cpu
energy, in: Proceedings of the 36th Annual Symposium on Foundations
of Computer Science (FOCS ’95), IEEE Computer Society, Washington,
DC, USA, 1995, pp. 374–382.
[5] R. Lent, Grid scheduling with makespan and energy-based
goals, Journal of Grid Computing 13 (4) (2015) 527–546.
doi:10.1007/s10723-015-9349-4.
[6] J. J. Durillo, V. Nae, R. Prodan, Multi-objective workﬂow scheduling: An analysis of the energy eﬃciency and makespan tradeoﬀ, in: 13th IEEE/ACM International Symposium on Cluster,
Cloud, and Grid Computing (CCGrid 2013), 2013, pp. 203–210.
doi:10.1109/CCGrid.2013.62.
[7] H. Sun, Y. He, W.-J. Hsu, R. Fan, Energy-eﬃcient multiprocessor
scheduling for ﬂow time and makespan, Theor. Comput. Sci. 550 (2014)
1–20. doi:10.1016/j.tcs.2014.07.007.
25

[8] J. J. Patt, W. F. Banholzer, Improving energy eﬃciency in the chemical
industry, The Bridge: Linking Engineering and Society 39 (2) (2009)
15–21.
[9] D. Sperling, N. Lutsey, Energy eﬃciency in passenger transportation,
The Bridge: Linking Engineering and Society 39 (2) (2009) 22–30.
[10] A. Bruzzone, D. Anghinolﬁ, M. Paolucci, F. Tonelli, Energy-aware
scheduling for improving manufacturing process sustainability: A mathematical model for ﬂexible ﬂow shops, CIRP Annals - Manufacturing
Technology 61 (1) (2012) 459–462.
[11] S. Mitra, L. Sun, I. E. Grossmann, Optimal scheduling of industrial
combined heat and power plants under time-sensitive electricity prices,
Energy 54 (2013) 194–211.
[12] J. L. Berral, I. Goiri, R. Nou, F. Juliá, J. Guitart, R. Gavaldá, J. Torres,
Towards energy-aware scheduling in data centers using machine learning, in: e-Energy ’10: Proceedings of the 1st International Conference
on Energy-Eﬃcient Computing and Networking, 2010, pp. 215–224.
doi:10.1145/1791314.1791349.
[13] T. Hirofuchi, H. Nakada, H. Ogawa, S. Itoh, S. Sekiguchi, Eliminating
datacenter idle power with dynamic and intelligent VM relocation, in:
Distributed Computing and Artiﬁcial Intelligence, Vol. 79 of Advances
in Intelligent and Soft Computing, Springer Berlin Heidelberg, 2010,
pp. 645–648.
[14] C. Artigues, P. Lopez, A. Hait, Scheduling under energy constraints,
in: International Conference on Industrial Engineering and Systems
Management (IESM 2009), 2009.
[15] S. Lee, G. Ryu, Y. Chon, R. Ha, H. Cha, Automatic
standby power management using usage proﬁling and prediction,
IEEE Trans. Human-Machine Systems 43 (6) (2013) 535–546.
doi:10.1109/THMS.2013.2285921.
[16] Lawrence Berkeley National Laboratory, Standby Power (2016).
URL http://standby.lbl.gov/
[17] M. Drozdowski, J. Marszalkowski, J. Marszalkowski, Energy trade-oﬀs
analysis using equal-energy maps, Future Generation Computer Systems 36 (2014) 311–321. doi:10.1016/j.future.2013.07.004.
26

[18] K. Lee, J. Y. Leung, Z.-h. Jia, W. Li, M. L. Pinedo, B. M. Lin, Fast approximation algorithms for bi-criteria scheduling with machine assignment costs, European Journal of Operational Research 238 (1) (2014)
54–64. doi:10.1016/j.ejor.2014.03.026.
[19] H. Shi, W. Wang, N. Kwok, Energy dependent divisible load theory for
wireless sensor network workload allocation, Mathematical Problems in
Engineeringdoi:10.1155/2012/235289.
[20] S. A. Mansouri, E. Aktas, U. Besikci, Green scheduling of a twomachine ﬂowshop: Trade-oﬀ between makespan and energy consumption, European Journal of Operational Research 248 (2016) 772–788.
doi:10.1016/j.ejor.2015.08.064.
[21] T. J. Brennan, Optimal energy eﬃciency policies and regulatory
demand-side management tests: How well do they match?, Energy Policy 38 (8) (2010) 3874–3885.
[22] K. Spees, L. B. Lave, Demand response and electricity market eﬃciency,
The Electricity Journal 20 (2007) 69–85.

[23] K. Jessoe, D. Rapson, Commercial and Industrial Demand Response Under Mandatory Time-of-U
Energy Institute at HAAS, 2013, Tech. Rep. WP-238.
URL https://ei.haas.berkeley.edu/research/papers/WP238.pdf
[24] P. Ranganathan, Recipe for eﬃciency:
Principles of poweraware computing, Commun. ACM 53 (4) (2010) 60–67.
doi:10.1145/1721654.1721673.
[25] A. Narayan, S. Rao, Power-aware cloud metering, IEEE Trans. Services
Comput. 7 (3) (2014) 440–451. doi:10.1109/TSC.2013.22.
[26] C. Lavania, S. Rao, E. Subrahmanian, Reducing variation in solar energy supply through frequency domain analysis, IEEE Systems Journal
6 (2) (2012) 196–204. doi:10.1109/JSYST.2011.2162796.
[27] W. Katzenstein, E. Fertig, J. Apt, The variability of interconnected wind plants, Energy Policy 38 (8) (2010) 4400–4410.
doi:10.1016/j.enpol.2010.03.069.
[28] T. A. Al Enawy, H. Aydin, Energy-constrained scheduling for weaklyhard real-time systems, in: Real-Time Systems Symposium, 2005.
RTSS 2005. 26th IEEE International, IEEE, 2005, pp. 10–pp.
27

[29] M. R. Garey, D. S. Johnson, Computers and Intractability; A Guide
to the Theory of NP-Completeness, W. H. Freeman & Co., New York,
NY, USA, 1990.
[30] S. Martelli, P. Toth, Knapsack Problems: Algorithms and Computer
Implementations, Wiley, 1990.
[31] P. Agrawal, S. Rao, Energy-aware scheduling of distributed systems, IEEE Trans. Autom. Sci. Eng. 11 (4) (2014) 1163–1175.
doi:10.1109/TASE.2014.2308955.
[32] B. Veeravalli, D. Ghose, T. G. Robertazzi, Divisible load theory: A new
paradigm for load scheduling in distributed systems, Cluster Computing
6 (1) (2003) 7–17. doi:10.1023/A:1020958815308.
[33] O. H. Ibarra, C. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM 22 (4) (1975) 463–468.
doi:10.1145/321906.321909.
[34] P. Agrawal, S. Rao, Energy-minimal scheduling of divisible loads, in:
4th International Workshop on Energy-Eﬃcient Data Centres (E2DC
2015), co-located with ACM e-Energy 2015, Bangalore, India, 2015.
doi:10.1145/2768510.2768528.
[35] G. Dobson, Scheduling independent tasks on uniform processors, SIAM
J. Comput. 13 (4) (1984) 705–716. doi:10.1137/0213044.
[36] D. K. Friesen, M. A. Langston, Variable sized bin packing, SIAM J.
Comput. 15 (1) (1986) 222–230. doi:10.1137/0215016.

28

