Download PDFOpen PDF in browser
Switch back to the title and the abstract in Chinese

A Quick Heuristic-Dynamic Programming for The Two-Dimensional Cutting Problem*

EasyChair Preprint no. 946

9 pagesDate: May 1, 2019


The two-dimensional rectangular cutting problem with defects is discussed. The goal is to cut a small rectangular block of a given height and width from a large rectangular object containing a plurality of defects on the premise of satisfying several constraints, so that the sum of the area of the cut small rectangular blocks are maximized. The constraint is that each cutting operation must be guillotine and cannot pass through the defects, and the number of small rectangular blocks of each type is not limited and maintains a given direction. The problem is regarded as covering the original plate with small rectangular block, and a Quick Heuristic-Dynamic Programming (QHDP) algorithm is proposed. Firstly, a one-dimensional knapsack problem is established according to the height and width of small rectangular blocks, respectively, and an efficient discrete set is generated respectively. Then, each value in the discrete set is used as a possible cutting line coordinate for sub-problem division. If a cutting line passes through the defects, the recursive branch is cut off. The algorithm calculates 14 internationally accepted examples. The experimental results show that it has obtained the optimal solution of all the examples, and the calculation time is less than one tenth of the best algorithm in the current literature. The algorithm complexity is analyzed and proved.

Keyphrases: defects, dynamic programming, NP-hard, Optimization, two-dimensional cutting

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Yin Aihua and Huang Jianghai and Hu Dongping and Chen Chong},
  title = {A Quick Heuristic-Dynamic Programming for The Two-Dimensional Cutting Problem*},
  howpublished = {EasyChair Preprint no. 946},

  year = {EasyChair, 2019}}
Download PDFOpen PDF in browser