Research On Cutting And Packing Problem Based On Memetic Algorithm

Nowadays，green manufacturing and energy-saving technology has become one of thekey issues of the manufacturing industry. As a key technology to reduce energyconsumption and improve materials utilization, two-dimensional cutting and packingtechnology has been becoming the important research focus in academia and industry, andwidely used in the processing of machinery manufacturing, ship equipment and tailoring.Research on the method of two dimensional cutting and packing is the key to improve theprocessing efficiency of complex parts and the utilization of plate. In this thesis, theoptimization methods, namely rectangular packing, irregular packing and cutting pathplanning are studied from a systematic viewpoint. The main researches are organized asfollows.The theoretical basis and solving framework of cutting and packing problem are studied,followed by the description of the concept of cutting and packing problem, Themathematical models of the two problems are established, and the optimization methodand the framework of general solution based on Memetic algorithm is discussed.Algorithms in rectangular packing problem are studied. For the characteristics at rightangles to the emission of the rectangular pieces, a placement policy of bottom left corneroccupying (BLCO) is developed. An improved priority operation crossover operator IPOXis constructed based on improved crossover operation between individuals. By using themixed ideas of global random search and local focus search from Memetic algorithm, thehybrid algorithm HGASA based on genetic algorithm and simulated annealing algorithmis proposed.Algorithms in irregular packing problem are studied. For the diversity of the shape andthe arbitrary nature of the rotation angle of the shaped pieces, the geometric calculationmethods based on the no fit polygon (NFP) are studied, followed by the changes ofrotation angle based on the rotation matrix. The positioning strategy of shaped piecesbased on the bottom left fit is proposed, and the focus search mechanism of tabu search is strengthened. Then the hybrid algorithm HGATS based on genetic algorithm and tabusearch algorithm is proposed.Optimization methods in cutting path planning are studied. In the optimization processof selecting cutting starting point, the contour feature point is analyzed to extract the initialcutting starting point from the recent feature points to the origin, in which the hillclimbing algorithm is used to find the better solution of the surrounding neighbors. In theoptimization process of sorting cutting order, as it as the TSP problem, the ant colonyalgorithm is used to solve this problem. Then the hybrid algorithm HACHC based on antcolony algorithm and hill climbing algorithm for the two problems is proposed.SmartNest software with independent intellectual property rights is developed based onthree kinds of hybrid intelligent algorithm, namely HGASA, HGATS and HACHC.Combined with the typical enterprise production instance, the general solutions framework,software system framework, main function module and flow chart of automatic cuttingand packing are presented, and the functions of three new hybirid algorithms are alsoachieved in this software. Compared with the three types of international famous nestingsoftware, the satisfactory result from SmartNest in the steel plate length and materialutilization is achieved.