点击次数：

论文类型：期刊论文

发表时间：2011-05-01

发表刊物：International Journal of Advancements in Computing Technology

收录刊物：EI、Scopus

卷号：3

期号：4

页面范围：79-88

ISSN号：20058039

摘要：In this paper, a hybrid particle swarm algorithm is proposed to minimize the makespan of job-shop scheduling problem which is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. The new algorithm is based on the principle of particle swarm optimization (PSO). PSO as an evolutionary algorithm, it combines coarse global search capability (by neighboring experience) and local search ability. Simulated annealing (SA) as a neighborhood search algorithms, it has strong local search ability and can employ certain probability and can to avoid becoming trapped in a local optimum. Three neighborhood SA algorithms is designed and combined with PSO(called HPSO), for each best solution that particle find, SA is performed on it to find it's best neighbor solution. The effectiveness and efficiency of HPSO are demonstrated by applying it to 43 benchmark job-shop scheduling problems. Comparison with other researcher's results indicates that HPSO is a viable and effective approach for the job-shop scheduling problem.