IMPROVED DYNAMIC PROGRAMMING ALGORITHM FOR UNCONSTRAINED TWO-DIMENSIONAL STOCK CUTTING PROBLEM

In this paper, a new dynamic programming algorithm for unconstrained 2D stuck cutting problem is presented. The complexity of this new algorithm is analyzed. An improved method is also presented according to the property of the new algorithm, with respact to the theoretical analysis, the applicable scope of the improved method is given and the future applicability is described. It has been shown in numerical experiments that compared with the original dynamic programming method, the improved method can save the computational time and space with an optimal solution.