Research Of Block-based Two-stage Evolutionary Algorithm In Multi-objective Flow Shop Scheduling Problem

The multi-objective flow shop scheduling problem is a wide combinatorial optimization problem in actual production activities.Different from the single-objective shop scheduling problem,multi-objective needs to consider two or more targets at the same time to optimize the overall,which greatly increases the difficulty of the problem and makes the solving process more complicated.At present,there are many algorithms to solve multi-objective flow shop scheduling problems,but many algorithms often have more limitations when solving large-scale complex problems.The Two Phase Sub Population Genetic Algorithm has great advantages in the diversity of solutions,and the quality of the solution needs to be further improved.The decomposition-based multi-objective genetic algorithm has insufficient diversity in the solution due to the constant population size and weight vector.Aiming at the two goals of minimizing total completion time and minimizing maximum total time for flow shop scheduling,this paper proposes an Block-based Two Phase Evolutionary Algorithm to solve production scheduling optimization problems.The algorithm is divided into two stages.In the first stage,the population is divided into several sub-groups,and the weights of each sub-group are assigned.In the second stage,the sub-groups are recombined into one large group,and the Multi-Objective Genetic Algorithm based on Decomposition is introduced.The Tchebycheff decomposition strategy is for group decomposition.The evolutionary mechanism of the algorithm is to generate better offspring through several generations of traditional genetic calculations.The ant information density is used to establish the position pheromone matrix and the dependent pheromone matrix for the children,and the blocks are mined according to the two matrix mining blocks.Blocks recombination forms an artificial chromosome.Finally,the chromosomes are recombined to improve the quality of the chromosomes,and the binary competition method is used to select.In order to compare the performance of the algorithm,various algorithms such as BTPEA,TPSPGA,MOGA/D,NSGA-II,and SPEA-II were tested using the Taillard standard example.In the distribution of solutions,the value of BTPEA is at the bottom left of the graph,that is,they have achieved a better solution.In the D1_R value,BTPEA achieved the lowest value,indicating that the algorithm has a better solution effect on the diversity and convergence of the solution.In the C,the value of C(A,x)is equal to 1 or slightly less than 1(A represents BTPEA,X represents other algorithms),which proves that the quality of the solution obtained by the algorithm is higher.The running time of BTPEA is significantly lower than other algorithms in terms of computer runingtime.