Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

被引：6

作者：

Davis, James M. ^{[1
]}

Gandhi, Rajiv ^{[2
]}

Kothari, Vijay H. ^{[3
]}

机构：

[1] Cornell Univ, Dept Operat Res, Ithaca, NY 14850 USA

[2] Rutgers State Univ, Dept Comp Sci, Camden, NJ 08102 USA

[3] Dartmouth Coll, Dept Comp Sci, Hanover, NH 03755 USA

来源：

OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 02期

基金：

美国国家科学基金会;

关键词：

Scheduling; Algorithms; Online; Approximation; Primal-dual; Dual fitting; DATA MIGRATION;

D O I：

10.1016/j.orl.2012.12.001

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 [171). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1 + root 2. The latter implies that the cost of the optimal schedule is within a factor of 1 + root 2 of the cost of the optimal LP solution. (c) 2012 Elsevier B.V. All rights reserved.

引用

页码：121 / 125

页数：5

共 23 条

[11] 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
[12] Graham R. L., 1979, Discrete Optimisation, P287
[13] 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
[14] Kim YA, 2003, SIAM PROC S, P97
[15] A class of on-line scheduling algorithms to minimize total completion time
Lu, X
Sitters, RA
Stougie, L
[J]. OPERATIONS RESEARCH LETTERS, 2003, 31 (03) : 232 - 236
[16] Minimizing the sum of weighted completion times in a concurrent open shop
Mastrolilli, Monaldo
Queyranne, Maurice
Schulz, Andreas S.
Svensson, Ola
Uhan, Nelson A.
[J]. OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 390 - 395
[17] On-line scheduling to minimize average completion time revisited
Megow, N
Schulz, AS
[J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (05) : 485 - 490
[18] Queyranne M, 1994, 4081994 TU BERL
[19] Schulz AS, 2002, J SCHEDULING, V5, P121, DOI [10.1002/jos.93, 10.1002/jos.093]
[20] SCHULZ AS, 1996, LECT NOTES COMPUT SC, V1084, P301

← 1 2 3 →