On-line scheduling to minimize average completion time revisited

被引：47

作者：

Megow, N

Schulz, AS

机构：

[1] Tech Univ Berlin, Inst Math, D-10623 Berlin, Germany

[2] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 05期

关键词：

scheduling; on-line algorithm; approximation algorithm; competitive analysis;

D O I：

10.1016/j.orl.2003.11.008

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：485 / 490

页数：6

共 18 条

[1] AFRATI F, 1999, P 40 ANN IEEE S FDN, P32
[2] ALBETOULLE J, 1984, PROGR COMBINATORIAL, P245
[3] Anderson EJ, 2002, SIAM PROC S, P548
[4] Approximation techniques for average completion time scheduling
Chekuri, C
Motwani, R
Natarajan, B
Stein, C
[J]. SIAM JOURNAL ON COMPUTING, 2001, 31 (01) : 146 - 166
[5] BOUNDS FOR THE OPTIMAL SCHEDULING OF NORMAL-JOBS ON META-PROCESSORS
EASTMAN, WL
EVEN, S
ISAACS, IM
[J]. MANAGEMENT SCIENCE, 1964, 11 (02) : 268 - 279
[6] Single machine scheduling with release dates
Goemans, MX
Queyranne, M
Schulz, AS
Skutella, M
Wang, YG
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (02) : 165 - 192
[7] Graham R. L., 1979, Discrete Optimisation, P287
[8] Scheduling to minimize average completion time: Off-line and on-line approximation algorithms
Hall, LA
Schulz, AS
Shmoys, DB
Wein, J
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (03) : 513 - 544
[9] HOOGEVEEN JA, 1996, LECT NOTES COMPUTER, V1084, P404
[10] Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X

← 1 2 →