A heuristic for nesting problems of irregular shapes

作者：Lee Wen Chen^*; Ma Heng; Cheng Bor Wen

来源：Computer-Aided Design, 2008, 40(5): 625-633.

DOI：10.1016/j.cad.2008.02.008

• nesting
• stock cutting
• material utilization
• pattern layout

Layout hits a close relationship with product cost in the vein of how to most efficiently cut product patterns from raw materials. This is the so-called "nesting problem", which occurs frequently in sheet metal and furniture industries, wherein material utilization needs to be maximized. In this paper, a quick location and movement (QLM) algorithm is proposed to solve the situation of irregular shapes nested on multiple irregular sheets. This approach includes two major parts: it first approximates irregular shapes to a polygon with the use of a cluster of straight lines, and second, it arranges the approximated shapes one-by-one with the proposed step-by-step rule. Finally, this study investigates and compares examples presented by other authors. The results show that the QLM algorithm takes less time to calculate a layout and the material utilization efficiency is higher compared to other methods.

• 出版日期2008-5