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

Dieter Debels, Bert de Reyck, Roel Leus and Mario Vanhoucke

Vlerick Leuven Gent Management School Working Paper Series from Vlerick Leuven Gent Management School

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-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.

Keywords: project scheduling; heuristics; scatter search; electromagnetism (search for similar items in EconPapers)
Pages: 30 pages
Date: 2003-09-24
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.vlerick.be/en/5595-VLK/version/default/ ... vlgms-wp-2003-25.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.vlerick.be/en/5595-VLK/version/default/part/AttachmentData/data/vlgms-wp-2003-25.pdf [301 Moved Permanently]--> https://www.vlerick.com/en/5595-VLK/version/default/part/AttachmentData/data/vlgms-wp-2003-25.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 (2004)
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:vlg:vlgwps:2003-25

Access Statistics for this paper

More papers in Vlerick Leuven Gent Management School Working Paper Series from Vlerick Leuven Gent Management School Contact information at EDIRC.
Bibliographic data for series maintained by Isabelle Vandenbroere ().