Research And Application Of Particle Swarm Optimization In Scheduling Problem

Scheduling is making the plan for the production process, which plays the leading role in the manufacture, transportation and logistics system. Effective scheduling methods can greatly improve the production benefit and utilization factor. The kernel problem of production scheduling is the model and the algorithm, and effective scheduling algorithm is the important part of the scheduling theory. Particle swarm optimization is the evolutionary algorithm based on swarm intelligence and the bionic algorithm that imitates the bird swarm to seek the food. Particle swarm optimization has the obvious computation model, and is easy to be carried out and has good optimization performance. In this paper, research of performance of particle swarm optimization and application in production scheduling and port equipment allocation is invested, and primary contents and results are following.(1) Compassion between evolutionary strategy and particle swarm optimization is analyzed, experimental results which are carried out on the single peak function (two dimensional problem and multidimensional problem) and the multi-peak function show that, particle swarm optimization has better performance than evolutionary strategy.(2) The common flow procedure of particle swarm optimization for the scheduling problem is introduced, and the key problem of the design for the particle representation is analyzed. As for the character of the different scheduling problem, three kinds of particle representations are presented, which include the particle representation based on PPS, the particle representation based on PPR, and the hybrid particle representation based on PPS-PPR. The mapping relation between three kinds of particle representations and solution space of the scheduling and the decoding approaches are pointed out.(3) Three kinds of the particle representations are applied to three kinds of scheduling problems, which include Flow Shop, Job Shop and Parallel Machines Scheduling. The algorithm steps of particle swarm optimization for three kinds of scheduling problems are invested. Many computational results indicate that particle swarm optimization can effectively optimize the above scheduling problems. The particle swarm optimization for flexible job shop scheduling problem is presented, computational results prove that theperformance of PSO for flexible job shop scheduling problem gets ahead of GA and heuristic method.(4) As to permutation flow shop scheduling problem, the particle neighbor structure and the mapping relation with scheduling solution are analyzed. The process is presented that the local search method based on neighbor operation is carried out in the particle swarm optimization. The three kinds of different local search methods based neighbor operation are introduced, which include the method based on interchange operation, the method based on insert operation, and the method based on inverse operation. Computational results prove that the local search methods can preferably improve the performance of particle swarm optimization, and hybrid particle swarm optimization based on the local search method outperforms GA and NEH heuristic method.(5) With regard to permutation flow shop scheduling problem, the different particle swarm models, inertia weight, the particle population, the initialization of the position and velocity, and restriction of the position and the velocity are analyzed.(6) Particle swarm optimization based on three kinds of the particle representations is applied to the practical production scheduling problems, which include the vehicle scheduling problem of logistics distribution system, the automatic warehouse stow crane sorting operation scheduling problem and the port berth allocation problem. Computational results prove that particle swarm optimization based on three kinds of the particle representations can effectively solve the above scheduling problem.(7) In order to study the port equipment allocation problem, the particle swarm optimization and simulation optimization theory are applied to the port tugboat allocation optimization. The discrete event simulation model for the port tugboat operation is given. The port tugboat operation simulation system software based on Visual Basic 6.0 and Access database is programmed. A new particle swarm optimization model with mutation operation is introduced and is applied to the port tugboat allocation simulation optimization. The better tugboat allocation result gained through computation.