An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem*

EasyChair Preprint 953

Abstract

The two-dimensional 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 Heuristic-Dynamic Programming (IHDP) algorithm is proposed to prove the important theorem about its complexity. The algorithm reduces the size of the discrete set, establishes the one-dimensional 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 sub-question 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: Two-Dimensional Cutting Problem, improved heuristic-dynamic programming, two-dimensional cutting problem with defects

@booklet{EasyChair:953,
  author    = {Yin Aihua and Chen Chong and Hu Dongping and Huang Jianghai and Yang Fan},
  title     = {An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem*},
  howpublished = {EasyChair Preprint 953},
  year      = {EasyChair, 2019}}