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ₗeftₜoᵣightₛoda₂003 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 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.