Analysis And Implementation On Parallel Particle Swarm Algorithm For Multi-objective Flexible Scheduling Problem

Multi-objective particle swarm optimization (MOPSO) algorithm is one of the swarm intelligence optimization algorithms. According to the difference of external archive maintained strategies, global best position selection methods and its best position updating methods, etc., multi-objective particle swarm optimization algorithm forms different branches. The classical multi-objective particle swarm optimization algorithms include the CMOPSO algorithm, the MOCLPSO algorithm, the PAMOPSO algorithm etc. By analyzing the particle velocity and position update method, this paper implements the three classical multi-objective particle swarm optimization algorithms, and analyzes the advantage and disadvantage of the three PSO algorithms by means of the different test functions according to convergence and diversity. Experimental results show the MOCLPSO algorithm performs better in terms of diversity, and the PAMOPSO algorithm performs better in terms of convergence.The appearance of computer graphics processor GPU and parallel programming platform CUDA further promote the development of parallel particle swarm optimization algorithm. This paper implements the basic PSO algorithms based on CUDA platform. With other identical conditions, the basic PSO algorithm on the GPU operates faster than that on the CPU but both are basically same in convergence; By fixing the number of dimensions and changing the number of particles, the running time and the rate of speed of the basic PSO algorithm increases with the number of swarm; By fixing the number of particles and changing the number of dimensions, the running time of the basic PSO algorithm increases with the number of dimensions, but the rate of speed is almost unchanged. In the case of the number of particles and the number of dimensions are fixed, the more complex the test functions of the basic PSO algorithm, the higher the rate of speed.Multi-objective flexible job scheduling problem is that when parallel machines and multifunction machines coexist in the workshop, each process of jobs are legitimately arranged in the machines in order to determine the start time of each process, and optimizes the given multiple performance indicators. On the basis of implementations of the MOPSO and PSO algorithms based on the CUDA platform, aimed to decrease the manufacturing cycle, the machine total load and critical machine load, the paper combines GPU parallel multi-objective particle swarm optimization (MOPSO) algorithm and simulated annealing (SA) algorithm to solve multi-objective flexible shop scheduling problems. In the implementation of the algorithm, the MOPSO sub-algorithm is mainly used to allocate the appropriate machines for each process, and the SA sub-algorithm, as a nested subroutine in the PSO algorithm, carries particles fitness evaluation and locally optimizes the sorting process of all machines. This paper first conducts the coding design, the parameter settings and the fitness function selection, and then computes the optimal solution of the external archives as the output according to the weight function. The experimental results of the parallel hybrid algorithm are compared with that of the temporal decomposition (TD) algorithm and the classical genetic (GA) algorithm. The comparison results show that the parallel hybrid algorithm is better in both of scheduling optimization and the time complexity.