Genetic Algorithms for Nesting of Rectangular Shapes

Abstract

The problem of placement of a set of 2-D shapes on a large resource while producing a minimal waste is a common resource utilization problem. For example, in sheet metal industry, 2-D patterns are placed on to sheets with finite dimensions. In this case, stock sheets on which the pieces are placed are depleted resources and the materials remaining after placement of pieces (scrap) can not be used for further allocation of pieces. This problem is encountered in every area of industry from design to distribution and sales through various aspects of manufacturing process. Due to high cost, any wastage of material is intolerable during manufacturing. Since the cost of high volume stamped cutout parts is largely dependent on material usage; scrap minimization is a primary goal of design process. Although many factors influence the scrap rate, one of the most critical is the positioning or layout of parts on the stock sheet. In other words, the problems of nesting is to select the optimum arrangement for a combination of 2-D regular/irregular shapes \onto the large stock sheet so as to minimized material waste while taking into consideration the various practical constraints. The constraints of this problem very with the application. These may be the raw material used, design requirements, number of shapes required, manufacturing constraints etc.