文章基本信息

标题：An improved heuristic-dynamic programming algorithm for rectangular cutting problem
本地全文：下载
作者：Yin, Aihua ; Chen, Chong ; Hu, Dongping 等
期刊名称：Computer Science and Information Systems
印刷版ISSN：1820-0214
电子版ISSN：2406-1018
出版年度：2020
卷号：17
期号：3
页码：717-735
DOI：10.2298/CSIS200125017Y
出版社：ComSIS Consortium
摘要：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.
关键词：Guillotine; Two-dimension cutting problem; Dynamic programming; Defect; NP-hard