关键词: 无约束二维切割, 下料, 双排多段排样方式, 背包问题

Abstract: To solve large scale unconstrained two-dimensional guillotine-cutting problem of rectangular
items, an algorithm for generating the patterns of double-rows and multi segments is proposed, where
the plate is divided into two segments by a cut, each of which is then divided into a series of blocks with
a set of cuts, and each block contains a group of horizontal strips. The optimal position of the cut that
divides the plate into two segments is determined through enumeration. Knapsack problems are solved
to obtain the maximum values of all possible blocks and the block layouts on the segments. The
algorithm is tested on two groups of benchmark problems in the literature. The computational results
indicate that the algorithm can obtain better optimization results in a reasonable computation time.

Key words: unconstrained two-dimensional cutting, stock packing, double-rows and multi-segments
patterns, knapsack problem