Speed Scaling with an Arbitrary Power Function

被引：24

作者：

Bansal, Nikhil ^{[1
]}

Chan, Ho-Leung ^{[2
]}

Pruhs, Kirk ^{[3
]}

机构：

[1] Eindhoven Univ Technol, NL-5600 MB Eindhoven, Netherlands

[2] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[3] Univ Pittsburgh, Dept Comp Sci, Pittsburgh, PA 15260 USA

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2013年 / 9卷 / 02期

基金：

美国国家科学基金会;

关键词：

Speed scaling; scheduling;

D O I：

10.1145/2438645.2438650

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this setting. We show that a natural algorithm, which uses Shortest Remaining Processing Time for scheduling and sets the power to be one more than the number of unfinished jobs, is 3-competitive for the objective of total flow time plus energy. We also show that another natural algorithm, which uses Highest Density First for scheduling and sets the power to be the fractional weight of the unfinished jobs, is a 2-competitive algorithm for the objective of fractional weighted flow time plus energy.

引用

页数：14

共 12 条

[1] Energy-Efficient Algorithms for Flow Time Minimization [J].

Albers, Susanne ;

Fujiwara, Hiroshi .

ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)

[2]

Andrew Lachlan L. H., 2009, Performance Evaluation Review, V37, P39, DOI 10.1145/1639562.1639576

[3]

Bansal N, 2008, LECT NOTES COMPUT SC, V5125, P409, DOI 10.1007/978-3-540-70575-8_34

[4]

Bansal N, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P805

[5]

Bansal N, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1238

[6] The impact of dynamically heterogeneous multicore processors on thread scheduling [J].

Bower, Fred A. ;

Sorin, Daniel J. ;

Cox, Landon P. .

IEEE MICRO, 2008, 28 (03) :17-25

[7]

Gupta A., 2010, P IEEE INT GREEN COM

[8]

Gupta A, 2010, LECT NOTES COMPUT SC, V6198, P312, DOI 10.1007/978-3-642-14165-2_27

[9]

Lam TW, 2008, LECT NOTES COMPUT SC, V5193, P647

[10] An efficient algorithm for computing optimal discrete voltage schedules [J].

Li, MM ;

Yao, FF .

SIAM JOURNAL ON COMPUTING, 2006, 35 (03) :658-671

← 1 2 →