Research Of Two Dimensional Irregular Auto-Nesting Algorithm

In the present manufacturing scenario, cutting of two-dimensional (2-D) shaped parts from 2-D sheets, with a minimum wastage of material, is an important task. The task of arranging the parts on the sheet is known as nesting. This paper studies the two-dimensional irregular auto-nesting problems, and also presents some effective methods to solve the problems.What's the Computer Aided Nesting (CAN) problem? The paper discusses this problem and it's relative research works in chapter 1. The main research aim and our work are also introduced there.In chapter 2, the paper proposes a model and algorithm for blank layout of single pattern in single rectangular sheet. This corresponding algorithm can work out the optimum layout automatically and efficiently.The 2-D irregular nesting problem is discussed in chapter 3, which is known as the NP-hard problem in complexity. In this paper we designed a heuristic approach base on genetic simulated annealing algorithm, which will be introduced in chapter 4, can deal with the problem of packing multiple shaped parts in an irregular sheet without orientation limitation. At the same time, the algorithm also provided a new way to represent the sheet and part geometries, which can be irrespective of the complexity in the geometries. The proposed approach looked for the best sequence of the shaped parts and each part's optimum rotation by the genetic simulated annealing algorithm, and completed packing by the heuristic algorithm with the bottom-left-condition automatically. The algorithm is discussed in detail in this paper.In chapter 4, we introduce the base ideas of Genetic Algorithms (GA) and Simulated Annealing (SA). Father on, a hybrid GA method is proposed to looked for the best sequence of the shaped parts and each part's optimum rotation. In combination with the heuristic location approach proposed in chapter 3, we present an approach for the packing of polygons base on genetic simulated annealing algorithm.Chapter 5 summarizes all achievements of this dissertation, reviews innovation points and defects, and gives the further work in the future.