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

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)