The strip cutting/packing problem: Incremental substrip algorithms-based heuristics

The strip cutting problem consists of cutting a large strip with a fixed-width and unlimited length into smaller sub-rectangles, without violating the demand values imposed on each sub-rectangle. Computer science, industrial engineering, logistics, manufacturing, management, production processes are among obvious fields of applications. In this paper we present some algorithms for solving approximately large-scale strip cutting/packing problems. The strip cutting problem is reduced to a series of single constrained cutting stock problems and solved by using dynamic programming techniques and a tree search procedure. The performances of the proposed algorithms are evaluated on a set of medium and large size problem instances. These algorithms are parallelizable and this is one of their important features.