Volume 42, Number 2, April-June 2008CIRO 05
|Page(s)||215 - 228|
|Published online||17 May 2008|
New representation to reduce the search space for the resource-constrained project scheduling problem
et Recherche Opérationnelle, Université de Montréal, C. P. 6128, Succursale Centre-Ville, Montréal (Québec), H3C 3J7, Canada;
Accepted: 28 November 2007
This paper describes a new representation for the solutions of the resource-constrained project scheduling problem (RCPSP) denoted Activity Set List. The most efficient heuristics for the problem use the activity list representation and the serial SGS method to construct the corresponding solution (schedule). The activity list may induce a search space of representations much larger then the space of schedules because the same schedule can correspond to many different activity list representations. We indicate how the activity set list representation can significantly reduce the search space, and how to move more efficiently through it. Furthermore, this new representation never excludes the optimal solution and it has many interesting properties. An evaluation of the search space reduction induced by this representation is made for the most used library of instances in the literature. The activity set list representation may be used to construct a new category of more efficient solution procedures for the problem.
Mathematics Subject Classification: 90B35
Key words: Project scheduling / Resource-constrained project scheduling / Activity list representation / Activity set list representation / Heuristics and metaheuristics.
© EDP Sciences, ROADEF, SMAI, 2008
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.