Download PDFOpen PDF in browserAn Improved HeuristicDynamic Programming Algorithm for Rectangular Cutting Problem*EasyChair Preprint 9539 pages•Date: May 2, 2019AbstractThe twodimensional cutting problem with defects is discussed. A small rectangular block of a given size and direction is cut from a large rectangular plate containing a plurality of defects. The number of each small rectangular block cut is not limited, and each cut is to be of the guillotine and the cutting line cannot be cut to the defects. In addition, the small rectangular blocks that are cut cannot contain defects, and the goal is to maximize the total value of cutting small rectangular blocks. In order to solve the above problems, an improved HeuristicDynamic Programming (IHDP) algorithm is proposed to prove the important theorem about its complexity. The algorithm reduces the size of the discrete set, establishes the onedimensional knapsack problem with the width and height of the small rectangular block, constructs two discrete sets using the obtained solution and the right and upper boundaries of the defects, and performs trial cut lines for each element of the discrete set. The subquestion is divided, and the cutting line passing through the defect is abandoned. The algorithm calculates 14 internationally accepted examples. The experimental results show that it obtains the optimal solution of these examples, and its computational efficiency is nearly ten times higher than that of the latest literature algorithm. Keyphrases: TwoDimensional Cutting Problem, improved heuristicdynamic programming, twodimensional cutting problem with defects
