To overcome the shortcoming of the genetic algorithm and the tabu search algorithm for solving the job shop scheduling problem, this paper proposes an adaptive genetic tabu algorithm. By adjusting the mutation probability adaptively and putting the tabu search algorithm to the process of the genetic algorithm, the improved genetic tabu algorithm promotes the rate in convergence and avoids such disadvantages as premature convergence. Simulation experiments demonstrate that the proposed improved genetic tabu algorithm is fast in convergence, and it does not get stuck at a local optimum easily.