Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich · INFORMS journal on computing · 2017
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. Additionally, it efficiently handles the most general models with job-dependent speed/energy functions with single and multiple machines. To the best of our knowledge, this has not been addressed prior to this study. In particular, the general version of the single-machine case is solvable by the new technique in O(n2) time. The online appendix is available at https://doi.org/10.1287/ijoc.2017.0758 .