|
Title:
|
A HEURISTIC DYNAMIC-PROGRAMMING ALGORITHM FOR 2D UNCONSTRAINED GUILLOTINE CUTTING |
|
Author(s):
|
X.song , C.b.chu , Y.y.nie |
|
ISBN:
|
972-98947-3-6 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2004 |
|
Edition:
|
Single |
|
Keywords:
|
Unconstraint knapsack problem; Heuristic dynamic programming. |
|
Type:
|
Full Paper |
|
First Page:
|
1527 |
|
Last Page:
|
1534 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In this paper, a heuristic dynamic-programming recursion is proposed for solving unconstrained 2D knapsack problem efficiently. The algorithm we propose is an incompletely enumerative method, in which some intricate cutting patterns may not be enumerated. Compared with the traditional dynamic-programming, the algorithm gives a high percentage of optimal solutions (93%) with a much lowered computational complexity. Some theoretical analyses for the algorithm are performed. Computational results are given for small and medium-sized problems. |
|
|
|
|
|
|
