Abstract: The reason why genetic algorithm available exhibits limitations when it is applied to job-shop scheduling problem (JSSP) is analyzed. In this paper, a new particle swarm optimization algorithm is applied to solve the problems in the JSSP. During the running, the mutation probability for the current best particle is determined by two factors: the variance of the popu lation's fitness and the current optimal solution. The ability of particle swarm optimization algorithm(PSO) to break away from the local optimum is greatly improved by the mutation. The results of the example verify its better performance compared with the conventional algorithms.