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.