TY - GEN

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

AU - Grigoriev, A.

AU - Woeginger, G.J.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-36136-7_34

DO - 10.1007/3-540-36136-7_34

M3 - Conference contribution

SN - 978-3-540-00142-3

T3 - Lecture Notes in Computer Science

SP - 381

EP - 390

BT - Algorithms and Computation (Proceedings of the 13th Annual International Symposium, ISAAC'02, Vancouver BC, Canada, September 21-23, 2002)

PB - Springer

CY - Berlin

ER -