A Study in Pairwise Clustering for Bi-dimensional Irregular Strip Packing Using the Dotted Board Model

• Type: Article in International Conference Proceedings Book
• Date: 2018

Authors

André Kubagawa Sato (Author) Other; Guilherme Elias Setter Bauab (Author) Other; Thiago de Castro Martins (Author) Other; Marcos de Sales Guerra Tsuzuki (Author) Other; António Miguel Gomes (Author) FEUP

Conference proceedings International

Title: IFAC PAPERSONLINE

Pages: 284-289

3rd IFAC Conference on Advances in Proportional-Integral-Derivative Control (PID)

Ghent Univ, Ghent, BELGIUM, MAY 09-11, 2018

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 1 Citation

Other information

Authenticus ID: P-00P-M7G

DOI: 10.1016/j.ifacol.2018.08.297

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 6