Application And Research On Particle Swarm Optimization Algorithm In Flexible Job Shop Scheduling Problems

The traditional job shop scheduling problem is a kind of scheduling problems where each job is processed by a specified machine. But in practice, the job generally can be processed by more than one machine, which brings the flexible job shop scheduling problem.Since flexible job shop scheduling possesses the advantage of route flexibility, it can avoid the problem of jam-up and congestion in the traditional job shop. Meanwhile, the flexible routes can make the system proceed with the exception encountered in the manufacturing procedure such as machine failure. Therefore, the flexible routes are capable of enhancing the agility of the job shop scheduling system. However, this new feature enlarges the range of the available solutions for the flexible job shop scheduling problems and brings new challenges to the given problems. Moreover, making decisions on multiple objectives is often needed when solving and analyzing the flexible job shop scheduling problems in practice. Thus, seeking the effective methods to solve multi-objective flexible job shop scheduling problems is of important theoretical value and practical significance.This dissertation mainly discusses the application of the particle swarm optimization algorithm on flexible job shop scheduling problems, especially the multi-objective flexible job shop scheduling problems. The main and pioneering works of this dissertation are as follows:(1) Research on the particle swarm optimization algorithm based on chaos and its application in flexible job shop scheduling problems. As a new optimization technique, chaos bears randomicity, ergodicity and the superiority of escaping from a local optimum. By integrating the advantage of Chaos optimization and . particle swarm optimization algorithm, a hybrid particle swarm optimization algorithm is proposed. Firstly, parameters of particle swarm optimization algorithm are adaptively chaotic optimized to efficiently balance the exploration and exploitation abilities. Then, during the search process of particle swarm optimization algorithm, the chaotic local optimizer is introduced to raise its resulting precision and convergence rate. The algorithm is applied to solving the single objective and multi-objective flexible job-shop scheduling problems and the global search performance of the new algorithm is validated by the results of the comparative experiments.(2) Discussion of the multi-objective weighting composite optimization with particle swarm optimization algorithm, resulting in a multi-objective hybrid particle swarm optimization algorithm. Based on the combination of particle swarm optimization and chaos, a fitness function with fuzzy logic is proposed to evaluate the particles for the dimension problems of multiple objectives. Meanwhile, the weighting coefficients are randomly generated to further maintain the diversity of the population and find all the non-dominated solutions as more as possible. Experiments on four typical flexible job shop scheduling instances are presented to show the good distribution and stability of the non-dominated solutions found by the proposed approach.(3) Research on the application of the fully-informed particle swarm algorithm in the multi-objective flexible job shop scheduling problems. Firstly, the population is ranked based on Pareto optimal concept. And the neighborhood topology used in the fully-informed particle swarm algorithm is based on the Pareto rank. Secondly, the crowding distance of individuals is computed in the same Pareto level for the secondary rank. Thirdly, addressing the problem of trapping into the local optimal, two mutation operators based on the coding mechanism are introduced into our algorithm.(4) Research on the application of particle swarm optimization algorithm based on the dynamic probabilistic search in the multi-objective flexible job shop scheduling problems. At the earlier stage, the average of the neighboring best individuals instead of the general single one is employed in the algorithm to guide the search. In the latter stage, the next generation individuals' positions are sampled from a Gaussian dynamic probabilistic distribution around the expected position of the particle at the next generation with the purpose of improving the local exploiting ability of our method. Then, borrowing ideas from Pareto optimization, the non-dominated solutions are stored by using an elitism repository, and a new fitness allocation approach is proposed. Meanwhile, the self-adaptive mutation operators are introduced to enhance the diversity of solutions. Finally, comparative experiments are conducted with several groups of flexible job shop scheduling instances. The experimental results show the better search ability of the algorithm, which indicates that the proposed algorithm is feasible in solving multi-objective flexible job shop scheduling problems.