Bin packing problem considering irregular items

• Grant number: 21/04602-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: July 01, 2021
• End date: December 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Franklina Maria Bragion de Toledo
• Grantee: Diego Yoshihiro Hono
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

The packing problem considering irregular items is one of the challenges of the clothing industry. In this industry, for the quality of the final product, all the items that compose it must come from the same batch of fabric; for example, the sleeves, the front, and the back parts of a T-shirt must be cut together. In general, the cutting process is performed by placing the fabric on a table, so its width and length are fixed, which can be interpreted as a bin packing problem. This work aims to maximize the number of finished products cut in each bin, thus minimizing the loss of tissue. To this end, a mathematical programming model will be proposed for the problem studied using literature models as a starting point. Due to the computational complexity of the problem (NP-hard) the cases for which the proposal performs well and which cases it fails will be analyzed. In addition, a study of machine learning techniques will be carried out to apply them to the studied problem, thus looking for alternatives to solve the problem or to assist the exact methods in solving it. (AU)