Given a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.

Martello S., Vigo D. (1998). Exact solution of the two-dimensional finite bin packing problem. MANAGEMENT SCIENCE, 44(3), 388-399 [10.1287/mnsc.44.3.388].

Exact solution of the two-dimensional finite bin packing problem

Martello S.
Membro del Collaboration Group
;
Vigo D.
Membro del Collaboration Group
1998

Abstract

Given a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.
1998
Martello S., Vigo D. (1998). Exact solution of the two-dimensional finite bin packing problem. MANAGEMENT SCIENCE, 44(3), 388-399 [10.1287/mnsc.44.3.388].
Martello S.; Vigo D.
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: https://hdl.handle.net/11585/954395
 Attenzione

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

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