Paper Info
Title
A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem
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.
Year
DOI
Venue
2007
10.1287/opre.1060.0358
Operations Research
Keywords
Field
DocType
benchmark set,exact optimisation procedure,current state-of-the-art heuristics,problem instance,new genetic algorithm,ga procedure,so-called decomposition-based genetic algorithm,resource-constrained project-scheduling problem,decomposition-based genetic algorithm,popular problem type,project management,production scheduling
Resource management,Constraint satisfaction,Mathematical optimization,Heuristic,Computer science,Scheduling (computing),Scheduling (production processes),Heuristics,Genetic algorithm,Operations management,Project management
Journal
Volume
Issue
ISSN
55
3
0030-364X
Citations 
PageRank 
References 
55
1.74
16
Authors
2
Name
Order
Citations
PageRank
Dieter Debels12179.98
M Vanhoucke291955.85