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)

    Abstract

    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
    PublisherSpringer
    Pages381-390
    ISBN (Print)978-3-540-00142-3
    DOIs
    Publication statusPublished - 2002

    Publication series

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

    Fingerprint

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

    Cite this