Xia Weijun

Wu Zhiming

Zhang Wei

          Yang Genke

Department of Automation,

Shanghai Jiaotong University,

Shanghai 200030, China

OPTIMIZATION TO JOB-SHOP

Abstract: A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Com-paring results indicate that PSO-based algorithm is a viable and effective approach for the job-shop scheduling problem.

Key words: Job-shop scheduling problem  Particle swarm optimization  Simulated annealing Hybrid optimization algorithm