A Hybrid Scatter Search / Electromagnetism Meta-Heuristic for Project Scheduling

D. Debels (), B. de Reyck, R. Leus and Mario Vanhoucke

Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration

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. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory, hereafter referred to as the electromagnetism meta-heuristic. We present computational experiments on standard benchmark datasets, compare the results with current state-ofthe- 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.

Keywords: project scheduling; heuristics; scatter search; electromagnetism (search for similar items in EconPapers)
Pages: 26 pages
Date: 2004-03
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://wps-feb.ugent.be/Papers/wp_04_237.pdf (application/pdf)

Related works:
Journal Article: A hybrid scatter search/electromagnetism meta-heuristic for project scheduling (2006)
Working Paper: A hybrid scatter search / electromagnetism meta-heuristic for project scheduling (2003)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:rug:rugwps:04/237

Access Statistics for this paper

More papers in Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration Contact information at EDIRC.
Bibliographic data for series maintained by Nathalie Verhaeghe ().