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

Goemans, MX ;

Queyranne, M ;

Schulz, AS ;

Skutella, M ;

Wang, YG .

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

Hall, LA ;

Schulz, AS ;

Shmoys, DB ;

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

Lu, X ;

Sitters, RA ;

Stougie, L .

OPERATIONS RESEARCH LETTERS, 2003, 31 (03) :232-236

[16] Minimizing the sum of weighted completion times in a concurrent open shop [J].

Mastrolilli, Monaldo ;

Queyranne, Maurice ;

Schulz, Andreas S. ;

Svensson, Ola ;

Uhan, Nelson A. .

OPERATIONS RESEARCH LETTERS, 2010, 38 (05) :390-395

[17] On-line scheduling to minimize average completion time revisited [J].

Megow, N ;

Schulz, AS .

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 →