EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4005. Extreme Points-Based Heuristic for Irregular Panel 2D-Bin Packing with Defects

Invited abstract in session MB-7: Cutting and Packing 2 - 2D irregular, stream Cutting and Packing (ESICUP).

Monday, 10:30-12:00
Room: 1019 (building: 202)

Authors (first author is the speaker)

1. Elsa Silva
Departament of Production and Systems, University of Minho
2. Tiago Silveira
Computer Science, Universidade Federal de Alfenas
3. Maria Antónia Carravilla
INESC TEC, Faculty of Engineering, University of Porto
4. José Fernando Oliveira
INESC TEC, Faculty of Engineering, University of Porto
5. Matheus Campinho
INESC TEC

Abstract

The 2-dimensional Bin Packing Problem addressed in this presentation arises within the ornamental stone industry, where heavy stone panels of irregular shapes, often with defects, must be cut to meet the demand for rectangular items. The cutting process in this industry is subject to practical constraints, primarily influenced by the thickness of the stone panels and the cutting technology employed, resulting in an effect known as overcut. Overcutting involves cutting the raw material beyond the edge of the intended piece. This effect can damage pieces placed on top of the cut unless there is sufficient separation between the pieces or alignment with another cut in the same direction.

To the best of our knowledge, this constraint has never been explicitly addressed in the literature, making it a non-trivial challenge to overcome.

In response to these challenges, a novel approach is proposed. An extreme point-based heuristic has been developed to solve the problem, enhanced by a local search procedure based on the two-exchange heuristic. The irregularity of the panels is managed through a transformation process that converts irregular shapes into regular ones, simplifying the structure. Computational experiments using real-world data have been conducted to validate the effectiveness of the proposed approach, and the results and practical applications are thoroughly discussed.

Keywords

Status: accepted

Back to the list of papers