Evolutionary algorithms applied to project scheduling problems—a survey of the state-of-the-art
- 15 January 2007
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 45 (2) , 425-450
Abstract
Evolutionary algorithms, a form of meta-heuristic, have been successfully applied to a number of classes of complex combinatorial problems such as the well-studied travelling salesman problem, bin packing problems, etc. They have provided a method other than an exact solution that will, within a reasonable execution time, provide either optimal or near optimal results. In many cases near optimal results are acceptable and the additional resources that may be required to provide exact optimal results prove uneconomical. The class of project scheduling problems (PSP) exhibit a similar type of complexity to the previous mentioned problems, also being NP-hard, and therefore would benefit from solution via meta-heuristic rather than exhaustive search. Improvement to a project schedule in terms of total duration or resource utilisation can be of major financial advantage and therefore near optimal solution via evolutionary techniques should be considered highly applicable. In preparation for further research this paper reviews the application of evolutionary algorithms to the PSP to date extending previous reviews in this area by also encompassing the study of PSP using the design structure matrix. In order to better examine the coverage of this research, this paper also utilises the PSP classification system proposed by (Herroelen, W., Demeulemeester, E. and de Reyck, B., A note on the paper ‘Resource-constrained project scheduling: notation, classification, models and methods’ by Brucker et al ., Euro. J. Op. Res., 2001, 128, 679–688.) to identify the problems being studied in each application and to identify the areas lacking in research. The paper concludes with an examination of areas that in the opinion of the authors would particularly benefit from further research.Keywords
This publication has 33 references indexed in Scilit:
- A hybrid scatter search/electromagnetism meta-heuristic for project schedulingEuropean Journal of Operational Research, 2006
- Efficient Process OptimizationConcurrent Engineering, 2003
- An evolutionary algorithm for resource-constrained project schedulingIEEE Transactions on Evolutionary Computation, 2002
- Ant colony optimization for resource-constrained project schedulingIEEE Transactions on Evolutionary Computation, 2002
- A self‐adapting genetic algorithm for project scheduling under resource constraintsNaval Research Logistics (NRL), 2002
- A note on the paper “Resource-constrained project scheduling: Notation, classification, models and methods” by Brucker et al.European Journal of Operational Research, 2001
- Parameter control in evolutionary algorithmsIEEE Transactions on Evolutionary Computation, 1999
- A genetic algorithm for multi-mode resource constrained project scheduling problemEuropean Journal of Operational Research, 1997
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSPEvolutionary Computation, 1993