Professor, Department of Industrial Engineering
University of Porto
Cutting and Packing 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 objects or spaces, 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 the case when packing boxes on pallets and these inside trucks or containers, in logistics applications. All these problems have in common the existence of a geometric sub-problem, which deals with the small object non-overlap constraints.
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 one of the major cost factors for many production sectors: the raw-materials. In some industries raw-material 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, which frequently has also important environmental impacts. In logistics applications, minimizing container and truck loading space waste directly leads to less transportation needs and therefore to smaller logistics costs and less pollution.
In this talk the several Cutting and Packing problems will be characterized and exemplified, based on Gerhard Wäscher’s typology (2007), allowing non-specialists to have a broad view over the area. Afterwards, as geometry plays a critical role in these problems, the geometric manipulation techniques more relevant for Cutting and Packing problems resolution will be presented. Finally, aiming to illustrate some of the most recent developments in the area, some approaches based on heuristics and metaheuristics, for the container loading problem, and based on mathematical programming models, for the irregular packing problem, will be described.