Fast iterative improvement methods for project scheduling under partially renewable resources

Arbeitspapier

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.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 501

Klassifikation und Themen

• Klassifikation: Management
• Thema: PROJECT SCHEDULING ; PARTIALLY RENEWABLE RESOURCES ; ACTIVE SCHEDULES ; SHIFT ; ITERATIVE IMPROVEMENT ; Projektmanagement ; Scheduling-Verfahren ; Theorie

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Schirmer, Andreas
• Ereignis: Veröffentlichung
• (wer): Universität Kiel, Institut für Betriebswirtschaftslehre ; ZBW – Leibniz Information Centre for Economics
• (wo): Kiel
• (wann): 1999

Weitere Informationen

• Handle: http://hdl.handle.net/10419/147589
• Letzte Aktualisierung: 10.03.2025, 11:42 MEZ