A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

0.00 Avg rating0 Votes
Article ID: iaor20063272
Country: Netherlands
Volume: 169
Issue: 2
Start Page Number: 638
End Page Number: 653
Publication Date: Mar 2006
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.