Greedy Minimum-Energy Scheduling
share
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. Idle processors can be turned off to save energy, while turning them on requires a fixed amount of energy. For the special case of a single processor, the greedy Left-to-Right algorithm 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 OPT + P, where OPT is the energy consumed by an optimal solution and P < OPT is the total processing volume. Our algorithm has a running time of 𝒪(n f log d), where d is the difference between the latest deadline and the earliest release time, and f is the running time of a maximum flow calculation in a network of 𝒪(n) nodes.
READ FULL TEXT