Online weighted flow time and deadline scheduling

被引：35

作者：

Becchetti, Luca ^{[1
]}

Leonardi, Stefano ^{[1
]}

Marchetti-Spaccamela, Alberto ^{[1
]}

Pruhs, Kirk ^{[2
]}

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, Rome, Italy

[2] Univ Pittsburgh, Dept Comp Sci, Pittsburgh, PA USA

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2006年 / 4卷 / 03期

关键词：

Scheduling; Weighted flow time; On-line;

D O I：

10.1016/j.jda.2005.12.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r(i), pmtn| Sigma w(i)F(i). We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling. (C) 2005 Elsevier B.V. All rights reserved.

引用

页码：339 / 352

页数：14

共 12 条

[1]

Aacharya S., 1998, 4 ACM IEEE INT C MOB, P43

[2]

Ausiello G., 1999, COMPLEXITY APPROXIMA

[3] Server scheduling in the weighted lp norm [J].

Bansal, N ;

Pruhs, K .

LATIN 2004: THEORETICAL INFORMATICS, 2004, 2976 :434-443

[4]

Bansal N., 2003, ACM SIAM S DISCR ALG, P508

[5]

Chekuri C., 2001, ACM SIAM S THEOR COM

[6]

Chekuri C., 2001, ACM S THEOR COMP

[7] Minimizing flow time nonclairvoyantly [J].

Kalyanasundaram, B ;

Pruhs, KR .

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :345-352

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

Kalyanasundaram, B ;

Pruhs, K .

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

[9]

Labetoulle J., 1984, PREEMPTIVE SCHEDULIN, P245

[10]

LEONARDI S, 1997, ACM S THEOR COMP, P110

← 1 2 →