Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices

We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set

R

of available speeds of the device, (ii) a set

J

of jobs, and (iii) a precedence constraint Π among

J

. Each job

j

in

J

, defined by its arrival time

a

j

, deadline

d

j

, and amount of computation

c

j

, is supposed to be processed by the device at a speed in

R

. Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in

J

such that the required energy consumption is minimized.

This paper focuses on the setting of

weakly

dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if

a

j

=

a

j

′

and

d

j

=

d

j

′

hold for all

j

,

j

′∈

Jand

|

R

|=2. If |

R

|<∞, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) Π = ∅ and for any

j

,

j

′ ∈

J

,

a

j

≤

a

j

′

implies

d

j

≤

d

j

′

. To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem.