Pattern nesting on irregular-shaped stock using Genetic Algorithms

• Published in: Engineering applications of artificial intelligence 2002-12, Vol.15 (6), p.551-558
• Main Authors: Tay, Francis E.H., Chong, T.Y., Lee, F.C.
• Format: Article
• Language: English
• Subjects: Boundary; Evolutionary; Genetic Algorithms; Nesting
• ISSN: 0952-1976; 1873-6769
• DOI: 10.1016/S0952-1976(03)00009-5

Pattern nesting aims to position 2-D shapes on a sheet so as to achieve maximum usage of a stock, or equivalently to minimise wastage. There are different methods used on computer to lay out the positions of the shapes on the stock, such as linear programming and heuristic method. A recent approach attempts to use Genetic Algorithms (GAs) to solve the problem of pattern nesting. The successful development of using GAs to nest 2-D shapes on regular-shaped stock has proved the feasibility of using GAs to solve pattern nesting problem. This work presents a new method of solving the pattern nesting problem on irregular-shaped stock using GAs, known as the evolutionary boundary nesting algorithm. This approach further generalises the scope of the pattern nesting problem by allowing nesting on stocks of any shapes and sizes. This implies that the nesting algorithm can be used universally in any industry, such as the garment, shipbuilding and aerospace industry. Basically, the shapes are nested sequentially in the stock and the evolutionary boundary nesting algorithm uses GAs to find the best position to nest each shape along the boundary of the stock.