Performance testing of rectangular parts-nesting heuristics

Abstract

We compare the performance of a set of rectangular layout heuristics on the basis of their packing densities and time performance, with a view to increase their applicability in manufacturing situations. Among the techniques is a class of heuristics introduced by the authors in an earlier work (Israni And Sanders, 1982). The experimental comparison is made over two attributes defined for the bill of materials; the area and the aspect ratio distributions of the pieces. In addition, some of the heuristics considered permit limited human intervention. Our study shows that the two attributes play a significant part in determining the performance of a heuristic. Length-sorted heuristics are found to perform differently as a class from height-sorted heuristics. The study shows that human intervention, even in limited amounts, usually improves the quality of a solution substantially. The heuristics' worst case time complexities are presented. For certain specific regions of the attributes, the best heuristic has been identified.