Abstract: In this paper, near optimal solutions to scheduling jobs on parallel machines to minimize the total tardiness(p∥T ), which is an NP problem, are addressedby a Genetic Algorithm. It is proved in this paper that the encoding space may be smaller than the solution space for finding an optimal solution in a GA algorithm. Based on this articulation and analysis of properties of thep∥T problem, the encoding space and decoding function are deliberately designed to reduce the searching efforts. Finally, the GA algorithm presented in this paper is compared with some heuristics through numerical examples, and the result shows that the GA algorithm is superior over others methods.