Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
提出一种新方法，将速度缩放问题与可控加工时间调度及子模优化联系起来，从而为传统模型提供更快算法，并首次高效处理了最一般的单机和多机模型。
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(n 2 ) time. The online appendix is available at https://doi.org/10.1287/ijoc.2017.0758 .