Energy Optimization in Speed Scaling Models via Submodular Optimization

摘要

In this paper, we propose a new methodology for the speed scaling problem based on its link to scheduling with controllable processing times and submodular optimization. It results in faster algorithms for traditional speed scaling models, characterized by a common speed/energy function. In addition, it handles efficiently the most general models with job-dependent speed/energy functions, with a single and multiple machines, which to the best of our knowledge have not been addressed in the past. In particular, the general version of the single-machine case is solvable by the new technique in O(n~2) time, faster than by the existing methods capable of solving only its special case.