A hybrid scatter search/electromagnetism meta-heuristic for project scheduling
AbstractIn 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal European Journal of Operational Research.
Volume (Year): 169 (2006)
Issue (Month): 2 (March)
Contact details of provider:
Web page: http://www.elsevier.com/locate/eor
Other versions of this item:
- Dieter Debels & Bert de Reyck & Roel Leus & Mario Vanhoucke, 2003. "A hybrid scatter search / electromagnetism meta-heuristic for project scheduling," Vlerick Leuven Gent Management School Working Paper Series 2003-25, Vlerick Leuven Gent Management School.
- D. Debels & B. De Reyck & R. Leus & M. Vanhoucke, 2004. "A Hybrid Scatter Search / Electromagnetism Meta-Heuristic for Project Scheduling," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 04/237, Ghent University, Faculty of Economics and Business Administration.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Valls, Vicente & Quintanilla, Sacramento & Ballestin, Francisco, 2003. "Resource-constrained project scheduling: A critical activity reordering heuristic," European Journal of Operational Research, Elsevier, vol. 149(2), pages 282-301, September.
- Hartmann, Sönke & Kolisch, R., 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 11180, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
- Bouleimen, K. & Lecocq, H., 2003. "A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version," European Journal of Operational Research, Elsevier, vol. 149(2), pages 268-281, September.
- Hartmann, Sonke & Kolisch, Rainer, 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 394-407, December.
- Li, K. Y. & Willis, R. J., 1992. "An iterative scheduling technique for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 56(3), pages 370-379, February.
- Taillard, Eric D. & Gambardella, Luca M. & Gendreau, Michel & Potvin, Jean-Yves, 2001. "Adaptive memory programming: A unified view of metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 1-16, November.
- Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
- Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
- Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
- Fleszar, Krzysztof & Hindi, Khalil S., 2004. "Solving the resource-constrained project scheduling problem by a variable neighbourhood search," European Journal of Operational Research, Elsevier, vol. 155(2), pages 402-413, June.
- M. Vanhoucke, 2007. "A genetic algorithm to investigate the trade-off between project lead time and net present value," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/456, Ghent University, Faculty of Economics and Business Administration.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.