Heuristic and exact algorithms for generating homogeneous constrained three-staged cutting patterns

An approach is proposed for generating homogeneous three-staged cutting patterns for the constrained two-dimensional guillotine-cutting problems of rectangles. It is based on branch-and-bound procedure combined with dynamic programming techniques. The stock plate is divided into segments. Each segment consists of strips with the same direction. Only homogeneous strips are allowed, each of which contains rectangles of the same size. The approach uses a tree-search procedure. It starts from an initial lower bound, implicitly generates all possible segments through the builds of strips, and constructs all possible patterns through the builds of segments. Tighter bounds are established to discard non-promising segments and patterns. Both heuristic and exact algorithms are proposed. The computational results indicate that the algorithms are capable of dealing with problems of larger scale. Finally, the solution to a cutting problem taken from a factory that makes passenger cars is given.