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 条

[1] Anderson EJ, 2002, SIAM PROC S, P548
[2] [Anonymous], 1996, LECT NOTES COMPUTER
[3] [Anonymous], 2010, The Design of Approximation Algorithms, DOI DOI 10.1017/CBO9780511921735
[4] [Anonymous], P 40 ANN IEEE S FDN
[5] Brucker P., 1977, Ann. Discrete Math., V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[6] CHAKRABARTI S, 1996, LECT NOTES COMPUT SC, V1099, P646
[7] 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
[8] Improved Results for Data Migration and Open Shop Scheduling
Gandhi, Rajiv
Halldorsson, Magnus M.
Kortsarz, Guy
Shachnai, Hadas
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2006, 2 (01) : 116 - 129
[9] Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
Gandhi, Rajiv
Mestre, Julian
[J]. ALGORITHMICA, 2009, 54 (01) : 54 - 71
[10] Two-dimensional Gantt charts and a scheduling algorithm of Lawler
Goemans, MX
Williamson, DP
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (03) : 281 - 294

← 1 2 3 →