Multi-Workshop Flexible Scheduling Optimization Based On Hybrid Evolutionary Algorithm

In recent years,the flexible job shop scheduling problem(FJSP)has increasingly become a hotspot in the research field of combinatorial optimization problems.Due to the enormous potential of FJSP in optimizing resources,reducing production costs,and enhancing the core competitiveness of enterprises,how establishing a complete mathematical model and efficient algorithms has become the top priority of theoretical research.This thesis focuses on the problems in distributed shop conditions.In order to improve the efficiency of solving such NP-hard problems,this thesis chooses to leverage the advantages of integrating multiple evolutionary algorithms.This thesis first studies the distributed flexible job shop scheduling problem with sequence-dependent setup time constraints(DFJSP-ST),and proposes a hybrid evolutionary algorithm based on multi-directional and multi-vector independent updates.The main contents are as follows: Firstly,combining particle swarm optimization algorithm and genetic algorithm,using the update method of particle swarm optimization to control three vectors to update independently,and using the crossover and mutation operators of genetic algorithm to update particles.The second is to use a multi-directional update strategy to partition particles based on their dominant direction,facilitating the guidance of particles towards multiple directions on the Pareto front.Third,the coding initialization process is optimized for different vectors.In terms of decoding,a decoding strategy based on the operation left shift is used to reduce the setup time and improve the quality of the solution by adjusting the operation processing order.Experimental results show that the proposed algorithm has good convergence and distribution.Secondly,the distributed flexible job shop scheduling problem with sequence-dependent setup and transfer time(DFJSP-ST-TT)is studied,and a hybrid evolutionary algorithm with local search is proposed.The main contents are as follows: First,in the distributed shop studied,each job is allowed to transfer at most once,and the shop-dependent vector has changed from job-based selection to operation-based selection.The second is to propose a local search strategy to optimize the latter half of the search process,increasing the diversity of solutions,guiding particles to escape out of the local optimum,and further improving distribution performance.The third is to continue to use the multi-directional update strategy and multivector independent update strategy proposed in the previous section to guide convergence and distribution of particles.It is experimentally shown that the hybrid evolutionary algorithm with the local search can enhance the distribution performance while ensuring the convergence performance.Finally,the hybrid evolutionary optimization algorithm proposed in this thesis integrates the advantages of multi-algorithms and designs a multi-directional update strategy that can improve the convergence performance of particles in multiple directions at the Pareto front surface.The corresponding encoding,decoding,and initialization strategies are designed according to the characteristics of each sub-problem.And the vector update operation operator is designed according to the coding structure.After experimental verification,the methods and strategies proposed in this thesis can better handle distributed flexible job shop scheduling problems with multiple constraints,and provide more inspiration and suggestions for solving other complex multi-objective optimization problems.