A (2+ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

被引：6

作者：

Sitters, Rene ^{[1
,2
]}

Yang, Liya ^{[3
]}

机构：

[1] Vrije Univ Amsterdam, NL-1081 HV Amsterdam, Netherlands

[2] CWI, NL-1098 XG Amsterdam, Netherlands

[3] East China Univ Sci & Technol, Shanghai 200237, Peoples R China

来源：

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

关键词：

Scheduling; Approximation algorithm; Precedence constraints; Total weighted completion time;

D O I：

10.1016/j.orl.2018.05.007

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give a (2 + epsilon)-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016). (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：438 / 442

页数：5

共 50 条

[1] A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
Skutella, Martin
OPERATIONS RESEARCH LETTERS, 2016, 44 (05) : 676 - 679
[2] Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect
Eren, Tamer
APPLIED MATHEMATICS AND COMPUTATION, 2009, 208 (02) : 355 - 358
[3] SCHEDULING WITH RELEASE DATES ON A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME
BELOUADAH, H
POSNER, ME
POTTS, CN
DISCRETE APPLIED MATHEMATICS, 1992, 36 (03) : 213 - 231
[4] SCHEDULING OF A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME SUBJECT TO RELEASE DATES
BIANCO, L
RICCIARDELLI, S
NAVAL RESEARCH LOGISTICS, 1982, 29 (01) : 151 - 167
[5] Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine
Liu, ZH
Cheng, TCE
THEORETICAL COMPUTER SCIENCE, 2005, 347 (1-2) : 288 - 298
[6] A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
Pisaruk, NN
DISCRETE APPLIED MATHEMATICS, 2003, 131 (03) : 655 - 663
[7] Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
Chekuri, C
Motwani, R
DISCRETE APPLIED MATHEMATICS, 1999, 98 (1-2) : 29 - 38
[8] Genetic Local Search Algorithm for minimizing the total completion time in single machine scheduling problem with release dates and precedence constraints
Zaidi, Ichraf
Mrad, Mehdi
Ladhari, Talel
2013 5TH INTERNATIONAL CONFERENCE ON MODELING, SIMULATION AND APPLIED OPTIMIZATION (ICMSAO), 2013,
[9] On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times
Ng, CT
Cheng, TCE
Yuan, JJ
Liu, ZH
OPERATIONS RESEARCH LETTERS, 2003, 31 (04) : 323 - 326
[10] Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates
Jaeger, Sven
OPERATIONS RESEARCH LETTERS, 2018, 46 (05) : 505 - 509

← 1 2 3 4 5 →