Improved crossover and mutation operators for Genetic-Algorithm project scheduling

摘要

In Genetic Algorithms (GAs) technique, offspring chromosomes are created by merging two parent chromosomes using a crossover operator or modifying an existing chromosome using a mutation operator. However, in scheduling problems in which the genes represent activities' start times, the crossover and mutation operators may cause violation of the precedence relationships in the offspring chromosomes. This paper proposes improved crossover and mutation algorithms to directly devise feasible offspring chromosomes. The proposed algorithms employed the traditional Free Float (FF) and a newly-introduced Backward Free Float (BFF). The obtained results exhibited robustness of the proposed algorithms to reduce the computational costs, and high effectiveness to search for optimal solutions. Moreover, validation was performed by comparing the results against the exact solutions obtained by the Integer Programming (IP) technique.