Discrete Dynamics in Nature and Society

Journal Menu

Discrete Dynamics in Nature and Society
Volume 2010 (2010), Article ID 838596, 11 pages
doi:10.1155/2010/838596

Research Article

A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan

Zhigang Lian^1,2,3

¹School of Electronic and Information Engineering, Shanghai DianJi University, Shanghai 200240, China
²School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
³Postdoctoral Centre, Jiangnan Shipyard (Group) Co., Ltd. Shanghai, Shanghai 201913, China

Received 5 February 2010; Revised 15 March 2010; Accepted 24 June 2010

Academic Editor: Elena Braverman

Copyright © 2010 Zhigang Lian. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

The Job-shop scheduling problem (JSSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original particle swarm optimization algorithm (OPSOA), generally, is used to solve continuous problems, and rarely to optimize discrete problems such as JSSP. In OPSOA, through research I find that it has a tendency to get stuck in a near optimal solution especially for middle and large size problems. The local and global search combine particle swarm optimization algorithm (LGSCPSOA) is used to solve JSSP, where particle-updating mechanism benefits from the searching experience of one particle itself, the best of all particles in the swarm, and the best of particles in neighborhood population. The new coding method is used in LGSCPSOA to optimize JSSP, and it gets all sequences are feasible solutions. Three representative instances are made computational experiment, and simulation shows that the LGSCPSOA is efficacious for JSSP to minimize makespan.