Cellular Particle Swarm Optimization And Its Applications On Flexible Job Shop Scheduling Problem

Optimization technique is a kind of application technology based on mathematics, aiming to solve engineering problems and provide the optimal solution or satisfactory solution. When solving real-world engineering problems, characteristics such as multivariable, nonlinear, multiparameter, and multiconstraint of problems make optimization a very challenging research direction. Particle Swarm Optimization algorithm (PSO), a emerging intelligent optimization algorithm based on swarm intelligence theory, uses the cooperation and competition within the individuals of a biological swarm to guide the search. And it arouses wide academic attentions due to its simple principle, few parameters and fast convergence speed.Firstly, the basic PSO algorithm is introduced, and its developments and applications are summarized. Secondly, PSO is analyzed from the view of CA, and the general framework of Cellular Particle Swarm Optimization is proposed. According to the information exchange mechanism of CA, CPSO-inner and CPSO-outer are designed. Then, mathematical justification is conducted to analyze the convergence of CPSO-inner and CPSO-outer. In the following, the behaviors of a particle in CPSO-inner and CPSO-outer are discussed by presenting the trajectories of particles.Thirdly, in order to verify the effectiveness of the proposed algorithms, nine representative variants of PSO are selected to conduct the comparison on thirty famous benchmark problems. The experimental results show the effectiveness of the two proposed algorithms, especially CPSO-outer, which outperforms other variants of PSO on most of problems.Next, CPSO is extended to a discrete version to better suit for Flexible Job Shop Scheduling Problem (FJSP), and an effective encoding method is adopted. In this algorithm, an effective neighborhood function is designed based on tabu search. The experimental results of benchmark problems for FJSP show that the proposed algorithm could effectively solve FJSP.Finally, the research in the dissertation is summarized, and the further research direction of CPSO is discussed.