Heuristic methods for nesting problems with plate reuse

• Grant number: 24/02631-2
• Support Opportunities: Scholarships in Brazil - Master
• Start date: July 01, 2024
• Status: Discontinued
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marina Andretta
• Grantee: Walison Adrian de Oliveira
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM
• Associated scholarship(s): 24/18303-4 - Solution methods for the ornamental stone cutting problem with scrap reuse, BE.EP.MS

Abstract

Irregular cutting problems (or nesting problems) are problems that aim to determine an optimal arrangement of smaller irregular objects (items) inside larger objects (containers) in order to meet a demand. We are particularly interested in the problem of cutting irregular items on reused sheets, in which we have various rectangular and irregular sheets (derived from previous cuts), each with fixed sizes, and we aim to allocate all items onto these sheets without overlaps, minimizing sheet waste. This problem arises in various industries such as woodworking, steelmaking, or textiles, where irregular items are cut from rectangular sheets as per customer requests. In some cases, items can be freely rotated (steel industry), while in others, rotations are not allowed (textile industry). Since there is often leftover material after cutting on a new sheet, the idea is to reuse this material in future cuts. In other words, when deciding which sheets to use for cutting items from an order, we can utilize both new sheets and those leftover from previous cuts. The objective of this project is to develop a heuristic method to solve this problem. We will mathematically model it as a mixed-integer nonlinear optimization problem (nonlinear in the case of free rotations), defining suitable objective function and constraints. Given that this is an NP-hard problem, we will solve it using a heuristic method, which will be implemented and tested. Instances from the literature will be used (adapted, if necessary), and results will be as much as possible compared to those in the literature.