Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/147589
Authors: 
Schirmer, Andreas
Year of Publication: 
1999
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 501
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.
Subjects: 
PROJECT SCHEDULING
PARTIALLY RENEWABLE RESOURCES
ACTIVE SCHEDULES
SHIFT
ITERATIVE IMPROVEMENT
Document Type: 
Working Paper

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.