An exact algorithm for generating homogeneous T-shape cutting patterns

An exact algorithm for generating homogeneous T-shape cutting patterns

0.00 Avg rating0 Votes
Article ID: iaor20081813
Country: United Kingdom
Volume: 34
Issue: 4
Start Page Number: 1107
End Page Number: 1120
Publication Date: Apr 2007
Journal: Computers and Operations Research
Authors:
Keywords: programming: branch and bound, programming: dynamic
Abstract:

Both the material usage and the complexity of the cutting process should be considered in generating cutting patterns. This paper presents an exact algorithm for constrained two-dimensional guillotine-cutting problems of rectangles. It uses homogeneous T-shape patterns to simplify the cutting process. Only homogeneous strips are allowed, each of which contains rectangular blanks of the same size and direction. The sheet is divided into two segments. Each segment consists of strips of the same length and direction. The strip directions of the two segments are perpendicular to each other. The algorithm is based on branch and bound procedure combined with dynamic programming techniques. It is a bottom-up tree-search approach that searches the solution tree from the branches to the root. Tighter bounds are established to shorten the searching space. The computational results indicate that the algorithm is efficient both in computation time and in material usage.

Reviews

Required fields are marked *. Your email address will not be published.