A Computational Improvement to the Dynamic Programming Algorithm for the Optimal Cutting of Equal Rectangles

摘要

The problem concerned is to cut a rectangular plate with guillotine cuts so as to produce the maximum number of small equal rectangular pieces. The plate length and width are L and W (L ≥ W) respectively. The piece length and width are l and ω (l > ω) respectively. A dynamic programming algorithm for this problem was presented in Applied Mathematical Modelling 2005, 29(11). It has complexity O(LW) because it considers all plate sizes of length x and width y, where both x and y are integers, 0 < x ≤ L and 0 < y ≤ W. A new procedure of the algorithm is presented in this paper. It considers only a much smaller number of plate sizes and has complexity O(LW/l~2). The computational results indicate that in solving large scale instances, the new procedure is much faster than the procedure on which the original algorithm is based.