Chinese Journal of Computers   Full Text
Title	A Self-Adaptive Hybrid Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem
Authors	ZHANG Chang-Sheng1) SUN Ji-Gui2) OUYANG Dan-Tong2) ZHANG Yong-Gang2)
Address	1)(School of Information Science and Engineering, Northeastern University, Shenyang 110004) 2)(Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, College of Computer Science & Technology, Jilin University, Changchun 130012)
Year	2009
Issue	No.11(2137—2146)
Abstract &   Background	Abstract 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. Keywords particle swarm optimization; flow shop scheduling; particle similarity; particle energy; greedy strategy Background The scheduling problems is a kind of important optimization problems in real life which is NP-hard and difficult to find a satisfying solution within a limited time. How to get the best or a satisfying solution quickly has great significance for improving productivity and the development of society. The traditional optimization algorithms have many advantages such as good computing efficiency, strong soundness and mature property, but they all have insurmountable limitation that it is difficult or impossible to find the exactly or even approximately best solution for a complex system. The presentation of evolutionary algorithm gives a new idea for solving complex optimization problems. It has been adopted by many research fields because of its intelligence, universality, stability, essential parallelism and global search ability. Many researchers in our country have put forward lots of optimization algorithms in which the particle swarm optimization algorithm is newer and preferable. It has been applied to many project practice problems and can get very good optimization effects. For many years the main focus of research was on the application of single metaheuristics to given problems. In recent years, it has become evident that the concentration on a sole metaheuristic is rather restrictive. A skilled combination of concepts of different metaheuristics, called hybrid metaheuristic, can provide a more efficient behavior and a higher flexibility when dealing with real-world and large-scale problems. In this work, the authors combined the generic operations with the particle swarm optimization algorithm and propose algorithm for the flow shop scheduling problem with single objective. Based on the analysis for the algorithm, its effectivenesses are validated by the comparisons with other existing algorithms on benchmarks with different scale and difficulties. Hybrid metaheuristic is a new research area and currently enjoys an increasing interest in the optimization community since the special issue “Hybrid Metaheuristics” of International Journal of Mathematical Modelling and Algorithms was published in 2005. The design and implementation of hybrid metaheuristics rise problems going beyond questions about the design of a single metaheuristic. Choice and tuning of parameters is for example enlarged by the problem of how to achieve a proper interaction of different algorithm components. Interaction can take place at low-level, using functions from different metaheuristics, but also at high-level, e.g., using a portfolio of metaheuristics for automated hybridization. However, the field of hybrid metaheuristics is still in its early days. Many approaches are pre-mature and a substantial amount of further research is necessary in order to develop clearly structured hybrid metaheuristics that can be generally used for optimization. So, this work in this paper will enrich and push forward the studies of the related areas in both theoretical and technological aspects.