An improved heuristic-dynamic programming algorithm for rectangular cutting problem

In this paper, we discussed a two-dimensional cutting problem with defects. In this problem, we are given a rectangular area which contains defects. The objective is to cut some rectangles with a given shape and direction from this rectangular area, which cannot overlap the defects, maximizing some profit associated with the rectangles generating by this cutting. We present an improved Heuristic-Dynamic Program (IHDP) to solve this problem and prove the important theorem about its complexity. The algorithm reduces the size of the discretization sets, establishes one-dimensional knapsack problem with the width and height of the small rectangular blocks, constructs two discretization sets using the obtained solution and the right and upper boundaries of the defects, and performs trial cut lines for each element of the discretization set. The algorithm calculates 14 internationally recognized examples. The experimental results show that it obtains the optimal solution of these examples, and its computing time is nearly ten times higher than that of the latest literature algorithm.