On-line scheduling to minimize average completion time revisited

被引：50
作者：
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 [J].
Chekuri, C ;
Motwani, R ;
Natarajan, B ;
Stein, C .
SIAM JOURNAL ON COMPUTING, 2001, 31 (01) :146-166
[5]   BOUNDS FOR THE OPTIMAL SCHEDULING OF NORMAL-JOBS ON META-PROCESSORS [J].
EASTMAN, WL ;
EVEN, S ;
ISAACS, IM .
MANAGEMENT SCIENCE, 1964, 11 (02) :268-279
[6]   Single machine scheduling with release dates [J].
Goemans, MX ;
Queyranne, M ;
Schulz, AS ;
Skutella, M ;
Wang, YG .
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 [J].
Hall, LA ;
Schulz, AS ;
Shmoys, DB ;
Wein, 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
12