Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks

Nir Halman; Chung Lun Li; David Simchi-Levi

doi:10.1007/978-3-540-85363-3_8

Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks

Nir Halman, Chung Lun Li, David Simchi-Levi

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.

Original language	English
Title of host publication	Approximation, Randomization and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
Pages	91-103
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-540-85363-3_8
Publication status	Published - 22 Sept 2008
Event	11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 - Boston, MA, United States Duration: 25 Aug 2008 → 27 Aug 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5171 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
Country/Territory	United States
City	Boston, MA
Period	25/08/08 → 27/08/08

Keywords

Approximation algorithms
Project management
Time-cost tradeoff

ASJC Scopus subject areas

General Computer Science
General Biochemistry,Genetics and Molecular Biology
Theoretical Computer Science

More information

10.1007/978-3-540-85363-3_8

Cite this

Halman, N., Li, C. L., & Simchi-Levi, D. (2008). Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings (pp. 91-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5171 LNCS). https://doi.org/10.1007/978-3-540-85363-3_8

Halman, Nir ; Li, Chung Lun ; Simchi-Levi, David. / Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. pp. 91-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{11243fb5a534432a8477d3676078b044,

title = "Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks",

abstract = "We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.",

keywords = "Approximation algorithms, Project management, Time-cost tradeoff",

author = "Nir Halman and Li, {Chung Lun} and David Simchi-Levi",

year = "2008",

month = sep,

day = "22",

doi = "10.1007/978-3-540-85363-3_8",

language = "English",

isbn = "3540853626",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "91--103",

booktitle = "Approximation, Randomization and Combinatorial Optimization",

note = "11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 ; Conference date: 25-08-2008 Through 27-08-2008",

}

Halman, N, Li, CL & Simchi-Levi, D 2008, Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks. in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5171 LNCS, pp. 91-103, 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008, Boston, MA, United States, 25/08/08. https://doi.org/10.1007/978-3-540-85363-3_8

Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks. / Halman, Nir; Li, Chung Lun; Simchi-Levi, David.
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. p. 91-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5171 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks

AU - Halman, Nir

AU - Li, Chung Lun

AU - Simchi-Levi, David

PY - 2008/9/22

Y1 - 2008/9/22

N2 - We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.

AB - We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.

KW - Approximation algorithms

KW - Project management

KW - Time-cost tradeoff

UR - http://www.scopus.com/inward/record.url?scp=51849106514&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-85363-3_8

DO - 10.1007/978-3-540-85363-3_8

M3 - Conference article published in proceeding or book

SN - 3540853626

SN - 9783540853626

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 91

EP - 103

BT - Approximation, Randomization and Combinatorial Optimization

T2 - 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008

Y2 - 25 August 2008 through 27 August 2008

ER -

Halman N, Li CL, Simchi-Levi D. Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. p. 91-103. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85363-3_8

Fully polynomial time approximation schemes for time-cost tradeoff problems in series-parallel project networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this