Parallel algorithms for 3D irregular cutting and packing problems

Cutting and Packing problems (C&Ps) frequently occur within the manufacturing and distribution of products. These problems consider the cutting (or packing) of smaller items from a larger item. C&Ps have a high practical and theoretical relevance. Nesting problems, for example, concern the cutting of small objects with irregular geometric shapes from a larger object. Such problems frequently occur in e.g. garment manufacturing, sheet metal cutting, furniture making, shoe manufacturing and nowadays in 3D printing. 3D packing problems consider the filling of 3D containers, bins or objects with 3D items, while satisfying stability and other constraints. C&Ps are computationally intensive due to the combinatorial explosion of the search space and necessary geometric computations. Even today, solving problems with only a dozen items remains a challenge. When the items of the problem are irregular the challenge is even larger. This project will leverage modern parallel computing capabilities in order to speedup the algorithms to solve 3D irregular cutting and packing problems. This includes parallelization on the CPU, but also on the GPU or other special purpose hardware