Given a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90◦. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower boundwhich explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computationalexperiments.

A Lower Bound for the Non-Orineted Two-Dimensionl Bin Packing Problem / Dell'Amico, Mauro; S. Martello, S.; D., Vigo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 118:1-2(2002), pp. 13-24. [10.1016/S0166-218X(01)00253-0]

A Lower Bound for the Non-Orineted Two-Dimensionl Bin Packing Problem

DELL'AMICO, Mauro;
2002

Abstract

Given a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90◦. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower boundwhich explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computationalexperiments.
2002
118
1-2
13
24
A Lower Bound for the Non-Orineted Two-Dimensionl Bin Packing Problem / Dell'Amico, Mauro; S. Martello, S.; D., Vigo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 118:1-2(2002), pp. 13-24. [10.1016/S0166-218X(01)00253-0]
Dell'Amico, Mauro; S. Martello, S.; D., Vigo
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0166218X01002530-main.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 110.36 kB
Formato Adobe PDF
110.36 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/15977
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 52
  • ???jsp.display-item.citation.isi??? 43
social impact