Abstract: Abstract:A graph model for Job_Shop scheduling is established by describing the scheduling scheme as a weighted directed graph. The validity of scheduling scheme is judged by topological queuing and the key job is extracted based on the key path. The improved genetic algorithm is subsequently presented for Job_Shop scheduling. The chromosome is coded with the constrained planar array and the evaluation function is computed with topological queuing. The operations of crossover and mutation are also directed by the key job. An example is given to demonstrate the proposed algorithm by comparing it with the other genetic algorithms presented in preterit articles.