A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem

Dieter Debels () and Mario Vanhoucke
Additional contact information
Dieter Debels: Faculty of Economics and Business Administration, Ghent University, Ghent, Belgium

Operations Research, 2007, vol. 55, issue 3, 457-469

Abstract: In the last few decades, the resource-constrained project-scheduling problem has become a popular problem type in operations research. However, due to its strongly NP-hard status, the effectiveness of exact optimisation procedures is restricted to relatively small instances. In this paper, we present a new genetic algorithm (GA) for this problem that is able to provide near-optimal heuristic solutions. This GA procedure has been extended by a so-called decomposition-based genetic algorithm (DBGA) that iteratively solves subparts of the project. We present computational experiments on two data sets. The first benchmark set is used to illustrate the performance of both the GA and the DBGA. The second set is used to compare the results with current state-of-the-art heuristics and to show that the procedure is capable of producing consistently good results for challenging problem instances. We illustrate that the GA outperforms all state-of-the-art heuristics and that the DBGA further improves the performance of the GA.

Keywords: production/scheduling; approximations/heuristic; project management; resource constraints (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0358 (application/pdf)

Related works:
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:inm:oropre:v:55:y:2007:i:3:p:457-469

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().