Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates

被引：3

作者：

Jaeger, Sven ^{[1
]}

机构：

[1] TU Berlin, Inst Math, Sekr MA 5-2,Str 17 Juni 136, D-10623 Berlin, Germany

来源：

OPERATIONS RESEARCH LETTERS | 2018年 / 46卷 / 05期

关键词：

Approximation algorithm; Scheduling; Precedence constraints; Total weighted completion time; Time-indexed LP relaxation; SCHEDULING PROBLEMS; GENERAL-CLASS; BOUNDS;

D O I：

10.1016/j.orl.2018.07.006

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a (2+2 In 2+epsilon)-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：505 / 509

页数：5

共 17 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2] Optimal Long Code Test with One Free Bit [J].

Bansal, Nikhil ;

Khot, Subhash .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :453-462

[3]

Chakrabarti S., 1996, Automata, Languages and Programming. 23rd International Colloquium, ICALP '96. Proceedings, P646

[4] Approximation Algorithms for Scheduling with Resource and Precedence Constraints [J].

Demirci, Gokalp ;

Hoffmann, Henry ;

Kim, David H. K. .

35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96

[5]

Graham R. L., 1979, Discrete Optimisation, P287

[6] 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

[7]

Hall LA, 1996, PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P142

[8] Non-approximability results for scheduling problems with minsum criteria [J].

Hoogeveen, H ;

Schuurman, P ;

Woeginger, GJ .

INFORMS JOURNAL ON COMPUTING, 2001, 13 (02) :157-168

[9] Better Unrelated Machine Scheduling forWeighted Completion Time via Random Offsets from Non-Uniform Distributions [J].

Im, Sungjin ;

Li, Shi .

2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, :138-147

[10] COMPLEXITY OF SCHEDULING UNDER PRECEDENCE CONSTRAINTS [J].

LENSTRA, JK ;

RINNOOYKAN, AHG .

OPERATIONS RESEARCH, 1978, 26 (01) :22-35

← 1 2 →