Genetic algorithm with pigeon-hole coding scheme for solving sequencing problems

One ofthe major difficulties in applying genetic algorithms in sequencing problems is the production of infeasible sequences by crossover operations. In this article we propose a new coding scheme based on a pigeon-hole idea.The Pigeon-hole coding scheme can guarantee the feasibility ofthe offspring generated by crossover operations. In addition,we adopta Randomized Single-point-Crossover operator and a Modified-Mutation operator in the algorithm,which are more effective as compared with the traditional crossover and mutation operators. Our pigeon-hole-based genetic algorithm is successfully applied in solving two NP-hard sequencing problems.