Research On Improved Genetic Algorithm For Flexible Job Shop Scheduling Problem Based On MPN

HFS(Hybrid Flow Shop)is a mass customization-oriented production organization model MCP(Mass Customization Production).The stage parallel machine included in it allows HFS to be flexible in production and can realize on-demand production and rapid switching of production requirements.In view of the wide range and complexity of HFS applications,its production scheduling problem has always been a hot spot in the research of intelligent manufacturing.At present,to solve the scheduling problem of HFS is to use various algorithms such as mathematical programming and heuristic search to solve the problem based on modeling the real workshop environment.Due to the large scale and many resource constraints of the large-scale hybrid-flow manufacturing system,the disaster of dimension occurs during job scheduling,and the problem of searching and solving is difficult.The Petri Net(Manufacturing Petri Net,MPN)oriented to in telligent objects has better expression and simplification ability;genetic algorithm has better global search ability.The combination of the two has obvious advantages in solving large-scale workshop scheduling problems.In this dissertation,focus on the makespan for such problems,based on the MPN model,an improved genetic algorithm is proposed to solve it.The dissertation first redefines the structure of the chromosome,and uses the chromosome arrangement algorithm to compress the solution space of the problem.Secondly,the particle swarm optimization(PSO)optimization mechanism is used to guide the direction of chromosome optimization in the chromosome crossover operator,and the simulated annealing algorithm(SAA)mechanism is used in the chromoso me mutation operator to prevent the premature convergence of the genetic algorithm.After each population iteration,two different neighborhood searches are performed to explore the potential of the optimal individual and the elite individual,and try to i ncrease the fitness of the individual.The experimental result shows that the improved genetic algorithm has made great improvements in the quality of the solution.The main contents of this dissertation are as follows:(1)The MPN model is used to model the existing real hybrid flow workshop,abstract the real hybrid flow workshop,consider the key points,and then simulate the workshop mechanism,decompress the space of solution,and summarize the constraint relationship of job.(2)First of all,to address the problem of mapping the model scheduling scheme to the chromosome,this dissertation adopts the method of workpiece retelling and optimization goal retelling,and proposes to use a mixed graph model to retell the constraint relationship of workpiece processing in the MPN model and use a schedule table to retell the optimization goal of the MPN model.The model constraints and optimization goals are manifested to provide the basis for chromosome coding.Then,for the problem of chromosome coding,a new chromosome coding structure is adopted to compress and code the mixed graph model information;the schedule table is converted into an adaptive coding method and the MPN machine processing mechanism is added to simplify the coding process to achieve a simple scheduling scheme.Finally,aiming at the problem of a large number of useless solutions due to random production of chromosomes,the method of adjusting chromosome arrangement gene-string based on chromosome selection gene-string is adopted.A chromosome arrangement gene-string optimization algorithm is proposed to adjust the arrangement gene-string with feedback to constrain the generation of chromosomes and realize the compression of the solution space.(3)On the basis of the above-mentioned MPN model construction and chromosome structure construction,in order to solve the problem that genetic algorithm is easy to converge prematurely,this dissertation uses a crossover with particle swarm mechanism added to solve the problem of genetic algorithm that is difficult to converge when dealing with large-scale mixed-flow workshop problems;added mutants of simulated annealing mechanism to prevent premature convergence of genetic algorithms.And the neighborhood search mechanism of elite individuals and o ptimal individuals is added to each iteration of the total group to fully stimulate the potential of individuals.The genetic algorithm improves the effectiveness and convergence of the algorithm by adding the above modules,so that it can solve large-scale mixed-flow workshop scheduling problems.The experimental data shows that the improved genetic algorithm has made great improvements in the optimality of the solution.