Advanced search
Start date

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


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)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

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)
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., . (19/25041-8, 18/07240-0, 18/16600-0, 16/01860-1)
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., . (13/07375-0, 18/07240-0, 20/15707-6)
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., . (13/07375-0, 16/01860-1, 18/07240-0)
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., . (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, . (13/07375-0, 18/07240-0)
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, . (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, . (13/07375-0, 18/07240-0, 15/15024-8, 17/01097-9)

Please report errors in scientific publications list using this form.