A solution method for the irregular strip-packing problem integrated to the cutting path problem

• Grant number: 21/14949-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: March 01, 2022
• End date: June 30, 2023
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Marina Andretta
• Grantee: Leonardo Trevisan
• 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: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry, AP.CEPID

Abstract

Irregular (non-rectangular and non-circular) cutting problems (or nesting problems) are problems that aim to determine an optimal arrangement of smaller irregular items within larger, rectangular, or irregular pieces (which we call containers) in order to meet demand. Among these problems, we have the so-called irregular strip-packing problem, for which the container has a fixed height and "infinite" length and we want to find an arrangement of all items in the strip using the smallest possible length. This problem is of great practical importance, as it arises in various types of industries (such as textiles, furniture, footwear, and metalworking). Another related problem is the cutting path determination problem, which, given the layout of the items in the strip, aims to determine the shortest path that a cutting tool will take to cut all the items. Clearly, layout changes can lead to longer or shorter paths. This problem is also of practical importance, especially when the cost of cutting is relevant. The objective of this project is to study and implement a solution method for the integration of the irregular strip-packing problem and the cutting path determination problem. This solution method will be a meta-heuristic, which will involve a constructive heuristic and the exact solution of a mathematical model.(AU)