Abstract: In this paper, a combined evolutionary programming (SAEP) with simulated annealing is presented to solve Job-shop scheduling problem. Two different selected methods between SAEP and EP and their mutation operators are discussed, and simulation results are given to illustrate the efficiency of the presented algorithm, and a comparison between the two algorithms is also presented.