Evolutionary algorithms applied to project scheduling problems - a survey of the state-of-the-art

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.