arXiv:1609.06430v1 [cs.DC] 21 Sep 2016

Energy-Efficient Scheduling:
Classification, Bounds, and Algorithms∗
Pragati Agrawal
pragati.a.in@ieee.org

Shrisha Rao
shrao@ieee.org

Abstract
The problem of attaining energy eﬃciency in distributed systems is of importance,
but a general, non-domain-speciﬁc theory of energy-minimal scheduling is far from
developed. In this paper, we classify the problems of energy-minimal scheduling and
present theoretical foundations of the same. We derive results concerning energyminimal scheduling of independent jobs in a distributed system with functionally similar machines with diﬀerent working and idle power ratings. The machines considered in
our system can have identical as well as diﬀerent speeds. If the jobs can be divided into
arbitrary parts, we show that the minimum-energy schedule can be generated in linear
time and give exact scheduling algorithms. For the cases where jobs are non-divisible,
we prove that the scheduling problems are NP-hard and also give approximation algorithms for the same along with their bounds.
Keywords: scheduling, energy eﬃciency, distributed systems, computational complexity

1

Introduction

Energy is a precious resource of the current industrial economy. For energy conservation
and sustainability, it is necessary to achieve energy eﬃciency, which we may take to mean
minimization of the energy consumed to do a given amount of work. This requires ways to
achieve greater energy eﬃciencies by proper scheduling of jobs over machines, in addition to
making each machine individually more energy eﬃcient. Scheduling theory is an important
ﬁeld of study that has received attention from researchers for decades, but most work on
scheduling till now has only looked at makespan and other time-related objectives. Energy
being such a limited resource and directly related to cost, it can in certain instances be
considered more important than time, i.e., it may be better to complete jobs using minimum
energy, rather than completing them quickly. Clearly, scheduling jobs in such a way that
∗

A part of this work is presented in a workshop paper (Agrawal and Rao, 2015) at the 4th International
Workshop on Energy-Efficient Data Centres (E2DC 2015), co-located with ACM E-Energy 2015, Bangalore,
India.

1

the total energy consumption of the system is minimal, or at least low, is of the essence.
We present a generalized theory for energy-eﬃcient oﬄine scheduling in this paper, which
does not go into domain-speciﬁc issues or technologies.
Our work is applicable to systems whose machines are similar in their capabilities but
can have diﬀerent working and idle power consumptions. The speeds at which machines
can execute tasks can be diﬀerent from one another, but are not time-varying, i.e., each
machine operates at the same speed whenever working. All machines are connected to
one another, so that a job from one machine can be transferred to any other machine.
There is no set limit to the number of machines in a system. Machines and jobs to be
executed are independent, and hence any job can be executed in any order on any machine.
Each machine is characterized by a ﬁxed working power (the power consumed by it when
under load) and a ﬁxed idle power (the power consumed by it when running idle), as seen
in previous work (Agrawal and Rao, 2014). Given a set of interconnected machines and
independent jobs, our results specify the allocation of jobs on the machines so that the
total power consumption of the system is minimized. However, unlike that previous work,
we focus on exact results rather than using heuristics for scheduling.
Considering a system of machines cooperatively running similar loads, we classify the
problems of energy-minimal oﬄine scheduling with non-identical interconnected machines
and independent jobs as follows:
1. Identical speeds, divisible loads:
This class of problem is discussed in Section 5.1.1, where we derive results to prove
that energy-minimal scheduling under this type of system can be solved in linear
time; we also give an algorithm for the same.
2. Identical speeds, non-divisible loads:
This turns out to be NP-hard, as shown in Section 5.1.2. We also give a linear-time
approximation algorithm which gives a solution within a bound of 34 .
3. Different speeds, divisible loads:
In Section 5.2.1 we give results for energy-minimal scheduling on such a system and
also a linear-time algorithm to ﬁnd the minimum-energy schedule.
4. Different speeds, non-divisible loads:
As with the case of identical speed machines, this class of problems is also NP-hard.
We give a linear-time approximation algorithm for this class in Section 5.2.2 which
gives a result within the bound of 19
12 times the optimal.
We ﬁrst introduce a generic system model which abstracts the relevant aspects of
energy-eﬃcient scheduling. We then give a classiﬁcation of the problems of energy-eﬃcient
scheduling on diﬀerent types of systems, and study their complexities. This makes possible
analyses giving results which govern the relative distribution of work among machines for
2

maximum energy eﬃciency, given the energy speciﬁcations of the machines. Using these
results we design scheduling algorithms for diﬀerent classes of systems. For problem classes
in which scheduling is NP-hard, we give approximation algorithms along with their bounds.
We deliberately do not give speciﬁc units for energy (which is typically measured in
joules, ergs, kilowatt-hours, etc.), power (often measured in watts, etc.), work (generally
speciﬁed in the same units as energy), or speed (work done per unit time); we likewise do
not ﬁnd it necessary to be precise about types of energy or energy sources. This is so to
remain agnostic towards particular system technologies and instantiations, and to avoid
domain-speciﬁc biases in our analyses.
There is a lot of work done for makespan scheduling, and other time-related objectives. But solving for time-related objectives does not guarantee minimum energy. The
novelty of this work is in considering energy speciﬁcally with completely generic machine
speciﬁcations. No other theoretical work until now has considered energy consumption
of machines while idle, which is known to be signiﬁcant from real life; e.g., in data centers (Hirofuchi et al., 2010; Berral et al., 2010). Our system model also shows the absolute
bounds of energy-minimal scheduling for speciﬁc types of systems. We derive results (for
divisible jobs) which serve as an upper-bound to maximum achievable eﬃciency—because
a system with divisible jobs can always have higher eﬃciency as compared to system with
non-divisible jobs (Pinedo, 2012).
A part of this theoretical framework, seen here in Section 4.1, has been presented in
our workshop paper (Agrawal and Rao, 2015), which introduces the classiﬁcation of energyminimal scheduling problems and gives results on the class of systems which have identical
speed machines and divisible loads. It also gives results for a special case of system with
diﬀerent speed machines and divisible loads in which idle power consumption of machines
was considered to be zero. It can be seen as the beginning of the work presented in
the current paper which comprehensively covers most types of energy-minimal scheduling
problems with completely interconnected machines and independent jobs.
In the present paper we deal with theoretical aspects of energy-minimal scheduling,
deriving results which can guide the design of scheduling algorithms for systems. On any
given schedule, if the conditions indicated in the results are satisﬁed, then that schedule
will be energy-minimal. Likewise, the results can also indicate when a system of machines
would be inherently wasteful of energy, and can thus guide more energy-eﬃcient system
designs.
It is easy to see (even a back-of-the-envelope calculation can suﬃce) that there are
many cases where it is not appropriate to run all machines, if one’s goal is to complete a
set of jobs with minimal energy consumption. The question that arises is: given a set of
jobs to complete, which machines should one use, and which not? Our results and analyses
address this point.
Machines not in use are not assumed to be switched oﬀ, but do consume power (what
we call idle power). We have deliberately allowed that machines do not get switched oﬀ
when not in use, given the reality of machines in many domains (after all, the on-oﬀ cycle
3

time for an industrial furnace, or even a personal computer, is not small). The situation
where a machine does get switched oﬀ is merely a special case where the idle power of that
machine is zero.
For the class of system in which machines have identical speeds with diﬀerent power
ratings, and when the jobs are divisible, we ﬁrst determine the precedence of the machines
(the order in which they should be assigned work). We then derive the optimal number of
machines which should be working so that the energy consumption is minimum. Based on
this we derive what should be the optimal allocation of work among the machines chosen to
run. We give an O(m) (where, m is the number of machines) algorithm which instantiates
the theoretical results, to derive the energy-minimal schedule given the speciﬁcations of
the machines and jobs.
The slightly harder problem of ﬁnding the minimum-energy schedule for divisible jobs
over machines with diﬀerent speeds and power ratings can also be solved in O(m) time.
We give an exact algorithm for this class too.
For the classes of problems with non-divisible jobs, we see that the problems are NPhard. Hence we give O(m) approximation algorithms for both cases: systems with identicaland diﬀerent-speed machines.
The remainder of the paper is organized as follows. Related work is mentioned in
Section 2. The system model along with the notation used in deﬁning the energy-minimal
scheduling problem and the motivation is presented in Section 3. Section 4 discusses about
the precedence of machines for both identical speed and diﬀerent speed machine case. The
proposed algorithms along with their bounds are given in Section 5. Finally, Section 6
describes the two types of measures commonly used for energy eﬃciency in systems, and
shows that these are incompatible.

2

Related Work

In energy-minimal scheduling, as opposed to classical makespan scheduling, there are additional parameters (energy speciﬁcations) which come into picture and hence it is inherently
more complex than makespan scheduling. Agrawal and Rao (2014) show that energyeﬃcient scheduling is strictly harder than makespan scheduling, and present a generic
model for scheduling which takes into consideration both the working power and the idle
power of each machine. They propose three heuristic algorithms for energy-aware scheduling in a system where jobs have precedence constraints.
Though there have been a lot of work done in the ﬁeld of scheduling, the prime focus
of general works on scheduling (Pinedo, 2012, 2009; Herrmann, 2006) has been to optimize
on objectives related to time—such as makespan, earliness, and avoidance of tardiness.
Existing literature dealing with scheduling for energy reduction generally focuses on speciﬁc domains, such as communication networks, embedded systems, and high-performance
computing. These works invariably rely on speciﬁc features and technologies of those

4

domains. For instance, Wang and Saksena (1999) address parallel task scheduling for reducing energy consumption for high-end computing using the DVFS (dynamic voltage and
frequency scheduling) technique with some heuristics. More recently, Yassa et al. (2013)
also base their approach on DVFS to minimize energy consumption (as do many others). Huang et al. (2011) propose energy-aware task allocation using simulated annealing
with timing adjustment for network-on-chip based heterogeneous multiprocessor systems.
Sheikh et al. (2012) survey existing scheduling algorithms and software for reducing energy
dissipation in performing tasks on diﬀerent platforms including single processors, multicore
processors, and distributed systems. This survey is quite comprehensive and discusses the
architectural, software, and algorithmic issues for energy-aware scheduling of computing
devices. Pouwelse et al. (2001) give a heuristic for energy priority scheduling for variable voltage processors. Bambagini et al. (2013) use the combination of oﬄine-DVFS and
online-DPM (dynamic power management) techniques to reduce energy consumption in
embedded systems. Some recent anthologies (Zomaya and Lee, 2012; Pierson, 2015) deal
with energy eﬃciency in computing systems at various scales (processors to data centers).
However, while they are rich in pragmatic approaches and domain-speciﬁc ideas for energy
eﬃciency, they do not present a theory of energy-eﬃcient scheduling per se, and only basic
algorithms (e.g., Greedy-Min, Greedy-Max) are considered on occasion. It is patently obvious that even though there are works on application-speciﬁc energy-eﬃcient scheduling,
a generalized theory is yet far from developed.
In the domain of microprocessor power management and energy saving, much of the
prior work uses speed scaling and power-down techniques (Irani and Pruhs, 2005; Albers,
2009). Augustine et al. (2004) suggests optimal power-down strategies with more than one
low-power state. When a device is idle, their algorithm turns the device in low-power sleep
state. Bansal et al. (2009, 2013) use the other technique called speed scaling. Bansal et al.
(2007) have given a tighter bound for the YDS algorithm given by Yao et al. (1995) and
proved that their BKP algorithm is cooling-oblivious. Bansal et al. (2009, 2013) consider
an arbitrary power function of speed, for speed scaling.
There are some studies of scheduling whose theoretical developments can help in energyeﬃcient scheduling too. One such is divisible load theory, which studies methodologies
involving the continuous and linear modeling of partition-able communication and computation loads for parallel processing (Veeravalli et al., 2003; Yu and Robertazzi, 2003;
Singh and Sahu, 2014; Abdullah and Othman, 2013; Robertazzi et al., 2005). Another
such ﬁeld is multi-objective scheduling, in which machine cost is considered as one of
the objectives. (In general, machine cost includes any cost which incurs because of usage
of the machines of the system.)
There is some prior work concerning scheduling for multiple criteria. For instance,
Leung et al. (2012) consider two objectives for scheduling: one is time-related such as
makespan (as the customer’s objective), and the other is total machine cost (as the service
provider’s objective). They form diﬀerent ﬁnal objectives by combining these two objectives in various ways and analyze the complexity of the scheduling problem for each of these
5

various combinations. Lee et al. (2014) propose a heuristic for bi-criteria scheduling with
machine assignment costs with worst-case performance bounds. Lee et al. (2012) also work
on multi-objective scheduling. Other than makespan, they also minimize the total congestion and completion time, the maximum and total tardiness, and the number of tardy
jobs. They give a coordination mechanisms for parallel machine scheduling. Shi et al.
(2012) formulate an assignment scheme for the divisible load theory for sensing workload
allocations. Drozdowski et al. (2014) give a method of visualizing the relationships between computation and energy consumption (in supercomputing and HPC applications)
as two-dimensional maps similar to isotherms.
Though the objectives considered in these and other such works can be seen as marginally
relevant to minimizing energy (setting energy consumed by a running machine as a machine
cost), they have not considered the idle power consumptions of machines, which is needed
for realistic analyses. In many papers that consider multiple scheduling objectives, all objectives are concerned with time only, and do not make sense for energy-minimal scheduling.
The theoretical framework and classiﬁcation of energy-minimal scheduling problems is not
discussed in or derivable from any of these papers.
Clearly then, there is a need of a theoretical framework, as presented here, which realistically models systems of machines considering both idle power and running power, and also
allows us to classify the various types of problems involved in energy-minimal scheduling
and understand their complexities. This theory can of course also be extended for further
ﬁne-grained analyses (e.g., for machines with multiple performance levels). The theoretical
framework proposed is thus a necessary addition to existing and ongoing work focusing
on heuristic approaches to energy-eﬃcient scheduling, and also complements technologyspeciﬁc approaches to energy reduction such as DVFS (Le Sueur and Heiser, 2010).

3

System Model

In this section we formally introduce our system model and deﬁne the energy-minimal
scheduling problem in the most general sense. As any other scheduling problem, we have a
set of interconnected machines and a set of jobs that are to be executed using the machines.
We presume that all machines are connected in such a way that a job can be transfered from
any machine to any other machine without any energy dissipation. Jobs are independent
and hence can be executed in any order and on any machine.
We consider two types of jobs, divisible and non-divisible. There can be two types
of systems as well, based on the speeds of the machines in the system: one in which all
machines run at the same speed (even though their power ratings may be diﬀerent), and
the other class in which machines run at diﬀerent speeds. Thus, based on the type of job
and the type of system, we have four classes of scheduling problems.
Let the set of m machines in a system be denoted by C, where C = {ci : 1 ≤ i ≤ m} and
ci denotes the machine i of the set C. We discuss the precedence of machines later in this

6

paper. R denotes the working set of machines. The working power of machine ci is denoted
as µ(c
i ), and the idle power as γ(ci ). The sum of the idle power of all the machines is given
Pm
by i=1 γ(ci ) = Γ. 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.
All machines in a system work in parallel, and the maximum working time of a system
to execute a given set P of n jobs p1 to pn is T , which is the makespan of the system for
that set of jobs. If machine ci works only for time τ (ci ), then the idle time of that machine
ci is given by T − τ (ci ) = κ(ci ). The amount of work done by machine ci is represented by
w(ci ), where
w(ci ) = τ (ci )υ(ci )
(3.1)
The weight (processing
Pn time) of job pj is denoted by ψ(pj ) and the sum of the weights
of all jobs is given by j=1 ψ(pj ) = W P
. Also, the sum of work done by all machines is
equal to the total work to be done, i.e., m
i=1 w(ci ) = W .
When υ(ci ) = 1, ∀i, 1 ≤ i ≤ m, then we say that the machines are identical in their
working capacities or speed, implying that they can execute and complete any job given to
them in equal time. Also, in this case τ (ci ) = w(ci ), ∀i, 1 ≤ i ≤ m. And if in the present
case all jobs are executed sequentially on one machine, then that time taken is equal to W ,
the total amount of work to be done.
The energy consumed by a machine can be calculated given the power consumption by
the machine in working state and the duration for which the machine works. Since the
power rating of a machine is energy consumed per unit time, it is in principle possible to
calculate the energy consumed by any machine over a given time duration by integrating
the power consumption over time (Halliday et al., 2010). If the power consumed is constant
over time, the energy is given by the product of power with time.
In many systems like data centers, it is not a simple matter to shut oﬀ machines, even
when they are not given any load. Thus, if no machine is not switched oﬀ until the total
work is over, even such an idle machine consumes some power though not producing any
work. Considering the energy consumption in idle state too, the total energy consumed by
a machine 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 )τ (ci ), and
the energy consumed in the idle state by γ(ci )(κ(ci )). So the total energy consumption by
a machine ci is given by µ(ci )τ (ci ) + γ(ci )(κ(ci )). With this, the expression for the energy
consumed in a system can be given as the sum of the energies consumed by all m machines:
m
X
[µ(ci )τ (ci ) + γ(ci )(κ(ci ))]
E=
i=1

7

(3.2)

Symbol

Meaning
Total energy consumption of system with m machines
and jobs distributed to r machines
Makespan of the system
Set of machines c1 , c2 , . . . , cm
Working set of machines
Number of machines on which jobs are distributed
Power consumption in working state by machine ci
Power consumption in idle state by machine ci
Speed of machine ci
Time spent in working state by machine ci
Time spent in idle state by machine ci
Amount of work given to machine ci
Set of jobs p1 , p2 , . . . , pn
Weight of job pj
Total working time of all the jobs

Em,r
T
C
R
r
µ(ci )
γ(ci )
υ(ci )
τ (ci )
κ(ci )
w(ci )
P
ψ(pj )
W

Table 1: Notation
Putting the value of κ(ci ) = T − τ (ci ), in (3.2),
E=

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

(3.3)

i=1

The general energy equation can be formed by replacing τ (ci ) with
in (3.3).

m 
X
w(ci )
w(ci )
+ γ(ci )(T −
)
E=
µ(ci )
υ(ci )
υ(ci )

w(ci )
υ(ci )

(from (3.1))

i=1

After simpliﬁcation,

E=

m 
X
w(ci )
i=1

υ(ci )

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



(3.4)

where 1 ≤ i ≤ m.
The notation used is indicated in Table 1. (Though some terms are deﬁned later in the
paper, we list them here for quick reference.)
We assume the following in our system:
1. All jobs are independent, i.e., there are no precedence constraints between jobs. It
means a job need not wait for completion of any to start its execution. Hence, there

8

is no idle time (gap) for a machine in between the execution of two jobs. This implies
that
T = max τ (ci ), ∀i
(3.5)
2. In the class where jobs are divisible, the divisibility of jobs means, jobs can be arbitrarily divided and assigned to any machine.
3. All machines stay on for the duration of the makespan of the whole set of jobs; no
machine is switched oﬀ while others continue to run. At any instant while the jobs are
being executed, each machine ci either consumes its working power µ(ci ) if working,
or its idle power γ(ci ) if not. (The situation where a machine gets switched oﬀ to
consume zero power while not executing a job, can of course be trivially handled by
setting γ(ci ) to 0.)
4. For the model in which the speed of all machines is the same, all machines are
indexed in increasing order of the diﬀerences of their working power and idle power,
i.e., µ(ci ) − γ(ci ) ≤ µ(cj ) − γ(cj ), ∀i, j where 1 ≤ i ≤ j ≤ m. For the model where
machines can have diﬀerent speeds, the machines are indexed in an order such that
i )+Γ
and afterwards machines are
the ﬁrst machine is the one with smallest µ(ci )−γ(c
υ(ci )
indexed in non-decreasing order of

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

where 1 ≤ i ≤ m.

5. For the model in which the speed of all machines is the same, one unit of work takes
one unit of time for execution, irrespective of the machine on which it is executed.
The problem of energy-minimal scheduling refers to ﬁnding schedules for a set of jobs
which would require minimum total energy when executed on a given system:
1. Identical speed machines:
The machines in the system have diﬀerent working and idle power consumptions, but
have equal speeds in execution of jobs. The aim for this type of system is to minimize
E given by (3.3).
2. Different speed machines:
Machines can have diﬀerent power consumptions as well as diﬀerent speeds. The aim
for this type of system is to minimize E given by (3.4).
For each of these classes we have two sub-classes, with divisible jobs and non-divisible
jobs.
In any of these classes, the aim is to schedule a set of jobs on the given set of machines
such that the energy consumption of the system E given by (3.3) and (3.4) is minimized.
The minimum makespan scheduling does not guarantee minimal energy schedules, and
that in fact makespan scheduling is a special case of energy-minimal scheduling, where the

9

working power of machines is equal to their idle power. Putting µ(ci ) = γ(ci ) in (3.3), we
get,

E =
=

m
X

i=1
m
X

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

i=1

This means that energy is directly proportional to makespan, and hence energy can be
minimized by minimizing makespan if the working power is equal to idle power.
Consider an arguably more practical setting where idle power is less than the working
power, γ(ci ) = zi · µ(ci ), where 0 ≤ zi ≤ 1:
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 )]

i=1

Then, the equation of energy can be written as:
E=

m
X

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

(3.6)

i=1

Hence, from (3.6) we can see that energy cannot be minimized by just minimizing
makespan, though the energy consumption of an individual machine does depend upon
its working time. Hence energy minimization is a more generic problem than makespan
minimization.
In this section we have introduced the system model and the assumptions of the scheduling problem we have considered. We have also indicated the objective function which we
will be looking to minimize. We now proceed to solve scheduling problems in the following
section.

4

Precedence of Machines

In this section we ﬁrst ﬁnd the precedence of machines, i.e., the order in which they should
be assigned work. This precedence helps in determining which machines should be alloted
work and how much, to reduce the overall energy consumption of the system.
10

With diﬀering power speciﬁcations of machines, it stands to reason that it may be
advantageous to prefer some machines over others in doing jobs. We investigate the properties of the system to determine the precedence of machines so that the energy consumed
in their execution is minimized. The problem of ﬁnding relative distribution of work among
machines can be broken into two parts:
• Given the set of m machines, which subset of machines should be allowed to work
and which should remain idle for all times during the makespan?
• What should be the distribution of work among the working machines?
There are no restrictions on the jobs except that the total load is considered to be W .
This means that the results derived in this section are applicable to all type of systems.
We ﬁrst derive results for the case where machines have identical speeds and then for the
case where they can have diﬀerent speeds.

4.1

Systems with Identical Speed Machines

In this subsection we consider the relative work distribution among machines with identical
speeds such that energy consumption is minimized.
As indicated previously, we assume that all machines are indexed in the non-decreasing
order of the diﬀerences between their working and idle power. We claim that when the
machines are indexed in such an order, then the loading of machines should be such that
the working times of these machines are in non-increasing order.
Lemma 4.1. Given µ(ck ) − γ(ck ) ≤ µ(cl ) − γ(cl ), then for energy optimality of the system,
τ (ck ) ≥ τ (cl ) ∀k, l, where 1 ≤ k ≤ l ≤ m.
Proof. We prove this by contradiction. Given µ(ck ) − γ(ck ) ≤ µ(cl ) − γ(cl ), then let us say
that for minimal energy consumption, τ (ck ) < τ (cl ).
With a little rearrangement of (3.3) we get,
E=

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

This in turn gives:
E=

+
+

k−1
X
[(µ(ci ) − γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(ck ) − γ(ck ))τ (ci ) + γ(ck )T ]
i=1
l−1
X

[(µ(ci ) − γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(cl ) − γ(cl ))τ (ci ) + γ(cl )T ]

i=k+1
m
X

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

i=l+1

11

(4.1)

The two possible cases can be: when τ (ck ) ≥ τ (cl ), and when τ (ck ) < τ (cl ). We derive
the energy equations for both cases and then compare them. By comparing the energy
equations in both, we arrive at a condition under which the energy consumed in one case
is less, and ﬁnd a contradiction.
Case 1: τ (ck ) ≥ τ (cl ). Take τ (ck ) = t + ǫ1 and τ (cl ) = t − ǫ1 , where ǫ1 ≥ 0.
Putting these values in (4.1) we get,
E=

k−1
X
[(µ(ci ) − γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(ck ) − γ(ck ))(t + ǫ1 )
i=1

l−1
X

+γ(ck )T ] +

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

i=k+1

m
X

[(µ(ci )

(4.2)

i=l+1

−γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(cl ) − γ(cl ))(t − ǫ1 ) + γ(cl )T ]
Case 2: τ (ck ) < τ (cl ). Take τ (ck ) = t − ǫ2 and τ (cl ) = t + ǫ2 , where ǫ2 > 0.
Putting these values in (4.1) we get,
E′ =

k−1
X
[(µ(ci ) − γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(ck ) − γ(ck ))(t − ǫ2 )
i=1

+γ(ck )T ] +

l−1
X

[(µ(ci ) − γ(ci ))τ (ci ) + γ(ci )T ] + [(µ(cl )

(4.3)

i=k+1

−γ(cl ))(t + ǫ2 ) + γ(cl )T ] +

m
X

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

i=l+1

Subtracting (4.3) from (4.2) to compare energies in both the cases, we get,
E − E ′ =[(µ(ck ) − γ(ck ))(t + ǫ1 ) + γ(ck )T ]
− [(µ(ck ) − γ(ck ))(t − ǫ2 ) + γ(ck )T ]
+ [(µ(cl ) − γ(cl ))(t − ǫ1 ) + γ(cl )T ]
− [(µ(cl ) − γ(cl ))(t + ǫ2 ) + γ(cl )T ]
Simplifying (4.4), we get,
E − E ′ = (ǫ1 + ǫ2 )[(µ(ck ) − γ(ck )) − (µ(cl ) − γ(cl ))]
If we say that in Case 2 the energy consumed is less, this means
E − E′ > 0
(ǫ1 + ǫ2 )[(µ(ck ) − γ(ck )) − (µ(cl ) − γ(cl ))] > 0

12

(4.4)

(µ(ck ) − γ(ck )) > (µ(cl ) − γ(cl ))

(4.5)

(4.5) is in contradiction to our assumption. QED.
We show which machines should be given comparatively more work then others. There
is a special case in which the idle power of a machine is proportional to its working power.
The following corollary covers machine precedence in such a case.
Corollary 4.2. When the ratio between the working power consumption (µ(ci )) and idle
power consumption (γ(ci )) of the machine is some constant z, ∀i, 1 ≤ i ≤ m, then µ(ci ) −
γ(ci ) is proportional to µ(ci ), so we need to index the machines in the order of µ(ci ).
For energy optimality it may well be suitable to give work to only some of the machines while letting others run completely idle. We now state the condition showing which
machines should be used when using only a subset of all the machines is beneﬁcial.
Lemma 4.3. If we give work to only some r machines, where 1 ≤ r ≤ m, then, for reduced
energy consumption, these are the r machines that form the set {c1 , c2 , . . . , cr } given our
index order.
Proof. For the r machines working, τ (ci ) > 0, and for the other m − r machines τ (ci ) = 0.
If τ (cr+1 ) > 0 then there must be any τ (ci ) from the set {τ (c1 ), τ (c2 ), . . . , τ (cr )} which is
equal to 0. But by Lemma 4.1, τ (c1 ) ≥ τ (c2 ) ≥ τ (c3 ) ≥ . . . ≥ τ (cr ) > 0 since τ (cr+1 ) > 0.
These two statements are contradictory and so it is not possible that τ (cr+1 ) > 0. Hence
it stands proved that for energy optimality, if we give work to only some r machines where
1 ≤ r ≤ m, then these r machines are of the set {c1 , c2 , . . . , cr }.
Using Lemma 4.3, given some number of machines to be used, we can ﬁnd which
machines should be assigned jobs. We now state and prove the condition which decides
how many machines should be used so that energy consumption of the system is minimal.
Let the energy consumption of a system of m machines, when jobs are distributed to r
machines, be given by Em,r . If we add one more machine to the working set of machines,
then we take some amount of work from previously working machine(s) and give that
amount of work to the new machine. s(ci ) represents the amount of work taken away from
machine ci and given to other machine(s).
Theorem 4.4. When r − 1 machines are working, for machine cr to be given work (i.e.,
τ (cr ) 6= 0) and result in reduced energy consumption, the following must hold.
m
r−1
X
X
γ(ci ) > 0
[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))s(ci )] + s(c1 )
i=1

i=1

13

(4.6)

Proof. We prove this by construction. If only r of the m machines are used and the rest
remain idle all the time, (3.3) can be re-written as follows, where the energy is expressed
by Em,r :
Em,r =

r−1
X
[µ(ci )τ (ci ) + γ(ci )(T − τ (ci ))]
i=1

m
X

+ µ(cr )τ (cr ) + γ(cr )(T − τ (cr )) +

γ(ci )T

i=r+1

Putting T = τ (c1 ), [by (3.5), Lemma 4.1 and Lemma 4.3]
Em,r =

r−1
X
[µ(ci )τ (ci ) + γ(ci )(τ (c1 ) − τ (ci ))]
i=1

+ µ(cr )τ (cr ) + γ(cr )(τ (c1 ) − τ (cr )) +

m
X

(4.7)
γ(ci )τ (c1 )

i=r+1

Re-arranging (4.7),
Em,r

m
r−1
X
X
γ(ci )
(µ(ci ) − γ(ci ))τ (ci ) + (µ(cr ) − γ(cr ))τ (cr ) + τ (c1 )
=

(4.8)

i=1

i=1

Also, we know that,
W =

r
X

τ (ci )

(4.9)

i=1

Taking out the term r from (4.9),
W =

r−1
X

τ (ci ) + τ (cr )

i=1

τ (cr ) = W −

r−1
X

τ (ci )

(4.10)

i=1

Putting the value of τ (cr ) from (4.10) in (4.8), we get,
Em,r =

r−1
X
(µ(ci ) − γ(ci ))τ (ci ) + (µ(cr )
i=1

− γ(cr ))(W −

r−1
X
i=1

14

τ (ci )) + τ (c1 )

m
X
i=1

(4.11)
γ(ci )

Re-arranging (4.11),
Em,r

r−1
X
[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))τ (ci )]
=
i=1

+ (µ(cr ) − γ(cr ))W + τ (c1 )

m
X

(4.12)

γ(ci )

i=1

This is a general equation for the energy of a system with m machines, where jobs are
given to r machines, where 1 ≤ r ≤ m and W is the total working time to complete all
jobs.
If we give jobs to r − 1 machines in a m machine system, its energy can be derived by
putting r = r − 1 in (4.12). Also the τ (ci )s are changed to τ (ci )′ s as in the following:
Em,r−1 =

r−2
X
[µ(ci ) − γ(ci ) − µ(cr−1 ) + γ(cr−1 )]τ (ci )′
i=1

′

+ (µ(cr−1 ) − γ(cr−1 ))W + τ (c1 )

m
X

(4.13)

γ(ci )

i=1

It is better that we give work to more machines only when the energy consumption by
doing so is lowered. Hence, if Em,r−1 > Em,r , then only we should give work to r machines,
else we give to r − 1 machines only. Thus the condition for using r machines can be written
as:
Em,r−1 − Em,r > 0
(4.14)
Using (4.12) and (4.13),
Em,r−1 − Em,r =

r−1
X

[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))(τ (ci )′ − τ (ci ))]

i=1

′

+ (τ (c1 ) − τ (c1 ))

m
X

(4.15)
γ(ci )

i=1

Taking τ (ci )′ − τ (ci ) = s(ci ), we get,
Em,r−1 − Em,r =

r−1
X

[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))s(ci )] + s(c1 )

m
X

γ(ci )

i=1

i=1

Here, s(ci ) informally signiﬁes the amount of work taken away from machine ci , to facilitate
giving work to the machine cr .

15

To give the jobs to r machines Em,r−1 − Em,r > 0.
m
r−1
X
X
γ(ci ) > 0
[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))s(ci )] + s(c1 )
i=1

i=1

QED.
Having derived the condition describing which machines to use for doing jobs, we now
ﬁnd out the amount of work to be given to each of these machines.
Theorem 4.5. If we give jobs to r > 1 machines, then for minimum energy consumption,
the distribution of jobs on all r machines should be equal and given by W
r .
Proof. We prove this by contradiction. Consider two cases, one in which the distribution
of work among the machines, which qualify to work according to Theorem 4.4 is equal, and
the other in which the work distribution is unequal. We claim, to show the contradiction,
that in the case in which the distribution is equal, the energy consumption is greater as
compared to the other, and that such is hence a non-optimal distribution.
Case 1: Equal distribution, τ (ci ) = Wr , ∀i, 1 ≤ i ≤ r, i.e., τ (c1 ) = τ (c2 ) = τ (c3 ) = . . . =
τ (cr ) = Wr .
W
Case 2: Unequal distribution, τ (c1 ) = W
r + ǫ, τ (c2 ) = τ (c3 ) = . . . = τ (cr−1 ) = r and
W
τ (cr ) = r − ǫ.
Here we assign more work to machine 1 compared to that required by equal distribution
of work among r machines (by Lemma 4.1, a bias has to favor smaller-numbered machines,
and therefore machine 1 most of all). The amount of extra work given to machine 1 is
ǫ and this amount of work is withdrawn from machine cr . We chose only to alter the
work distributions of machines 1 and r to keep the proof simple. We could have chosen
any machine ck for doing extra work and any machine cl for doing lesser work, where
k > l. But for allotting extra work ǫ to machine ck , we have to increase the amount of
work assigned to all machines in the set {c1 , c2 , . . . , ck } by at least ǫ, so that Lemma 4.1 is
satisﬁed.
Similarly for reducing the work of machine cl by ǫ, we have to reduce the amount of
work assigned to all machines in the set {cl+1 , cl+2 , . . . , cr } by at least ǫ so that Lemma 4.1
is satisﬁed. Hence if we want to alter the amount of work of just two machines (to keep
the proof simple) from an equal distribution, then we have alter it for machine c1 and cr .
It may be noted that our proof is generalizable for imbalances involving any numbers of
machines.
′
′′ . Then
Let the energy in Case 1 be denoted by Em,r
and the energy in Case 2 be Em,r
according to our proposition:
′′
′
Em,r
< Em,r
′′
′
Em,r
− Em,r
<0

16

(4.16)

Rewriting (4.12) after expanding, we get
Em,r =(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr ))τ (c1 )
+

r−1
X
[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))τ (ci )]
i=2

+ (µ(cr ) − γ(cr ))W + τ (c1 )

m
X

(4.17)

γ(ci )

i=1

′ ,
Putting the respective values of τ (ci )’s in (4.17) to derive Em,r
 
W
′
Em,r =(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr ))
r

 
r−1
X
W
+
(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))
r
i=2
 X
m
W
+ (µ(cr ) − γ(cr ))W +
γ(ci )
r

(4.18)

i=1

Similarly, we may derive
′′
Em,r

′′
Em,r

as:


W
+ǫ
=(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr ))
r
 
r−1 
X
W
+
(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))
r
i=2
X

m
W
γ(ci )
+ǫ
+ (µ(cr ) − γ(cr ))W +
r


(4.19)

i=1

Subtracting (4.18) from (4.19), we get
′′
Em,r

−

′
Em,r

= ǫ[(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr )) +

m
X

γ(ci )]

(4.20)

i=1

Using (4.16) and (4.20), we get
(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr )) +

m
X

γ(ci ) < 0

i=1

Now from Theorem 4.4,
m
r−1
X
X
γ(ci ) > 0
[(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr ))s(ci )] + s(c1 )
i=1

i=1

17

(4.21)

Re-writing the above equation, we get,
(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr ))s(c1 ) +

r−1
X
[(µ(ci )
i=1

− γ(ci ) − µ(cr ) + γ(cr ))s(ci )] + s(c1 )

m
X

(4.22)

γ(ci ) > 0

i=1

Now s(ci ) ≥ 0, ∀i ∈ {1, 2, . . . , r} and according to our Assumption 4 in Section 3,
(µ(ci ) − γ(ci ) − µ(cr ) + γ(cr )) ≤ 0, ∀i ∈ {1, 2, . . . , r}. Hence the ﬁrst and the second term
of (4.22) are negative, and the third term is positive. So for the condition in (4.22) to hold,
the following is necessary:
(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr ))s(c1 ) + s(c1 )

m
X

γ(ci ) > 0

i=1

This means,
(µ(c1 ) − γ(c1 ) − µ(cr ) + γ(cr )) +

m
X

γ(ci ) > 0.

(4.23)

i=1

But (4.21) is in contradiction with (4.23).
′′
′
′
′′ . Hence it stands proved
Hence, Em,r
− Em,r
< 0 is false, which means, Em,r
< Em,r
that we should give equal fractions of jobs to all the machines to get minimum energy.
QED.
Thus, for energy-minimal scheduling in this setting, work has to be divided equally
among r machines, where r is chosen to satisfy (4.6). Using these results we may give a
more general statement.
Corollary 4.6. When a given set of machines are chosen for work, then all those machines
should be in working state for an equal length of time for energy-minimal scheduling.
In the next subsection, we analyze the case when the speeds of machines are also
diﬀerent. That case is more general and includes the current case of identical speeds, but
the results for the identical speed case help develop theorems for variable speed system.

4.2

Systems with Different Speed Machines

In the previous subsection we gained insight on how a subset of machines can prove to
be more advantageous for working for the entire duration of the makespan, while the rest
of the machines are better left idle at all times. In this subsection we use the results of
previous subsection to develop a theory for systems in which machines can have diﬀerent
speeds.
18

From Corollary 4.6, we know that even when the speeds of machines are diﬀerent, all
the machines of the working set should be active for the complete makespan. This means
that if only a working set R of machines is assigned work, then,
τ (ci ) = τ (cj ) = T, ∀i, j ∈ R

(4.24)

τ (ck ) = 0, ∀k ∈
/R

(4.25)

Hence, if work is assigned to the subset R of m machines, where ||R|| = r, the energy
consumption can be found using (4.24) and (4.25) in (3.3), we get,
X
X
Em,r =
µ(ci )T +
γ(ci )T
(4.26)
i∈R

i∈R
/

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

Putting the value of

Pm

(4.27)

i=1

i∈R

i=1 γ(ci )

= Γ in (4.27)
X
Em,r = [ (µ(ci ) − γ(ci )) + Γ]T

(4.28)

i∈R

Using (4.24), the makespan of the system can be found as,
T =P

W
i∈R υ(ci )

(4.29)

Since our aim is to ﬁnd out relative distribution of work, without any loss of generality,
we can assume that the total work is one unit to make the representation simpler, hence
(4.29) can be re-written as:

Using (4.28) in (4.30) we get,
Em,r =

T =P
P

1
i∈R υ(ci )

i∈R (µ(ci )

P

− γ(ci )) + Γ
i∈R υ(ci )

(4.30)

(4.31)

We now ﬁnd out the set R for which Em,r of (4.31) is minimum. For the ease of
representation, let
X
pr =
(µ(ci ) − γ(ci )) + Γ
(4.32)
i∈R

19

and
qr =

X

υ(ci )

(4.33)

i∈R

Hence (4.31) can be written as

Em,r =

pr
qr

We now ﬁnd out that if all the work has to be assigned to only one machine, then which
will that machine be. We present the answer in our ﬁrst lemma of this section.
Lemma 4.7. If all the work is assigned to one machine ci , i.e., ||R|| = 1 and R = {ci },
i )+Γ
.
then for energy minimality this should be the machine with minimum µ(ci )−γ(c
υ(ci )
Proof. Substituting R = {ci } in (4.31), we get,
Em,1 =

(µ(ci ) − γ(ci )) + Γ
υ(ci )

Hence to minimize energy consumption Em,1 , we need to choose ci for which
is minimum.

µ(ci )−γ(ci )+Γ
υ(ci )

As mentioned in Assumption 4 in Section 3, we order the machines such that the ﬁrst
i )+Γ
machine is with minimum µ(ci )−γ(c
. Hence here i = 1, and the ﬁrst machine is given
υ(ci )
work in this case.
Now, if we want to give job to two machines then we will only give if the energy
consumed by two machines is less than the energy consumption of one machine. The
same principle applies whenever we want to expand the working set of machines. The
new expanded set must have lesser energy consumption than the previous set. In the next
theorem, we specify the conditions under which a set can be expanded.
Theorem 4.8. If a machine cj has to be included in the working set of machines R, then
the following condition must be satisfied
P
µ(cj ) − γ(cj )
i ) − γ(ci )) + Γ
i∈R (µ(c
P
(4.34)
>
υ(cj )
i∈R υ(ci )
Proof. Re-writing our condition (4.34), using (4.32) and (4.33)
pr
µ(cj ) − γ(cj )
>
qr
υ(cj )
Multiplying the denominators both sides,
pr υ(cj ) > µ(cj )qr − γ(cj )qr
20

Adding pr qr both sides,
pr υ(cj ) + pr qr > µ(cj )qr − γ(cj )qr + pr qr
pr (υ(cj ) + qr ) > qr (µ(cj ) − γ(cj ) + pr )
pr + µ(cj ) − γ(cj )
pr
>
qr
qr + υ(cj )
Back substituting pr and qr , we get
P
P
(µ(ci ) − γ(ci )) + Γ + µ(cj ) − γ(cj )
i∈R (µ(ci ) − γ(ci )) + Γ
P
P
> i∈R
i∈R υ(ci )
i∈R υ(ci ) + υ(cj )
Let R′ be the new set formed for including cj in R.
P
P
′ (µ(ci ) − γ(ci )) + Γ
i∈R (µ(ci ) − γ(ci )) + Γ
P
> i∈R P
i∈R υ(ci )
i∈R′ υ(ci )

(4.35)

The left hand side of (4.35) gives the energy consumption by working set R. The right
hand side of (4.35), gives the energy consumption when machine cj is included in the
original working set. Hence the energy consumption of the new set is lesser when the
condition (4.34) is satisﬁed.
The previous theorem gives the condition in which a machine could be included in
the working set to reduce the energy consumption of the system. But there can be many
machines which satisfy this condition. We need to ﬁnd out the machine which reduces the
energy consumption by largest amount and hence make the system energy minimal. Our
next theorem speciﬁes which machine should be given preference for inclusion in working
set.
Theorem 4.9. Given any two machines cj and ck which qualify to be included in working
set R according to Theorem 4.8, i.e.,

and

µ(cj ) − γ(cj )
pr
<
υ(cj )
qr

(4.36)

µ(ck ) − γ(ck )
pr
<
υ(ck )
qr

(4.37)

For minimal energy consumption, machine cj shall be chosen over ck if
µ(cj ) − γ(cj )
µ(ck ) − γ(ck )
<
υ(cj )
υ(ck )

21

(4.38)

Proof. Given the condition (4.38), we would like to derive energy equations from it. Multiplying the denominators both sides in (4.38), we get,
(µ(cj ) − γ(cj ))υ(ck ) < (µ(ck ) − γ(ck ))υ(cj )
By adding and subtracting (µ(cj ) − γ(cj ))υ(cj ) in equation (4.2), we get,
(µ(cj ) − γ(cj ))
(µ(cj ) − γ(cj )) − (µ(ck ) − γ(ck ))
<
υ(cj ) − υ(ck )
υ(cj )

(4.39)

From (4.36) and (4.39). We get,
(µ(cj ) − γ(cj )) − (µ(ck ) − γ(ck ))
(µ(cj ) − γ(cj ))
pr
<
<
υ(cj ) − υ(ck )
υ(cj )
qr
(µ(cj ) − γ(cj )) − (µ(ck ) − γ(ck ))
pr
<
υ(cj ) − υ(ck )
qr
((µ(cj ) − γ(cj )) − (µ(ck ) − γ(ck )))qr < pr (υ(cj ) − υ(ck ))
(µ(cj ) − γ(cj ))qr − (µ(ck ) − γ(ck ))qr − pr υ(cj ) + pr υ(ck ) < 0

(4.40)

Adding (4.2) and (4.40), we get,
(µ(cj ) − γ(cj ))qr − (µ(ck ) − γ(ck ))qr − pr υ(cj ) + pr υ(ck )
+ (µ(cj ) − γ(cj ))υ(ck ) − (µ(ck ) − γ(ck ))υ(cj ) < 0

(4.41)

Now adding and subtracting pr qr in (4.41), we get,
pr + µ(cj ) − γ(cj )
pr + µ(ck ) − γ(ck )
<
qr + υ(cj )
qr + υ(ck )

(4.42)

In (4.42), left hand side gives the energy consumption of the system when machine cj is
included in the working set R, while the right hand side gives the energy consumption of
the system when machine ck is included. The energy consumption is lesser with machine
cj in comparison to machine ck and hence machine cj would be given preference to be
included in working set.
When we put Lemma 4.7 and Theorem 4.9 together, we get the order in which machines
will get preference to be alloted work. This order is same as mentioned in Assumption 4
in Section 3. Combining Lemma 4.7, Theorem 4.9 and Assumption 4, we can state a
Corollary.

22

Corollary 4.10. If the machines are indexed in an order such that the first machine
)−γ(ci )
i )+Γ
is the one with smallest µ(ci )−γ(c
and afterwards in increasing order of µ(ciυ(c
,
υ(ci )
i)
and if the working set contains r machines, then for minimal energy consumption R =
{c1 , c2 , . . . , cr }, where each machine in this set is working for an equal amount of time.
Using this Corollary, (4.31) can be re-written as,

 Pr
i ) − γ(ci )) + Γ
i=1 (µ(c
Pr
Em,r = W
i=1 υ(ci )

(4.43)

which gives the energy consumption of a system with total work W .
From (4.43), energy is dependent on work W , but from (4.23) and Theorems 4.8 and 4.9
we know that ﬁnding the number of working machines (value of r) from the given set C of
machines is independent of work W .
We see that (4.23), (4.34) and (4.38) are independent of W , showing that the machines
used and the scheduling decisions do not depend upon the quantum of the work given to
the system. This in turn means that, some systems can be inherently wasteful and energy
ineﬃcient.
These results can be used in conﬁguring the system, that which machines we want
in system model. In some cases we do not want certain machines in the system. When
initially we have certain machines (set C), and we have to design the system, then using
our results we can choose which machines we want in our system.
Corollary 4.11. Given a set C of machines, we use {c1 , c2 , . . . , cr } in our system and
leave {cr+1 , cr+2 , . . . , cm } machines out of system.
Our results are independent of the work to be done. From results we know that, to
minimize the energy of the system some machines should always idle. So these results
(which guide which machines should be used), will help in designing of the system. So that
we can shut-oﬀ some machines which are always kept idle.
In this section, we found the precedence amongst machines for allotting work based on
their energy and speed speciﬁcations. The results derived in this section are applicable for
handling any class of jobs, which means that the precedence of machines will remain same
irrespective of whether the jobs are divisible, non-divisible or whether they have precedence
constraints. In the next sections we consider diﬀerent classes of systems based on type of
jobs.

5

Algorithms and Complexity

Depending upon the jobs to be executed the systems can be classiﬁed into many categories.
We have already mentioned those categories in Section 3. In the current section we analyze
the complexity of scheduling problem for these various types of systems and give scheduling
algorithms for the same. We ﬁrst analyze systems with identical speed machines and then
move ahead to systems with diﬀerent speeds.
23

5.1

Systems with Identical Speed Machines

In Section 4.1, we gave results which govern the scheduling of systems with identical speed
machines. Given the total amount of work and energy speciﬁcations of machines, we can
ﬁnd the number of machines which have to be assigned work using results of Section 4.1.
Algorithm 1 is an implementation of those results.
Algorithm 1: Find the number of working machines of the system in order to minimize the energy consumption when the speeds of machines are identical
input : Number of machines (m), working power of machines (µ(ci )), idle power of machines
(γ(ci )), total work to be done (W )
output: Number of working machines (r), makespan (T ), energy (E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

for i = 1 to m do
calculate µ(ci ) − γ(ci )
end
sort (µ(ci ) − γ(ci ));
low ← 1, high ← m;
while low ≤ high do
mid ← low + (high−low)
;
Pk 2
P
E(k) ← ( W
)[
µ(c
)
+ m
i
i=1
i=k+1 γ(ci )];
k
Calculate E(mid − 1), E(mid), E(mid + 1);
if (E(mid − 1) > E(mid))&&(E(mid) ≤ E(mid + 1)) then
r ← mid;
return r;
else
if E(mid − 1) > E(mid) then
low ← mid;
else
high ← mid;
end
end
end
T ← W
;
r
return T ;

Algorithm 1 takes the number of machines, the working power and idle power of the
machines, and the total work to be done as input, and gives the value of r, i.e., the number
of working machines, as output. The machines are indexed in the precedence order given
by Assumption 4 in Section 3. Now, we apply binary search to ﬁnd the value of r, such that
we get minimal energy value of the system. The algorithm is based on the previously given
results. The computation complexity of Algorithm 1 is O(m). We now ﬁnd the complexity
of scheduling problems and give algorithms for divisible and non-divisible jobs.

24

5.1.1

Divisible Loads

In this case we are given a set P of jobs, where jobs can be arbitrarily broken into any number of smaller jobs and these smaller jobs can be executed parallely on diﬀerent machines.
We consider the energy consumption overhead due to division/breaking of jobs overhead
to be null. Since the jobs are divisible, they can be trivially distributed over r machines
with makespan T , where r and T are given by Algorithm 1.
Hence the energy of system with divisible loads can be calculated using following equation.
Em,r

m
r
X
X
γ(ci )]
µ(ci ) +
= T[

(5.1)

i=r+1

i=1

Using Algorithm 1 and (5.1) we can ﬁnd the energy of the system.
Remark 5.1. Energy-minimal scheduling of divisible jobs on identical speed machines can
be done in linear time.
We now analyze the complexity of scheduling of non-divisible Loads.
5.1.2

Non-divisible Loads

Given the set P of non-divisible jobs, and time required to execute job pj on a machine
with unit speed ψ(pj ); our aim is to distribute the set P of jobs among the given set C
of machines such that energy consumption is minimum. From Corollary 4.6 it is evident
that whichever machines are chosen to work, they should be working for an equal amount
of time to achieve energy minimality. But it is not straightforward of sometimes even
possible to distribute work in such a way when jobs are non-divisible. We prove that it is
an NP-hard problem to calculate the minimal-energy schedule for the current case.
Proposition 5.2. In a system where machines have identical speeds and jobs are nondivisible, computing the energy-minimal schedule is an NP-hard problem.
Proof. Let r denote the number of machines which are given work and T is the makespan
according to Algorithm 1. Since all the machines have identical speed, the scheduling
problem is to make exclusive subsets Pi from set P such that the sum of work in set i is
T , i.e.,
X
ψ(pj ) = T ∀i; 1 ≤ i ≤ r
(5.2)
j∈Pi

Given a ﬁnite set of positive numbers and another positive number called the goal, to
ﬁnd the subset whose sum is closest to the goal is well known as the classical subset-sum
problem (Johnson, 1973). In the current scenario, the set of positive numbers {ψ(pj ) : j ∈
P} has to be distributed in subsets Pi such that sum of each subset is the positive number
25

T . For each subset (Pi ; i ≤ r), this problem of ﬁnding the exclusive subsets Pi can be seen
as the classical subset-sum problem. Since the subset-sum problem is NP-hard (Johnson,
1973), and our problem is reduced to subset-sum problem; energy-minimal scheduling of
jobs in a system where jobs are non-divisible is NP-hard.
Since ﬁnding the energy-minimal schedule is NP-hard, we develop an approximation
algorithm to ﬁnd energy eﬃcient schedules. Though we strive to achieve the makespan
given by Algorithm 1, in a system with non-divisible loads it is not always possible to
achieve it. We state the theorem which speciﬁes the ideal makespan To and working set of
machines Ro for energy minimality of system with non-divisible jobs.
Lemma 5.3. Given a system with identical speed machines and a set P of jobs with longest
job of length ψ(pmax ), the makespan is given by To = max(T, ψ(pmax )) and the working set
of machines Ro = {c1 , c2 , . . . , cro }, where
 
W
ro =
(5.3)
To
Proof. It is not possible to have makespan lesser than ψ(pmax ) since jobs cannot be divided.
Also, if we take To lesser than T , then we cannot have a energy-minimal schedule. Hence
for energy minimality,
To = max(T, ψ(pmax ))
(5.4)
From Corollary 4.6, it is evident that work should be distributed equally if possible to
the working machines. Hence with a possibly increased makespan, the number of working
machines might get decreased and given by (5.3). Also from Lemma 4.3, it is evident that
the working set of machines is given by:
Ro = {c1 , c2 , . . . , cro }

(5.5)

It is not always possible to keep each machine working till time To . Some machines
might work for more than To and some might get less than that because of non-divisibility
of jobs. From Lemma 4.1, we know that the amount of work should be in decreasing
order by the machine’s indices. With all this information, the approximation algorithm for
energy-minimal scheduling of non-divisible jobs can be given as follows.
In Algorithm 2, we index the machines in non-decreasing order of the diﬀerence of their
working power and idle power. Jobs are indexed in non-increasing order of their weight.
Initially we create r empty buckets for jobs to be ﬁlled in. First r jobs are chosen and given
to each r bucket, such that each bucket has one element. Now, to distribute remaining
n − r jobs to the buckets we follow a sequential process. The weighted sum of jobs of each
bucket is calculated and the next job is included in the bucket in which the value is least.
The same process is repeated until all jobs are included in one or other bucket or sets. Now
26

Algorithm 2: Approximation algorithm for energy-eﬃcient scheduling of the system
when the speeds of machines are identical
input : Number of machines (m), working power of machines (µ(ci )), idle power of machines
(γ(ci )), total work to be done (W ), ro , To
output: Makespan (T ), energy (E)
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

S = {} ;
for i = 1 to m do
di ← µ(ci ) − γ(ci ) ;
S = S ∪ {di } ;
end
sort S;
J = {} ;
for j = 1 to n do
J = J ∪ {ψ(pj )} ;
end
reverse-sort (J);
r ← ro ;
Pj = {};
for j = 1 to r do
P
Pj = Pj ∪ {pj };
j∈Pj ψ(pj ) = bj ;
end
for l = r + 1 to n do
calculate min(bj );
bu ← min(bj );
u←j ;
Pj = Pj ∪ {pl };
P
j∈Pj ψ(pj ) = bj ;
end
for i = 1 to r do
assign pi to ci (∀pi ∈ Pi ) ;
end
for iP
= 1 to r do
j∈Pj ψ(pj ) = τ (ci );
sort τ (ci );
T ← max(τ (ci ));
κ(ci ) ← T − τ (ci );
end
T ← max τ (ci ) (∀pi ∈ Pi ) ;
returnPT ;
P
E ← ri=1 µ(ci )τ (ci ) + T m
i=r+1 γ(ci );
return E;

27

we index the buckets in non-decreasing order of their total weights. We assign the jobs of
set i to machine i. Now the working time of all the machines is calculated. Hence we can
calculate the makespan, which is the maximum working time of all the machines.
This approximation algorithm is inspired by Graham’s algorithm (Graham, 1969) which
arranges a set of independent non-divisible jobs on identical speed machines such that the
makespan is minimum. We made some changes in the algorithm to mould it for diﬀerent
power speciﬁcation of machines. We now calculate the bound on deviation from ideal
energy consumption due to approximation.
Theorem 5.4. The maximum possible ratio of energy consumption using Algorithm 2 and
ideal energy consumption is given by:
( 4 − 1 − 1)Γ
E ∗ max
= 1 + Pro 3 3ro
Eo
i=1 (µ(ci ) − γ(ci )) + Γ

(5.6)

Proof. From (3.3), if all the ro machines are working for an equal amount of time To , then
energy consumption is given by:
ro
X
Eo = To [ (µ(ci ) − γ(ci )) + Γ]

(5.7)

i=1

From Algorithm 2, the energy consumed is given by:
E∗ =

ro
X
(µ(ci ) − γ(ci ))τ ∗ (ci ) + ΓT ∗

(5.8)

i=1

Assume that the algorithm gave such τ ∗ i that all the machines other than cj and ck are
allotted work equal to To . Mathematically,
τ ∗ (cj ) = To + ǫ,
where j < k ≤ ro . And

τ ∗ (ci ) = To ,

τ ∗ (ck ) = To − ǫ

∀i 6= j, k,

i ≤ ro

(5.9)
(5.10)

Since j < k, according to our algorithm τ ∗ (cj ) > τ ∗ (ck ) and so ǫ ≥ 0. Using these values
from (5.9) and (5.10) in (5.8), we get,
E ∗ =(µ(cj ) − γ(cj ))(To + ǫ) + (µ(ck ) − γ(ck ))(To − ǫ)
X
(µ(ci ) − γ(ci ))To + ΓT ∗
+

(5.11)

i6=j,k

Simplifying above,
∗

E = (µ(cj ) − γ(cj ) − (µ(ck ) − γ(ck )))ǫ +

ro
X
i=1

28

(µ(ci ) − γ(ci ))To + ΓT ∗

(5.12)

Now since j < k, we have µ(cj ) − γ(cj ) − (µ(ck ) − γ(ck )) ≤ 0. To compute the bound we
are looking for the case where E ∗ is maximum. That will occur when
µ(cj ) − γ(cj ) − (µ(ck ) − γ(ck )) = 0

(5.13)

Using (5.13) in (5.12), we get,
E

∗

ro
X
(µ(ci ) − γ(ci ))To + ΓT ∗
=

max

(5.14)

i=1

Now according to (Graham, 1969), the bound on makespan is given by:
T∗
4
1
= −
To
3 3ro

(5.15)

Using this bound in (5.14), we get
E

∗

max



ro
X
4
1
(µ(ci ) − γ(ci ))To + ΓTo
=
−
3 3ro

(5.16)

i=1

Simplifying above

E ∗ max = To

ro
X

(µ(ci ) − γ(ci )) + Γ

i=1

E

∗

max

= To

ro
X

(µ(ci ) − γ(ci )) + Γ

i=1

!



!

(5.17)


1
4
−
−1
3 3ro

(5.18)

4
1
−
3 3ro

+ To Γ



Substituting the values, we get,
Po
(µ(ci ) − γ(ci )) + Γ]) + To Γ( 34 −
To ( ri=1
E ∗ max
Po
=
(µ(ci ) − γ(ci )) + Γ]
Eo
To [ ri=1
Γ( 4 − 1 − 1)
E ∗ max
= 1 + Pro 3 3ro
Eo
i=1 (µ(ci ) − γ(ci )) + Γ

1
3ro

− 1)

(5.19)
(5.20)

In the worst case, the values of working power and idle power are equal,i.e. µ(ci ) =
γ(ci ); ∀i, so the bound is given by,
E ∗ max
Eo

= 1 + Pr o
= 1+

Γ( 34 −

1
3ro

− 1)

i=1 (µ(ci ) − γ(ci ))
Γ( 34 − 3r1o − 1)

Γ
4
1
= 1+( −
− 1)
3 3ro
1
4
−
=
3 3ro
29

+Γ

If ro is very large,i.e. when ro → ∞, then,
E ∗ max
4
=
Eo
3

(5.21)

(5.20) gives the lower bound of ineﬃciency of our algorithm and (5.21) gives the upper
bound.
We now move ahead to analyze the class of scheduling problems in which machines can
have diﬀerent working speeds.

5.2

Systems with Different Speed Machines

In this section, along with power speciﬁcations of machines we also consider the speeds
of machines to be diﬀerent and give algorithms for both divisible jobs and non-divisible
jobs. In Section 4.2, we proved various lemmas and theorems which govern the scheduling
of systems with diﬀerent speed machines. Using these results Algorithm 3 ﬁnds the set
of machines which should be assigned work for the energy-minimal scheduling when the
machines of the system have diﬀerent speeds.
Algorithm 3 takes the number of machines, the working power, idle power and speeds
of the machines, and the total work to be done as input, and gives the value of r, i.e.,
the number of working machines, as output. In the algorithm, we ﬁrst index the machines
in their precedence order, as given in Assumption 4 in Section 3. Then to calculate the
value of r, we check the condition in (4.34) from Theorem 4.8. Then from the given values
of total work to be done and the computed value of number of machines, we calculate
the makespan. The algorithm also computes the amount of work that has to be given to
respective machines. The complexity of Algorithm 3 is O(m).
We now ﬁnd the complexity of scheduling problems and give algorithms for divisible
and non-divisible jobs.
5.2.1

Divisible Loads

In this case, jobs can be arbitrarily broken into any number of smaller jobs and these
smaller jobs can be executed parallely on diﬀerent machines. Also we consider the energy
consumption overhead due to division/breaking of jobs overhead to be nil. In this scenario
the jobs can be trivially distributed over r machines such that machine ci gets w(ci ) amount
of work(as speciﬁed by Algorithm 3). The energy consumption of system with divisible
load can be given by:

m 
X
w(ci )
w(ci )
+ γ(ci )(T −
)
(5.22)
E=
µ(ci )
υ(ci )
υ(ci )
i=1

Clearly the scheduling of divisible jobs can be done by using Algorithm 3 which is a
linear time algorithm.
30

Algorithm 3: Find the working machines and makespan of the system when the
speeds of machines are diﬀerent
input : 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 )), total work to
be done (W )
output: Number of working machines (r), makespan (T )
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
µ(c1 )−γ(c1 )+Γ
i )+Γ
← min( µ(ci )−γ(c
);
υ(c1 )
υ(ci )
for i = 2 to m do
)−γ(ci )
calculate µ(ciυ(c
i)
end
sort (µ(ci ) − γ(ci ));
for r = 1 to m
do
Pr
(µ(c )−γ(c ))+Γ
]W ;
E(r) ← [ i=1Pr i υ(ci )i
ar+1 −br+1
cr+1

i=1

< E(r) then
r ← r + 1;
return r;
else
stop;
end
if

end
T ← W
;
r
return T ;
w(ci ) ← T ∗ υ(ci );
return w(ci );

31

Remark 5.5. Energy-minimal scheduling of divisible jobs on a system of machines running
at different speeds can be done in linear time.
Many might argue that many systems do not have the luxury to divide loads arbitrarily,
but it must be noted that eﬃciency in a system with divisible loads can be seen as upper
bound to the achievable eﬃciency. We proceed to analyze the case in which jobs are
non-divisible in the next section.
5.2.2

Non-divisible Loads

In this section we ﬁrst prove that scheduling non-divisible jobs for energy optimality on
a system with machines having diﬀerent speeds is an NP-hard problem. We then give an
approximation algorithm for the same.
Theorem 5.6. In a system where machines have different speeds and jobs are non-divisible;
computing energy-minimal schedule in that case is an NP-hard problem.
Proof. The amount of work w(ci ) that has to be assigned to machine ci is given by Algorithm 3. Now we need to make exclusive subsets Pi from set P such that the sum of work
in set Pi is w(ci ), i.e.,
X
ψ(pj ) = w(ci ) ∀i; 1 ≤ i ≤ r
(5.23)
j∈Pi

As also discussed with Theorem 5.2, this is in the form of the subset-sum problem which
is NP-hard (Johnson, 1973).

Since ﬁnding the energy-minimal schedule is NP-hard, we develop an approximation
algorithm to ﬁnd energy eﬃcient schedules. The approximation algorithm tries to distribute
jobs such that the ideal makespan speciﬁed by Algorithm 3 is achieved.
Lemma 5.7. Given a system of machines with different speed and a set P of jobs with
longest job of length ψ(pmax ) and the speed of the fastest machine is given by υmax , the
best possible achievable makespan is given by:
To = max(T,

ψmax
)
υmax

(5.24)

where T is given by Algorithm 3.
Proof. If there is a job which cannot be completed within T , irrespective of the arrangement
of jobs, then we increase the best achievable makespan To to accommodate that biggest
max
job. The biggest job cannot be completed any earlier than ψυmax
. Also, since any schedule
with makespan lesser than T should be suboptimal. Hence,
To = max(T,

32

ψmax
)
υmax

If the makespan is increased then there can be possible reduction in number of working
machines. The ideal number of working machines ro is given by the minimum number of
machines which satisfy,
W
Pr o
≥ To
(5.25)
i=1 υ(ci )

Using this ro as input, we present an approximation algorithm which tries to distribute
jobs amongst machines with diﬀerent speed such that the machines would work for an
equal amount of time.
Algorithm 4: Approximation algorithm for energy-eﬃcient scheduling of the system
when the speeds of machines are diﬀerent
input : Number of machines (m), working power of machines (µ(ci )), idle power of machines
(γ(ci )), speed of machines (υ(ci )), total work to be done (W ), ro , To
output: Makespan (T ), energy (E)
output: Schedule
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
)−γ(ci )
A(i) ← µ(ciυ(c
;
i)
end
sort A(i) in non-decreasing order;
for j = 1 to n do
B(j) ← ψ(pj ) ;
end
sort B(j) in non-increasing order ;
tempi ← 0 ;
for j = 1 to n do
for i = 1 to ro do
ψ(p )
tempi ← υij + tempi ;
end
assign pj to ci , where ci has min(tempi ) ;
end
T ← max τ (ci );
return T ;
P
w(ci )
w(ci )
E← m
i=1 [µ(ci ) υ(ci ) + γ(ci )(T − υ(ci ) )];
return E;

In Algorithm 4, we ﬁrst index the machines in decreasing order of the speed of the
machines. We also index the jobs in non-increasing order of their weights. Now, we take
a job at a time and ﬁnd that on which machine it will ﬁnish ﬁrst, based on the speed of
the machine. Then we assign that job to that particular machine. Similarly the process
is repeated till all the jobs are assigned to some machines. Now, the working time of all
machines is calculated, and the maximum working time of all machines is the makespan.
The approximation algorithm may not achieve the exact To , but it is within certain
bounds.
33

The bound for the makespan given by Dobson (1984) of such an LPT (largest processing
time) schedule is
19
(5.26)
12
Given this bound on makespan, we derive the bound on energy consumption of our
algorithm.
Theorem 5.8. When the speeds as well as the power specifications of the machines are
different, and when jobs are non-divisible, then a bound on the energy consumption using
Algorithm 4 and ideal energy consumption is given by:
E ∗ max
19
≤
Eo
12

(5.27)

Proof. The energy consumption for ideal schedule is given by:
ro
X
µ(ci ) + Γ)
Eo = To (

(5.28)

i=1

Since we do not know which machines are are working for time more than To and which
ones lesser than To , for the upper bound we assume that all machines are working for
T ∗ max . Hence,
ro
X
µ(ci ) + Γ)
(5.29)
E ∗ max = T ∗ max (
i=1

Clearly,

Po
µ(ci ) + Γ)
T ∗ max ( ri=1
E ∗ max
P ro
=
Eo
To ( i=1 µ(ci ) + Γ)

By (Dobson, 1984, Theorem 4.1),

From (5.31) and (5.32), we get,

(5.30)

E ∗ max
T ∗ max
=
Eo
To

(5.31)

19
T ∗ max
≤
To
12

(5.32)

E ∗ max
19
≤
Eo
12

(5.33)

As the bound on energy depends on makespan in our algorithm, the worst case bound
for our algorithm is also 19
12 .

34

6

Energy Efficiency: Incompatible Measures

There can be two measures for assessing the energy eﬃciency of a system of machines:
one, to consider the total energy consumed by the system to complete some work; and the
second, to consider the fraction of the energy consumed by machines in the system to do
work over the total energy consumed in the system.
The ﬁrst measure gives a sense of the energy required by the system per unit work
produced, and the second measure indicates how much of the energy consumed by the
system goes into work, and how much is idle (non-working) consumption by the system.
We hold that the ﬁrst measure, energy per unit work, is the more meaningful one (as it
can lead to lowered overall energy consumption while completing some amount of work).
Our analysis clearly indicates that these two measures of energy eﬃciency are incompatible, in the sense that they cannot be simultaneously optimized for arbitrary systems.
To see why, we may consider (4.43) for the total energy of the system. In (4.43), if we put
γ(ci ) = 0, ∀i, 1 ≤ i ≤ m, then the working energy is given by:
r
i
h
X
W
(6.1)
µ(ci ) Pr
i=1 υ(ci )
i=1

Dividing the above by (4.43), we get the following for the ratio of the working energy
to total energy:
Pr
i=1 µ(ci )
Pr
(6.2)
i=1 (µ(ci ) − γ(ci )) + Γ
This in turn simpliﬁes to:
Pr
µ(ci )
i=1 P
Pr
(6.3)
m
i=1 µ(ci ) +
i=r+1 γ(ci )

Considering (6.3) shows that the ratio of the working energy to total energy can only
be optimized by increasing the value of r, i.e., when r = m, but this violates Theorem 4.4
which tells us that for minimum total energy consumption, the value of r may not be
necessarily be equal to m.
Thus, a system running in such a way as to consume the least possible energy while
completing some work will not always be most eﬃcient in terms of the second measure, as
the energy consumption by the idle machines can be signiﬁcant. Conversely, if we seek to
optimize the system performance by the second measure and reduce the idle consumption
of machines, then the overall energy consumption to do the work is not always minimized.
The data center energy eﬃciency metric called Power Usage Eﬀectiveness (PUE) (Avelar et al.,
2012), an industry standard recommended by the U.S. Environmental Protection Agency
under its Energy Star program,1 is an energy eﬃciency measure of the second kind, as it
considers only the ratio of the total energy to the working energy. It is thus not a surprise
that the PUE comes with its share of controversy and criticisms (Brady et al., 2013).
1

See https://www.energystar.gov/ia/partners/prod development/downloads/DataCenterRating General.pdf.

35

References
Abdullah, M. and M. Othman
2013. Cost-based multi-QoS job scheduling using divisible load theory in cloud computing. Procedia Computer Science, 18:928–935.
Agrawal, P. and S. Rao
2014. Energy-aware scheduling of distributed systems. IEEE Trans. Autom. Sci. Eng.,
11(4):1163–1175.
Agrawal, P. and S. Rao
2015. Energy-minimal scheduling of divisible loads. In 4th International Workshop on
Energy-Efficient Data Centres (E2DC 2015), co-located with ACM E-Energy 2015.
Albers, S.
2009. Algorithms for energy saving. In Efficient Algorithms, Pp. 173–186. Springer.
Augustine, J., S. Irani, and C. Swamy
2004. Optimal power-down strategies. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, Pp. 530–539. IEEE.
Avelar, V., D. Azevedo, and A. French
2012. PUE: A Comprehensive Examination of the Metric. The Green Grid. White Paper
#49.
Bambagini, M., M. Bertogna, M. Marinoni, and G. Buttazzo
2013. An energy-aware algorithm exploiting limited preemptive scheduling under ﬁxed
priorities. In 8th IEEE International Symposium on Industrial Embedded Systems (SIES
2013), Pp. 3–12.
Bansal, N., H.-L. Chan, and K. Pruhs
2009. Speed scaling with an arbitrary power function. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, Pp. 693–701. Society for Industrial
and Applied Mathematics.
Bansal, N., H.-L. Chan, and K. Pruhs
2013. Speed scaling with an arbitrary power function. ACM Transactions on Algorithms
(TALG), 9(2):18.
Bansal, N., T. Kimbrel, and K. Pruhs
2007. Speed scaling to manage energy and temperature. Journal of the ACM (JACM),
54(1):3.
Berral, J. L., I. Goiri, R. Nou, F. Juliá, J. Guitart, R. Gavaldá, and J. Torres
2010. Towards energy-aware scheduling in data centers using machine learning. In
36

e-Energy ’10: Proceedings of the 1st International Conference on Energy-Efficient Computing and Networking, Pp. 215–224.
Brady, G. A., N. Kapur, J. L. Summers, and H. M. Thompson
2013. A case study and critical assessment in calculating power usage eﬀectiveness for a
data centre. Energy Conversion and Management, 76:155–161.
Dobson, G.
1984. Scheduling independent tasks on uniform processors. SIAM Journal on Computing,
13(4):705–716. doi:10.1137/0213044.
Drozdowski, M., J. Marszalkowski, and J. Marszalkowski
2014. Energy trade-oﬀs analysis using equal-energy maps. Future Generation Computer
Systems, 36:311–321.
Graham, R. L.
1969. Bounds on multiprocessing timing anomalies. SIAM journal on Applied Mathematics, 17(2):416–429.
Halliday, D., R. Resnick, and J. Walker
2010. Fundamentals of physics extended, volume 1. John Wiley & Sons.
Herrmann, J. W., ed.
2006. Handbook of Production Scheduling, volume 89 of (International Series in Operations Research & Management Science). Springer.
Hirofuchi, T., H. Nakada, H. Ogawa, S. Itoh, and S. Sekiguchi
2010. Eliminating datacenter idle power with dynamic and intelligent VM relocation. In
Distributed Computing and Artificial Intelligence, volume 79 of Advances in Intelligent
and Soft Computing, Pp. 645–648. Springer Berlin Heidelberg.
Huang, J., C. Buckl, A. Raabe, and A. Knoll
2011. Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems. In 19th Euromicro International Conference on Parallel, Distributed and
Network-Based Processing (PDP 2011), Pp. 447–454, Cyprus.
Irani, S. and K. R. Pruhs
2005. Algorithmic problems in power management. ACM Sigact News, 36(2):63–76.
Johnson, D. S.
1973. Approximation algorithms for combinatorial problems. In Proceedings of the fifth
annual ACM symposium on Theory of computing, Pp. 38–49. ACM.
Le Sueur, E. and G. Heiser
2010. Dynamic voltage and frequency scaling: The laws of diminishing returns. In
37

HotPower ’10: Proceedings of the 2010 International Conference on Power Aware Computing and Systems, Vancouver, Canada.
Lee, K., J. Y. Leung, Z.-h. Jia, W. Li, M. L. Pinedo, and B. M. Lin
2014. Fast approximation algorithms for bi-criteria scheduling with machine assignment
costs. European Journal of Operational Research, 238(1):54–64.
Lee, K., J. Y.-T. Leung, and M. L. Pinedo
2012. Coordination mechanisms for parallel machine scheduling. European Journal of
Operational Research, 220(2):305–313.
Leung, J. Y.-T., K. Lee, and M. L. Pinedo
2012. Bi-criteria scheduling with machine assignment costs. International Journal of
Production Economics, 139(1):321–329.
Pierson, J.-M., ed.
2015. Large-Scale Distributed Systems and Energy Efficiency. John Wiley and Sons.
Wiley Series on Parallel and Distributed Computing.
Pinedo, M. L.
2009. Planning and Scheduling in Manufacturing and Services, 2 edition. Springer.
Pinedo, M. L.
2012. Scheduling: theory, algorithms, and systems. Springer.
Pouwelse, J., K. Langendoen, and H. Sips
2001. Energy priority scheduling for variable voltage processors. In In Intl. Symp. on
Low-Power Electronics and Design, Pp. 28–33.
Robertazzi, T. G., M. A. Moges, and D. Yu
2005. Divisible load scheduling with multiple sources: Closed form solutions. In Conference on Infomation Sciences and Systems.
Sheikh, H. F., H. Tan, I. Ahmad, S. Ranka, and P. B. V.
2012. Energy- and performance-aware scheduling of tasks on parallel and distributed
systems. J. Emerg. Technol. Comput. Syst., 8(4):32:1–32:37.
Shi, H., W. Wang, and N. Kwok
2012. Energy dependent divisible load theory for wireless sensor network workload allocation. Mathematical Problems in Engineering.
Singh, A. K. and S. Sahu
2014. Environment conscious public cloud scheduling algorithm with load balancing.
International Journal of Computer Applications, 87(13):24–27.

38

Veeravalli, B., D. Ghose, and T. G. Robertazzi
2003. Divisible load theory: A new paradigm for load scheduling in distributed systems.
Cluster Computing, 6(1):7–17.
Wang, Y. and M. Saksena
1999. Scheduling ﬁxed-priority tasks with preemption threshold. In Sixth International
Conference on Real-Time Computing Systems and Applications (RTCSA ’99), Pp. 328–
335, Hong Kong, China.
Yao, F., A. Demers, and S. Shenker
1995. A scheduling model for reduced cpu energy. In Foundations of Computer Science,
1995. Proceedings., 36th Annual Symposium on, Pp. 374–382. IEEE.
Yassa, S., R. Chelouah, H. Kadima, and B. Granado
2013. Multi-objective approach for energy-aware workﬂow scheduling in cloud computing
environments. The Scientific World Journal.
Yu, D. and T. G. Robertazzi
2003. Divisible load scheduling for grid computing. In Fifteenth IASTED International
Conference on Parallel and Distributed Computing and Systems, volume 1, Pp. 1–6.
Zomaya, A. Y. and Y. C. Lee, eds.
2012. Energy-Efficient Distributed Computing Systems. Wiley-IEEE Computer Society.

39

