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 [J].

Chekuri, C ;

Motwani, R ;

Natarajan, B ;

Stein, C .

SIAM JOURNAL ON COMPUTING, 2001, 31 (01) :146-166

[8] Improved Results for Data Migration and Open Shop Scheduling [J].

Gandhi, Rajiv ;

Halldorsson, Magnus M. ;

Kortsarz, Guy ;

Shachnai, Hadas .

ACM TRANSACTIONS ON ALGORITHMS, 2006, 2 (01) :116-129

[9] Combinatorial Algorithms for Data Migration to Minimize Average Completion Time [J].

Gandhi, Rajiv ;

Mestre, Julian .

ALGORITHMICA, 2009, 54 (01) :54-71

[10] Two-dimensional Gantt charts and a scheduling algorithm of Lawler [J].

Goemans, MX ;

Williamson, DP .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (03) :281-294

← 1 2 3 →