A Study in Pairwise Clustering for Bi-dimensional Irregular Strip Packing Using the Dotted Board Model. Issue 11 (2018)

• Record Type: Journal Article
• Authors: Sato, André Kubagawa; Setter Bauab, Guilherme Elias; Martins, Thiago de Castro; Guerra Tsuzuki, Marcos de Sales; Gomes, Antonio Miguel
• Is Part Of: IFAC-PapersOnLine. Volume 51:Issue 11(2018)
• Page Start: 284
• Page End: 289
• Publication Date: 2018
• Subjects: Irregular strip packing -- raster method -- pairwise clustering -- overlap minimization; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2018.08.297
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: The bi-dimensional irregular strip packing is a difficult problem in the cutting and packing field. Its main feature, and central source of complexity, is the irregularity of the shape of the items. Consequently, mathematical solvers are only able to obtain optimal solutions for small instances and heuristics are often employed in the literature. In such algorithms, it is not possible to guarantee that the optimum solution is found. In such cases, a restricted version of the problem can be adopted in order to improve the performance. One possible restriction is the adoption of pairwise clustering, i.e., elimination of items by joining two pieces. In this work, an automatic pairwise clustering method is proposed for the dotted board model, which limits the placement of items to equally distributed discrete points. The clustered problems are then used as input to an irregular strip packing solver. The results obtained in this paper can be used as an initial guideline for the use of clustering in a discrete grid, which was beneficial in some of the tested cases.