algorithm aLG-d: In an idle period
first remain in the active state. After
b/r time units, if the period has not
ended yet, transition to the sleep state.
It is easy to prove that ALG-D is
2-competitive. We only need to consider two cases. If r T < b, then ALG-D
consumes rT units of energy during
the idle interval and this is in fact
equal to the consumption of OPT. If
r T ³ b, then ALG-D first consumes r .
b/r = b energy units to remain in the
active state. An additional power-up
cost of b is incurred at the end of the
idle interval. Hence, ALG-D’s total cost
is 2b, while OPT incurs a cost of b for
the power-up operation at the end of
the idle period.
It is also easy to verify that no deterministic online algorithm can achieve
a competitive ratio smaller than 2. If an
algorithm transitions to the sleep state
after exactly t time units, then in an
idle period of length t it incurs a cost of
tr + b while OPT pays min{rt, b} only.
We remark that power management
in two-state systems corresponds to
the famous ski-rental problem, a cornerstone problem in the theory of
online algorithms, see, for example,
Irani and Karlin. 26
Interestingly, it is possible to beat
the competitiveness of 2 using ran-domization. A randomized algorithm
transitions to the sleep state according
to a probability density function p(t).
The probability that the system powers down during the first t0 time units
of an idle period is ò0t0p(t)dt. Karlin et
al. 28 determined the best probability
distribution. The density function is
the exponential function ert/b, multiplied by the factor to ensure that
p(t) integrated over the entire time
horizon is 1, that is, the system is definitely powered down at some point.
algorithm aLG-r: Transition to the
sleep state according to the probability density function
ALG-R achieves a considerably
improved competitiveness, as com-
pared to deterministic strategies.
Results by Karlin et al. 28 imply that
ALG-R attains a competitive ratio of
number. More precisely, in any idle
period the expected energy consump-
tion of ALG-R is not more than
times that of OPT. Again, is the best
competitive ratio a randomized strat-
egy can obtain. 28
Karlin et al. 28 proposed the following
strategy that, given Q, simply uses the
best algorithm ALGt.
algorithm aLG-P: Given a fixed Q, let
AQ be the deterministic algorithm ALGt
that minimizes Equation 1.
Karlin et al. proved that for any Q,
the expected energy consumption of
ALG-P is at most times the expected
optimum consumption.
systems with multiple states
Many modern devices, beside the
active state, have not only one but several low-power states. Specifications
of such systems are given, for instance,
in the Advanced Configuration and
Power Management Interface (ACPI)
that establishes industry-standard
interfaces enabling power management and thermal management of
mobile, desktop and server platforms.
A description of the ACPI power
management architecture built into
Microsoft Windows operating systems can be found at http://www.
microsoft.com/whdc/system/pnppwr/
powermgmt/ default.mspx. 1
Consider a system with l states s1, …,
sl. Let ri be the power consumption
rate of si. We number the states in
order of decreasing rates, such as, r1
> … > rl. Hence s1 is the active state
and sl represents the state with lowest energy consumption. Let bi be
the energy required to transition
the system from si to the active state
s1. As transitions from lower-power
states are more expensive we have
b1 £ … £ bl. Moreover, obviously, b1 =
0. We assume again that transitions
from higher-power to lower-power
states incur 0 cost because the corresponding energy is usually negligible.
The goal is to construct a state transition schedule minimizing the total
energy consumption in an idle period.
Irani et al. 24 presented online and
offline algorithms. They assume that
the transition energies are additive,
such as, transitioning from a lower-power state sj to a higher-power state
si, where i < j, incurs a cost of bj − bi. An
figure 1. illustration of the optimum cost
in a four-state system.
Energy
State 2 State 1
State 3
State 4