Greedy multiprocessor server scheduling

被引：12

作者：

Bussema, Carl ^{[1
]}

Torng, Eric ^{[1
]}

机构：

[1] Michigan State Univ, Dept Comp Sci & Engn, E Lansing, MI 48824 USA

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 04期

关键词：

online scheduling; algorithms; flow; multiprocessor; l(p) norm; greedy;

D O I：

10.1016/j.orl.2005.07.005

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We show that the greedy highest density first (HDF) algorithm is (1 + epsilon)-speed O(1) -competitive for the problem of minimizing the lp norms of weighted flow time on in identical machines. Similar results for minimizing unweighted flow provide insight into the power of migration. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：451 / 458

页数：8

共 15 条

[1]

Avrahami Nir, 2003, P 15 ANN ACM S PAR A, P11, DOI DOI 10.1145/777412.777415

[2]

Awerbuch B., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P198, DOI 10.1145/301250.301304

[3]

Bansal N, 2003, SIAM PROC S, P508

[4]

BANSAL N., 2004, P 6 THEOR INF LAT AM, P434

[5]

Bansal N., 2003, P 35 S THEOR COMP ST, P242

[6]

Becchetti L, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P548

[7]

Becchetti L, 2001, LECT NOTES COMPUT SC, V2129, P36

[8]

Chekuri C., 2001, P 33 ANN ACM S THEOR, P84

[9]

Chekuri C., 2004, STOC, P363

[10] Speed is as powerful as clairvoyance [J].

Kalyanasundaram, B ;

Pruhs, K .

JOURNAL OF THE ACM, 2000, 47 (04) :617-643

← 1 2 →