Geodesic
An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem
Computer Science and Information Systems, Tome 17 (2020) no. 3.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

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.
Keywords: Guillotine, Two-dimension cutting problem, Dynamic programming, Defect, NP-hard 
@article{CSIS_2020_17_3_a4,
     author = {Aihua Yin and Chong Chen and Dongping Hu and Jianghai Huang and Fan Yang},
     title = {An {Improved} {Heuristic-Dynamic} {Programming} {Algorithm} for {Rectangular} {Cutting} {Problem}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2020},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2020_17_3_a4/}
}
TY  - JOUR
AU  - Aihua Yin
AU  - Chong Chen
AU  - Dongping Hu
AU  - Jianghai Huang
AU  - Fan Yang
TI  - An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem
JO  - Computer Science and Information Systems
PY  - 2020
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2020_17_3_a4/
ID  - CSIS_2020_17_3_a4
ER  - 
%0 Journal Article
%A Aihua Yin
%A Chong Chen
%A Dongping Hu
%A Jianghai Huang
%A Fan Yang
%T An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem
%J Computer Science and Information Systems
%D 2020
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2020_17_3_a4/
%F CSIS_2020_17_3_a4
Aihua Yin; Chong Chen; Dongping Hu; Jianghai Huang; Fan Yang. An Improved Heuristic-Dynamic Programming Algorithm for Rectangular Cutting Problem. Computer Science and Information Systems, Tome 17 (2020) no. 3. http://geodesic.mathdoc.fr/item/CSIS_2020_17_3_a4/