Meta-heuristic resource-constrained project scheduling: solution space restrictions and neighbourhood extensions

The resource-constrained project scheduling problem (RCPSP) has been extensively investigated during the past decades. Due to its strongly NP-hard status and the need for solving large realistic project instances, the recent focus has shifted from exact optimisation procedures to (meta-) heuristic approaches. In this paper, we extend some existing state-of-the-art RCPSP procedures in two ways. First, we extensively test a decomposition approach that splits problem instances into smaller sub-problems to be solved with an (exact or heuristic) procedure, and re-incorporates the obtained solutions for the sub-problems into the solution of the main problem, possibly leading to an overall better solution. Second, we study the influence of an extended neighbourhood search on the performance of a meta-heuristic procedure. Computational results reveal that both techniques are valuable extensions and lead to improved results. Keywords: Resource-constrained project scheduling; Problem decomposition; Meta-heuristic