An improved heuristic-dynamic programming algorithm for rectangular cutting problem

Computer Science and Information Systems

article

Aihua Yin¹  Chong Chen¹  Dongping Hu¹  Jianghai Huang¹  Fan Yang¹ 

[1] School of Software and Internet of Things Engineering, Jiangxi University of Finance and Economics

关键词: Guillotine;    Two-dimension cutting problem;    Dynamic programming;    Defect;    NP-hard;   

DOI  :  10.2298/CSIS200125017Y

学科分类：土木及结构工程学

来源: Computer Science and Information Systems

【 摘 要 】

In this paper, the two-dimensional cutting problem with defects is discussed. The objective is to cut some rectangles in a given shape and direction without overlapping the defects from the rectangular plate and maximize some profit associated. An Improved Heuristic-Dynamic Program (IHDP) is presented to solve the problem. In this algorithm, the discrete set contains not only the solution of one-dimensional knapsack problem with small rectangular block width and height, but also the cutting positions of one unit outside four boundaries of each defect. In addition, the denormalization recursive method is used to further decompose the sub problem with defects. The algorithm computes thousands of typical instances. The computational experimental results show that IHDP obtains most of the optimal solution of these instances, and its computation time is less than that of the latest literature algorithms.

【 授权许可】

CC BY-NC-ND