A Knapsack Function Based Algorithm For The Unconstrained Two Dimensional Guillotine Cutting Problem

In this paper we tackle the unconstrained non-staged guillotine two-dimensional cutting stock problem (UTDC) with rectangular pieces and one rectangular stock. This problem and its variants have been widely treated in literature by exact and heuristic solution methods which use the rst idea of knapsack function (Gilmore and Gomory, 1966). We highlight three errors present in the original procedure proposed to compute the recursive expression of the knapsack function. These errors aect the correctness of the solution providing at the same time an increase of the computational eort. Corrections for these errors are presented and an improved computational procedure is proposed. It has been experienced on a wide set of test instances present in literature (Pack-Lib2). The experimentation shows that the presented procedure outperforms or has computation time performances very near to the ones of other solution methods proposed in literature.