A Hybrid Scatter Search / Electromagnetism Meta-Heuristic for Project Scheduling
Debels, Dieter De Reyck, B. Leus, Roel Vanhoucke, Mario
Debels, Dieter
De Reyck, B.
Leus, Roel
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2006
Journal
European Journal of Operational Research
Book
Publication Volume
169
Publication Issue
2
Publication Begin page
638
Publication End page
653
Publication Number of pages
Collections
Abstract
In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.
Research Projects
Organizational Units
Journal Issue
Keywords
Programme & Portfolio Management