An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems

作者：Russo Mauro; Sforza Antonio; Aerie Claudio^*

来源：Computers & Operations Research, 2014, 50: 97-114.

DOI：10.1016/j.cor.2014.04.001

• Guillotine cutting
• Knapsack function
• Dynamic programming

In the unconstrained two-dimensional cutting problems (U2DCP) small rectangular objects have to be extracted from a large rectangular sheet, with no limits on the number of small objects.
The exact U2DCP solving approaches present in literature show some limits in tackling very large size instances, due to the high memory requirements.
In this work we propose five improvements, three original and two derived from the literature, in order to overcome these limits and to reduce the computational burden of the knapsack function based U2DCP solving approaches. These improvements, based on proofed theoretical results, allow to reduce the search space and to avoid redundant solutions without loss of the feasible ones.
The presented improvements, together with several computational refinements, are integrated in a new dynamic programming algorithm, which modifies the one by Russo et al. (2013 [16]). The proposed algorithm has been experienced on test instances present in literature and compared with the best U2DCP solving approaches. The obtained results show that it significantly outperforms them and it determines the optimal solution of unsolved very large size instances.

• 出版日期2014-10