Getting the best response for your erg
Getting the best response for your erg
复制标题
为您的设备获得最佳响应
DOI：
10.1145/1367064.1367078
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
K. Pruhs;Patchrawat Uthaisombut;G. Woeginger
我们考虑速度缩放问题的速度缩放问题，即在使用的能量上，动态释放的作业集合的平均响应时间。最佳日程安排为拒绝，我们表明这种方法为等级工作提供了有效的算法。工作速度不是可用能量的单调函数。 o（1）在平均响应时间方面具有额外的因素（1 +ε）能量。
We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint A on energy used. We propose an algorithmic approach in which an energy optimal schedule is computed for a huge A, and then the energy optimal schedule is maintained as A decreases. We show that this approach yields an efficient algorithm for equi-work jobs. We note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. We then explain why this algorithmic approach is problematic for arbitrary work jobs. Finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is O(1)-approximate with respect to average response time, given an additional factor of (1 + ε) energy.