Optimal speed scaling under arbitrary power functions
Optimal speed scaling under arbitrary power functions
复制标题
任意幂函数下的最佳速度缩放
DOI：
10.1145/1639562.1639576
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Tang
中科院分区：
文献类型：
--
作者：
L. Andrew;A. Wierman;A. Tang
本文研究了在线动态速度缩放算法的性能，目的是最大程度地减少能量和响应时间的线性组合。我们证明（SRPT，p-1（n））使用最短的剩余处理时间（SRPT）调度和进程的速度，使所使用的功率等于队列长度，对于非常宽的类是2竞争力功率速度权衡功能。此外，我们证明存在权衡功能，因此没有在线算法的竞争比率低于2。
This paper investigates the performance of online dynamic speed scaling algorithms for the objective of minimizing a linear combination of energy and response time. We prove that (SRPT, P--1 (n)), which uses Shortest Remaining Processing Time (SRPT) scheduling and processes at speed such that the power used is equal to the queue length, is 2-competitive for a very wide class of power-speed tradeoff functions. Further, we prove that there exist tradeoff functions such that no online algorithm can attain a competitive ratio less than 2.