Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan

This paper deals with power-aware scheduling of preemptable jobs on identical parallel processors to minimize schedule length when jobs are described by continuous, strictly concave functions relating their processing speed at time t to the amount of power allotted at the moment. Power is a continuous, doubly constrained resource, i.e. both: its availability at time t and consumption over scheduling horizon are constrained. Precedence constraints among jobs are represented by a task-on-arc graph. A methodology based on properties of optimal schedules is presented for solving the problem optimally for a given ordering of nodes in the graph. Heuristics for finding an ordering which leads to possibly short schedules are proposed and examined experimentally.