This paper presents a tabu search algorithm with varying neighborhood for Job Shop scheduling problem of minimizing the makespan.The neighborhood used can be changed with the process of the algorithm

and the scale of the neighborhood is not only small

but also the reachability can be kept.The computational results of different scale problems show that the efficiency of the algorithm is high

and that the influence of the initial solution on the algorithm is small.