A Hybrid Discrete Particle Swarm Optimization for Job Shop Scheduling

Author

Wang, Wanliang ; Zhang, Jing ; Xu, Xinli ; Jie, Jing ; Wang, Haiyan

Author_Institution

Coll. of Comput. Sci. & Technol., Zhejiang Univ. of Technol., Hangzhou, China

fYear

2010

fDate

26-28 Sept. 2010

Firstpage

303

Lastpage

306

Abstract

The job shop scheduling problem (JSSP) is a well known NP-hard problem, and many algorithms have been presented to solve it, but the results are still unsatisfactory. In this paper, a hybrid discrete particle swarm optimization algorithm based on a two layer population structure is proposed to solve the JSSP, meanwhile add an improved simulated annealing algorithm to increase the ability of finding the global optimum solutions. The experimental results illustrate the high effectiveness of the proposed method, which can avoid prematurity efficiently and be more robust than the PSO and DPSO.

Keywords

computational complexity; job shop scheduling; particle swarm optimisation; simulated annealing; NP-hard problem; global optimum solutions; hybrid discrete particle swarm optimization; job shop scheduling problem; simulated annealing algorithm; two layer population structure; Algorithm design and analysis; Benchmark testing; Job shop scheduling; Particle swarm optimization; Processor scheduling; Simulated annealing; component; job shop scheduling; makespan; particle swarm algorithm; simulated annealing algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Aspects of Social Networks (CASoN), 2010 International Conference on

Conference_Location

Taiyuan

Print_ISBN

978-1-4244-8785-1

Type

conf

DOI

10.1109/CASoN.2010.74

Filename

5636711