Research plan

To implement the research ideas three different, and frequent in practice, types of Cutting and Packing problems will be studied under specific conditions of uncertainty, occurring in real-world industries and services:

1. Multi-period one-dimensional cutting stock problem with uncertainty on the future period’s demand, as arising in the paper, metal or wooden profiles industries.
2. Two-dimensional cutting problem with uncertainty on the raw-material, as it happens in the textile and garment industries where fabric defects along dozens or hundreds of meters make unfeasible the previously planned cutting patterns.
3. Three-dimensional packing problems with uncertainty on the dimensions of the boxes to pack and on the delivery/availability data, as it occurs in the transportation sector where trucks or containers are to be loaded with boxes, and the dimensions of the actual items to load and the arrival date to the warehouse do not match the dimensions previously declared by customers.

The three problems will be approached from the optimized replanning and robust planning perspectives.

Cutting and Packing problems classification

Cutting and Packing (C&P) problems can be classified according to their dimensionality in 1D, 2D or 3D problems. This classification arises from the number of dimensions that are relevant for the problem resolution and depend directly on the real-world application, in several industrial and service sectors (e.g. paper, footwear, textile, garment, furniture, logistics), from which are derived. For instance, when cutting paper rolls in narrower rolls, one-dimensional (1D) problems arise. Cutting rectangular wood boards into smaller rectangles supposes a 2D cutting problem. An important sub-class of 2D C&P problems occurs when raw materials have to be cut into irregular parts (e.g. garment and footwear industries) - the nesting problem. Finally 3D problems arise, for example, when boxes have to be packed in containers or when cutting steel blocks for casting moulds.

Uncertainty classification in practical Cutting and Packing problems

In C&P problems, one or more items of material or space (the raw-material) must be divided into smaller pieces, usually ordered by customers. The main objective is waste minimization, i.e. the portion of the big items that is not used to produce small pieces. A cutting process has as physical input raw-material and as logic input information regarding what to cut (piece dimensions and quantities) and when to have the small pieces cut (due dates). A packing process has as physical input empty space and as logic input information regarding what to pack (piece dimensions and quantities) and when the pieces will be available to pack (arrival dates). In both cases, the outcome is a set of cutting or packing plans to execute. Uncertainty may arise in connection to any element of this structural information regarding Cutting and Packing problems, i.e. dimensions, quantities and due dates/arrival dates of small pieces and raw-material characteristics and properties. Uncertainty related to the execution of the cutting plans, i.e. related to the cutting machinery, will be out of the scope of this project.