Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget

摘要

We consider the problem of unrelated parallel machine scheduling when the DVS (dynamic voltage scaling) method is used to conserve energy consumption. Given an energy budget, we present (2+∈)-approximation algorithms for the makespan minimization problem under two different settings, the continuous model in which speeds are allowed to be any real number in [s_(min),s_(max)] and the discrete model in which only d distinct speeds are available. We also show how to derive a 2-approximation algorithm if the energy budget is allowed to be slightly exceeded.