Greedy Minimum-Energy Scheduling

Abstract We consider the problem of energy-efficient scheduling across multiple processors with a power-down mechanism. In this setting a set of n jobs with individual release times, deadlines, and processing volumes must be scheduled across m parallel processors while minimizing the consumed energy.When idle, each processor can be turned off to save energy, while turning it on requires a fixed amount of energy.For the special case of a single processor, the greedy Left-to-Right algorithm {irani_left_to_right_soda_2003} guarantees an approximation factor of $2$.We generalize this simple greedy policy to the case of m ≥ 1 processors running in parallel and show that the energy costs are still bounded by 2 + P, where is the energy consumed by an optimal solution and P < is the total processing volume.Our algorithm has a running time of O(n f log d), where d is the difference between the last deadline and the earliest release time, and f is the running time of a maximum flow calculation in a network of O(n) nodes.