Uncertainty in cutting and packing problems: robust planning and optimized replanning in manufacturing and transportation

• Grant number: 18/07240-0
• Support Opportunities: Regular Research Grants
• Start date: September 01, 2018
• End date: August 31, 2022
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Agreement: Fundação para a Ciência e a Tecnologia (FCT)
• Principal Investigator: Franklina Maria Bragion de Toledo
• Grantee: Franklina Maria Bragion de Toledo
• 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 researchers: Adriana Cristina Cherri ; Larissa Tebaldi de Oliveira ; Luiz Henrique Cherri ; Marina Andretta
• Associated scholarship(s): 20/15707-6 - Alternative approaches for dealing with uncertainties in nesting problems, BP.PD

Abstract

Cutting and Packing (C&P) problems are hard combinatorial optimization problems that arise in the context of several manufacturing and process industries or in their supply chains. These problems occur whenever a bigger object or space has to be divided into smaller parts, so that waste is minimized. This is the case when cutting paper rolls in the paper industry, large wood boards into smaller rectangular panels in the furniture industry, irregularly shaped garment parts from fabric rolls in the apparel industry, but also when packing boxes on pallets and these inside trucks or containers, in logistics applications. The resolution of these problems is not only a scientific challenge, given its intrinsic difficulty, but has also a great economic impact as it contributes to the decrease of a major cost factor for many production sectors: the raw-materials, which may represent up to 40% of the total production costs. It has also a significant environmental repercussion as it leads to a less intense exploration of the natural resources from where the raw-materials are extracted and decreases the quantity of garbage generated. In logistics applications, minimizing the waste of container/truck loading space directly leads smaller logistics costs and less pollution. Current research has paid little attention to the role of uncertainty in these problems, hindering a wider adoption of research results by companies. In companies? daily life, uncertainty can be taken for granted. Quantities ordered and the orders? due dates change. If uncertainty in future demand was somehow taken into account, raw-material could be saved. In the textile and garment industries, defects on fabric rolls arise and require production replanning. Cutting patterns less sensible to defects in fabric would lead to a smaller impact on the overall production chain. Logistics operators receive cargo where the delivery dates and the actual dimensions do not match the ones previously declared by their customers. If this variability was taken into account, more efficient truck and container loading plans and vehicle routes could be achieved. To plan for variability is a must for companies, but research is still lagging behind. Explicitly taking into account uncertainty, and the induced variability, when solving C&P problems with optimization techniques, is the core research idea of this project. Building on the extensive experience of the research team on the resolution of C&P problems, advanced optimization techniques (based on mathematical programming models, metaheuristics and their hybridization) will be used to develop and make available the next generation of C&P algorithms. This is a joint project between INESC TEC and a research group in the State of São Paulo, Brazil. This is a long- standing collaboration that has already proved its value, regarding both skills and expertise complementarity and creation of critical mass to approach complex problems. (AU)

Scientific publications

(8)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

BARTMEYER, PETRA MARIA; OLIVEIRA, LARISSA TEBALDI; SOUZA LEAO, ALINE APARECIDA; BRAGION TOLEDO, FRANKLINA MARIA. An expert system to react to defective areas in nesting problems. EXPERT SYSTEMS WITH APPLICATIONS, v. 209, p. 11-pg., 2022-08-02. (13/07375-0, 18/07240-0, 20/15707-6)

LAYANE RODRIGUES DE SOUZA QUEIROZ; MARINA ANDRETTA. A STOCHASTIC OPTIMIZATION MODEL FOR THE IRREGULAR KNAPSACK PROBLEM WITH UNCERTAINTY IN THE PLATE DEFECTS. Pesquisa Operacional, v. 42, 2022-08-26. (18/07240-0, 16/01860-1, 13/07375-0)

DE SOUZA QUEIROZ, LAYANE RODRIGUES; ANDRETTA, MARINA. A branch-and-cut algorithm for the irregular strip packing problem with uncertain demands. International Transactions in Operational Research, v. 29, n. 6, p. 28-pg., 2022-02-07. (13/07375-0, 16/01860-1, 18/07240-0)

DO NASCIMENTO, DOUGLAS NOGUEIRA; CHERRI, ADRIANA CRISTINA; OLIVEIRA, JOSE FERNANDO. The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches. OPERATIONAL RESEARCH, v. 22, n. 5, p. 41-pg., 2022-08-06. (19/25041-8, 18/07240-0, 18/16600-0, 16/01860-1)

LEAO, ALINE A. S.; TOLEDO, FRANKLINA M. B.; OLIVEIRA, JOSE FERNANDO; CARRAVILLA, MARIA ANTONIA; ALVAREZ-VALDES, RAMON. Irregular packing problems: A review of mathematical models. European Journal of Operational Research, v. 282, n. 3, p. 803-822, MAY 1 2020. (13/07375-0, 12/21176-7, 18/07240-0)

CASTELLUCCI, PEDRO B.; TOLEDO, FRANKLINA M. B.; COSTA, ALYSSON M.. Output maximization container loading problem with time availability constraints. OPERATIONS RESEARCH PERSPECTIVES, v. 6, 2019. (13/07375-0, 18/07240-0, 15/15024-8, 17/01097-9)

CHERRI, ADRIANA CRISTINA; CHERRI, LUIZ HENRIQUE; OLIVEIRA, BEATRIZ BRITO; OLIVEIRA, JOSE FERNANDO; CARRAVILLA, MARIA ANTONIA. A stochastic programming approach to the cutting stock problem with usable leftovers. European Journal of Operational Research, v. 308, n. 1, p. 16-pg., 2023-02-16. (18/07240-0)

FERREIRA, KAMYLA MARIA; DE QUEIROZ, THIAGO ALVES; BRAGION TOLEDO, FRANKLINA MARIA. An exact approach for the green vehicle routing problem with two-dimensional loading constraints and split delivery. Computers & Operations Research, v. 136, DEC 2021. (13/07375-0, 18/07240-0)