EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Cutting and Packing
- Combinatorial Optimization
- Practice of OR
Status: accepted
Back to the list of papers