A deterministic algorithm for generating optimal three-stage layouts of homogenous strip pieces
Abstract: The time required by
the algorithms for general layouts to solve the large-scale two-dimensional
cutting problems may become unaffordable. So this paper presents an exact
algorithm to solve above problems.
Design/methodology/approach: The algorithm uses the dynamic programming algorithm
to generate the optimal homogenous strips, solves the knapsack problem to
determine the optimal layout of the homogenous strip in the composite strip and
the composite strip in the segment, and optimally selects the enumerated
segments to compose the three-stage layout.
Findings: The algorithm not only meets the shearing and punching process
need, but also achieves good results within reasonable time.
Originality/value: The algorithm is tested through 43 large-scale
benchmark problems. The number of optimal solutions is 39 for this paper’s
algorithm; the rate of the rest 4 problem’s solution value and the optimal
solution is 99.9%, and the average consumed time is only 2.18 seconds. This
paper’s pattern is used to simplify the cutting process. Compared with the
classic three-stage, the two-segment and the T-shape algorithms, the solutions
of the algorithm are better than that of the above three algorithms.
Experimental results show that the algorithm to solve a large-scale piece
packing quickly and efficiency.
Author: Jun Ji, Fei-Fei Xing,
Jun Du, Ning Shi, Yao-Dong Cui
Journal Code: jptindustrigg140077
