We consider the variant of the Two-Dimensional Bin Packing Problem in which items have to be obtained by a series of guillotine cuts and cannot be rotated. We present a heuristic algorithm based on partial enumeration, and computationally evaluate its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.
Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints / Lodi, Andrea; Monaci, Michele; Pietrobuoni, Enrico. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 217:(2017), pp. 40-47. [10.1016/j.dam.2015.09.012]
Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints
LODI, ANDREA;MONACI, MICHELE;PIETROBUONI, ENRICO
2017
Abstract
We consider the variant of the Two-Dimensional Bin Packing Problem in which items have to be obtained by a series of guillotine cuts and cannot be rotated. We present a heuristic algorithm based on partial enumeration, and computationally evaluate its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.