A recursive branch-and-bound algorithm for constrained homogenous T-shape cutting patterns

The manufacturing industry often uses the two-phase process to divide stock plates into rectangular items. A guillotine machine cuts the plates into homogenous strips at the first phase, where each strip contains items of the same type. Either a guillotine machine or stamping press cuts the strips into items at the second phase. This paper presents a recursive branch-and-bound algorithm for generating constrained homogenous T-shape (HTS) cutting patterns at the first phase, where the frequency of an item type is constrained by its upper bound. A HTS pattern includes two segments. Each segment contains homogenous strips of the same direction. The strip directions of the two segments are perpendicular to each other. Two versions of the algorithm are presented. The first uses the unconstrained solutions to estimate the upper bounds, and the second uses the constrained solutions. The computational results indicate that the algorithm is much faster than existing algorithms. (C) 2011 Published by Elsevier Ltd