Abstract: According to the features of permutation flow-shop problem and the premature defect of GA，an improved GA for this problem is proposed.In the process of proposed GA，the NEH and the Palmer heuristics are used to initialize the population to improve the quality of the initial solutions，the Metropolis rule is employed in chromosome selection for avoiding fall into local optimum，and the tabu-search algorithm is embedded to get away from circuitous search.In order to save the genetic information of excellent chromosomes，an “elite mechanism” is presented to remember good genes，and the best solutions will be saved in each run.The auto-adaptive termination rule is suggested to further improve solution quality.At last，the effectiveness of the improved GA is verified based on some benchmark problems.The results show that the solution quality and the convergence speed are better than the NEH and original GA initialized by heuristic algorithm.