Application And Research Of Block Model-based Evolutionary Algorithm On Flow Shop Scheduling Problem

Flow-shop production model has been widely used in the modern manufacturing enterprises,it is a common type of scheduling problem,and it is an important issue in the workshop scheduling research.The goal of the scheduling is to arrange the order of jobs according to the constraints in a reasonable order to meet the performance goals.In actual production,a good scheduling of workpieces can ensure the orderly and steady progress of production activities,improve the utilization of resources and shorten the delivery period,which has important theoretical and practical significance for the development of enterprises.In theory research level,such problem is a classical NP-hard combinatorial optimization problem,and effective solution has strong guiding significance for solving other types of combinatorial optimization problems.Common algorithms for solving the shop scheduling problem such as genetic algorithm,its evolutionary mechanism of selection and crossover operation mixed the excellent gene of mother generation,which makes it difficult for offspring to have different genetic structure,resulting in falling into the local optimum,which is also common to many algorithms.The advantages and disadvantages of the algorithm lies in two aspects: search and convergence.This research proposes a block model-based evolutionary algorithm(BMEA)for permutation flow-shop scheduling problem(PFSP).To take into account the quality and diversity of the initial solution of the algorithm,the initial solution is generated by using the NEH(Nawaz-Enscore-Ham)heuristic and OBL(Opposition-based learning);In order to reduce the search dimension of the problem and improve the search efficiency of the algorithm,two kinds of blockchain structures are constructed: continuous blockchain and discontinuous blockchain.The continuous blockchain is build with the position matrix model which contain the location information of the job.The discontinuous blockchain is constructed by mining different good genes based on association rules.In order to achieve fast convergence,the early evolution of the algorithm mainly use the discontinuous blockchain structure to generate offspring.In the late evolution stage,the algorithm introduces the migratory operator of biogeography algorithm,for the problem of premature convergence in the late evolution stage,two kinds of continuous blockchain are used to generate offspring with mobility to increase the population diversity in order to jump out of the local optimal.In order to further improve the ability of searching algorithm,two local search strategies is proposed to segment and recombine chromosomes: Probability-based recombination and NEH-based recombination strategies,together with adjacent exchange methods to achieve fast convergence.This research validates the effectiveness of BMEA by simulating Taillard and Reeves examples in OR-Library and comparing it with other well-known algorithms.The fast convergence of the algorithm is mainly attributed to the implementation of efficient local search strategy and the injection of discontinuous blockchain structure,and the application of migration operators to update the population increases the diversity of population search,so that the population quickly jump out of the local optimum.The computational experiment on different benchmark suites in PFSP,the proposed BMEA has a high convergence speed and a better solution quality.