In the two-dimensional bin packing problem (2BP) we are given a set of rectangular items, each characterized by a width and a height, and an unlimited number of finite identical rectangular bins, of given width and height. The problem is to allocate, without overlapping, all the items to the minimum number of bins, with their edges parallel to those of the bins. An important variant of 2BP, which is also used in some approximation algorithms for its solution, is the strip packing problem (2SP), in which the items have to be packed in a strip of given width and infinite height, so as to minimize the height at which the strip is used. Two dimensional packing problems have many industrial applications, especially in cutting (e.g. wood, glass and paper industries) and packing (e.g. transportation, telecommunications and warehousing). We survey recent advances obtained for the two-dimensional bin packing problem.

Two-dimensional Bin Packing Problems

LODI, ANDREA;MARTELLO, SILVANO;MONACI, MICHELE;VIGO, DANIELE
2010

Abstract

In the two-dimensional bin packing problem (2BP) we are given a set of rectangular items, each characterized by a width and a height, and an unlimited number of finite identical rectangular bins, of given width and height. The problem is to allocate, without overlapping, all the items to the minimum number of bins, with their edges parallel to those of the bins. An important variant of 2BP, which is also used in some approximation algorithms for its solution, is the strip packing problem (2SP), in which the items have to be packed in a strip of given width and infinite height, so as to minimize the height at which the strip is used. Two dimensional packing problems have many industrial applications, especially in cutting (e.g. wood, glass and paper industries) and packing (e.g. transportation, telecommunications and warehousing). We survey recent advances obtained for the two-dimensional bin packing problem.
Paradigms of Combinatorial Optimization: Problems and New Approaches
107
129
A. Lodi; S. Martello; M. Monaci; D. Vigo
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/92372
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact