Project scheduling with irregular costs : Complexity, approximability, and algorithms

A. Grigoriev, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)


We address a generalization of the classical discrete time-cost tradeoff problem where the costs are irregular and depend on the starting and the completion times of the activities. We present a complete picture of the computational complexity and the approximability of this problem for several natural classes of precedence constraints. We prove that the problem is NP-hard and hard to approximate, even in case the precedence constraints form an interval order. For orders of bounded height, there is a complexity jump: For height one, the problem is polynomially solvable, whereas for height two, it is NP-hard and APX-hard. Finally, the problem is shown to be polynomially solvable for orders of bounded width and for series parallel orders.
Original languageEnglish
Title of host publicationAlgorithms and Computation (Proceedings of the 13th Annual International Symposium, ISAAC'02, Vancouver BC, Canada, September 21-23, 2002)
Place of PublicationBerlin
ISBN (Print)978-3-540-00142-3
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Project scheduling with irregular costs : Complexity, approximability, and algorithms'. Together they form a unique fingerprint.

Cite this