Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints
复制标题
DOI：
10.1287/ijoc.2017.0758
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
中科院分区：
文献类型：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
在本文中，我们根据其与可控处理时间和次管的优化的链接，提出了一种针对速度缩放问题的新方法。它为传统的速度尺度模型提供了更快的算法，其特征在于通用速度/能量功能。此外，它有效地处理了具有工作依赖的速度/能量功能的最通用的模型，该模型具有单个和多台计算机。据我们所知，这在本研究之前尚未解决。特别是，在O（n2）时间中，新技术可以解决单机盒的一般版本。
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.