Fast iterative improvement methods for project scheduling under partially renewable resources

Andreas Schirmer

No 501, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: It is well-known that for many project scheduling problems the Space AS of active schedules contains at least one optimal solution for each feasible instance, so restricting heuristic construction methods to AS will improve algorithmic efficiency without foresaking the chance to eventually find an optimal schedule. Yet, for some problems such results are not directly applicable. We address one such problem, namely the resource-constrained project scheduling problem under partially renewable resources (RCPSP/TI). Here delaying certain activities may yield better solutions than starting each activity as soon as possible. Since AS is the smallest space guaranteed to contain optimal schedules, it would be desirable to devise methods which sample AS, or at least the next-larger Space SAS of semi-active schedules. However, no such methods are in sight because the "delay problem" of which activities should be delayed and by how many periods cannot be properly addressed during the construction process, when not all remaining resource capacities are known. Indeed, all priority rulebased construction methods for the RCPSP/TI use scheduling schemes which sample the next-larger space FS of feasible schedules. But while the delay problem withstands solution during the construction of schedules, it can be solved afterwards, suggesting the idea of fast iterative improvement algorithms which use appropriate shift operations to improve heuristically constructed feasible schedules. We develop several such approaches, using local and global shifts, and evaluate the effect of different design choices on effectiveness and efficiency of the algorithms. Computational results validate the efficacy of our approach.

Keywords: PROJECT SCHEDULING; PARTIALLY RENEWABLE RESOURCES; ACTIVE SCHEDULES; SHIFT; ITERATIVE IMPROVEMENT (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147589/1/manuskript_501.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:501

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().