An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem

Aihua Yin1, Chong Chen1, Dongping Hu1, Jianghai Huang1 and Fan Yang1

  1. School of Software and Internet of Things Engineering, Jiangxi University of Finance and Economics
    Nanchang Jiangxi, China
    Dongping_hu337@jxufe.edu.cn

Abstract

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.

Key words

Guillotine, Two-dimension cutting problem, Dynamic programming, Defect, NP-hard

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS200125017Y

Publication information

Volume 17, Issue 3 (October 2020)
Year of Publication: 2020
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Yin, A., Chen, C., Hu, D., Huang, J., Yang, F.: An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem. Computer Science and Information Systems, Vol. 17, No. 3, 717-735. (2020), https://doi.org/10.2298/CSIS200125017Y