Research And Implementation Of Irregular Part Nesting Based On Parallel Genetic Algorithm

The problem of optimization of nesting of two-dimensional irregular parts refers to the discharge of a variety of irregular parts of different sizes on a certain sheet(mostly rectangular shape).The irregular parts must not be overlapped with each other and must not be exceed the sheet boundary as well,to make the utilization rate as large as possible.This problem is widespread in clothing,steel,furniture,glass,machinery manufacturing and other fields,and is closely related to the cost management of the factory.Therefore,the research of this paper has practical application value.The nesting problem is a typical NP-hard problem.There is still no algorithm to find the optimal solution in a short time.Aiming at the difficulties commonly encountered in the current nesting problem,this paper uses a method based on no-fit polygon and parallel genetic algorithms to arrange two-dimensional irregular parts,and implements the program through C++ programming language,Qt framework and Open MP parallel library.The work is as follows:(1)Using the mathematical model of Markov chain to study the genetic algorithm,and briefly proved the convergence of the genetic algorithm,which supplements the theoretical basis of the algorithm,which is the first innovation point of this paper.(2)According to the characteristics of the nesting problem,the nesting data is encoded,and the selection operator,crossover operator and mutation operator are designed.For encoding,decimal encoding is used,which can maximize the original information of the nesting and is easy to program.In terms of operator selection,the method of direct selection is adopted,and the significance of adopting the selection operator is described.In terms of crossover operator,the crossover operator of ordercrossover is used to reduce the amount of calculation as much as possible to save the algorithm time.In terms of mutation operators,mutations are performed on the angles.(3)Programs a nesting test software.According to the large amount of computational problems of the nesting problem,a lightweight model layer of the layout program was designed and programmed.A lightweight library can make the computation of program operations faster.,especially in nesting program.The display of no-fit polygon through GUI interactions helps to study the effect of irregular shape elements on the effect of layout.This is the second innovation point of this paper.In the specific design of the algorithm,through the cache technology to deal with some repeated calculations in each evolving generation, the computation time is greatly reduced,this is the third innovation point of this paper.(4)A comparative test was conducted using some of the benchmark problems provided by the European nesting interest group ESTCUP,and good results were obtained.The utilization ratio of the nesting was comparable to that of the foreign comparison algorithm.The test of some data even better than foreign comparison algorithms.Compared with the domestic literature,the utilization rate of nesting has exceeded the utilization rate of some documents.