A self-adaptive hybrid particle swarm optimization algorithm for flow shop scheduling problem

被引：8
作者：
Zhang, Chang-Sheng [1 ]
Sun, Ji-Gui [2 ]
Ouyang, Dan-Tong [2 ]
Zhang, Yong-Gang [2 ]
机构：
[1] School of Information Science and Engineering, Northeastern University
[2] Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science and Technology, Jilin University
来源：
Jisuanji Xuebao/Chinese Journal of Computers | 2009年 / 32卷 / 11期
关键词：
Flow shop scheduling; Greedy strategy; Particle energy; Particle similarity; Particle swarm optimization;
D O I：
10.3724/SP.J.1016.2009.02137
中图分类号：
学科分类号：
摘要：
A hybrid self-adaptive algorithm is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan, which combined the particle swarm optimization algorithm and genetic operators together. The particle similarity and particle energy are defined. The threshold of particle similarity dynamically changes with iterations and the particle energy depends on the swarm evolving degree and the particle's evolving speed. In order to improve the proposed algorithm performance further, a neighborhood based random greedy search strategy is introduced to overcome the shortcoming of evolving slowly in the later running phase. Finally, the proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The result shows that the solution quality and the stability of the HPGA both precede the other two algorithms. It can be used to solve large scale flow shop scheduling problem.
引用
收藏
页码：2137 / 2146
页数：9
相关论文
共 12 条
  • [1] Garey M., Johnson D., Sethy R., The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, 2, pp. 117-129, (1976)
  • [2] Valente J.M.S., Alves R.A.F.S., An exact approach to early/tardy scheduling with release dates, Computers & Operations Research, 32, 11, pp. 2905-2917, (2005)
  • [3] Gangadharan R., Rajendran C., Heuristic algorithms for scheduling in no-wait flowshop, International Journal of Production Economics, 32, 3, pp. 285-90, (1993)
  • [4] Aldowaisan T., Allahverdi A., New heuristics for no-wait flowshops to minimize makespan, Computers and Operations Research, 30, 12, pp. 19-31, (2003)
  • [5] Yang Q.-Y., Sun J.-G., Zhang J.-Y., Et al., A hybrid discrete particle swarm algorithm for open-shop problems, Proceedings of the 6th International Conference on Simulated Evolution and Learning (SEAL 2006), pp. 158-165, (2006)
  • [6] Rameshkumar K., Suresh R.K., Mohanasundaram K.M., Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makspan, Proceedings of the ICNC 2005, pp. 572-581, (2005)
  • [7] Lian Z.-G., Gu X.-S., Jiao B., A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan, Applied Mathematics and Computation, 175, 1, pp. 773-785, (2006)
  • [8] Nearchou A.C., The effect of various operators on the genetic search for large scheduling problems, International Journal Production Economics, 88, 12, pp. 191-203, (2004)
  • [9] Lauriere J.-L., A language and a program for stating and solving combinatorial problems, Artificial Intelligence, 10, 1, pp. 29-127, (1978)
  • [10] van den Bergh F., An analysis of particle swarm optimizers, (2002)
12