Research On Multi-Objective Flexible Job Shop Scheduling Problem Based On Improved Backtracking Search Algorithm

Job Shop Scheduling Problem(JSP)has become one of the most crucial problems in the field of Scheduling.Because of its complexity and pragmatic application performance,the goal of Flexible Job-shop Scheduling Problem was to minimize the time required to complete all tasks.Compared with many Scheduling problems in the real world,the research on Multi-Objective Flexible Job-shop Scheduling Problem(MO-FJSP)usually involves simultaneous optimization of multiple goals which conflict to certain extent.Therefore,MO-FJSP may be closer to the actual production environment and should be given enough attention and in-depth research.With the arrival of green manufacturing,it is very important to consider the target of energy consumption in scheduling problem,which has become a hot research field.Therefore,the mathematical model for FJSP is established and solved to minimize the maximum completion time,total machine load and total energy consumption.Backtracking Search Algorithm(BSA)is a dual-population Algorithm considering the old and the new population to guide the evolution of the new population.The traditional backtracking search algorithm has some shortcomings,such as weak discretization,premature convergence and limited local search ability.To solve these problems,this paper applies the Backtracking Search Algorithm to MO-FJSP,and proposes an Improved Pareto ordering Backtracking Search Algorithm(IBSA).Then the mutation operation is dynamically controlled by changing the individual search amplitude factor to widen the search direction and prevent the population from falling into local optimum in the process of iteration.Because the backtracking search algorithm uses the old population to provide the direction for the search process,which results in the weakening of the later search ability and the limitation of the local search ability,by combining individual guidance with random number perturbation.A new crossover operator is proposed to improve the ability of later optimization and prevent the algorithm from premature convergence.Finally,a reception criterion is proposed to further enhance the convergence ability of the algorithm.In order to verify the solvation of the Algorithm,a series of benchmark examples,such as Kacem and Brandimarte,are used to simulate the proposed algorithm,compared with the simulation results of other algorithms in the literature.The results show that the improved algorithm has superior performance.