Heuristic for constrained T-shape cutting patterns of rectangular pieces

T-shape patterns are often used in dividing stock plates into rectangular pieces, because they make good balance between plate cost and cutting complexity. A dividing cut separates the plate into two segments, each of which contains parallel strips, and the strip orientations of the two segments are...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2012-12, Vol.39 (12), p.3031-3039
Main Authors: Cui, Yaodong, Huang, Baixiong
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Constraints
Cutting
Cutting stock
Cutting stock problem
Exact sciences and technology
Flows in networks. Combinatorial problems
Heuristic
Mathematical models
Operational research and scientific management
Operational research. Management science
Optimization
Optimization algorithms
Plates
Segments
Strip
Studies
T-shape patterns
Two-dimensional cutting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:T-shape patterns are often used in dividing stock plates into rectangular pieces, because they make good balance between plate cost and cutting complexity. A dividing cut separates the plate into two segments, each of which contains parallel strips, and the strip orientations of the two segments are perpendicular to each other. This paper presents a heuristic algorithm for constrained T-shape patterns, where the optimization objective is to maximize the pattern value, and the frequency of each piece type does not exceed the demand. The algorithm considers many dividing-cut positions, determines the pattern value associated to each position using a layout-generation procedure, and selects the one with the maximum pattern value as the solution. Pseudo upper bounds are used to skip some non-promising positions. The computational results show that the algorithm is fast and able to get solutions better than those of the optimal two-staged patterns in terms of material utilization. ► We present a heuristic for the constrained two-dimensional cutting problem of rectangular pieces. ► T-shape patterns are used to simplify the cutting process. ► The approach can solve large-scale instances quickly. ► The computational results indicate that T-shape patterns can yield much better material utilization than both two-staged and homogenous T-shape patterns.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2012.03.001