Solution methods for the ornamental stone cutting problem with scrap reuse

• Grant number: 24/18303-4
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: May 04, 2025
• End date: November 03, 2025
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marina Andretta
• Grantee: Walison Adrian de Oliveira
• Supervisor: Maria Antonia da Silva Lopes e Carravilla
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Institution abroad: Universidade do Porto (UP), Portugal
• Associated to the scholarship: 24/02631-2 - Heuristic methods for nesting problems with plate reuse, BP.MS

Abstract

Rectangular cutting problems focus on determining an optimal arrangement of smaller rectangular objects (items) within larger objects (slabs) to meet specific demands. This research particularly addresses the cutting problem with slab reuse, involving several rectangular slabs of fixed sizes, some new and others from previous cuts. The goal is to allocate all items onto these slabs without overlap while minimizing material waste. This issue is prevalent in various industries, with a primary focus on the ornamental stone industry, which cuts rectangular pieces from large slabs to fulfill customer orders. In certain cases, depending on the stone type, pieces may have fixed rotations. When materials are leftover after cutting a new slab, the aim is to reuse these scraps in future cuts. Thus, when deciding on which slabs to cut for an order, both new slabs and those from previous cuts can be utilized. This project aims to develop a heuristic method to solve this problem, mathematically modeling it as a mixed-integer optimization problem with a defined objective function and appropriate constraints. Given that this is an NP-hard problem, we will employ a heuristic method to tackle it, which will be implemented and tested with real instances.