Given a set of identical capacitated bins, a set of weighted items and a set of precedences among such items, we are interested in determining the minimum number of bins that can accommodate all items and can be ordered in such a way that all precedences are satised. The problem, denoted as the Bin Packing Problem with Precedence Constraints (BPP-P), has a very intriguing combinatorial structure and models many assembly and scheduling issues.According to our knowledge the BPP-P has received little attention in the literature, and in this paper we address it for the first time with exact solution methods. In particular, we develop reduction criteria, a large set of lower bounds, a Variable Neighborhood Search upper bounding technique and a branch-and-bound algorithm. We show the eectiveness of the proposed algorithms by means of extensive computational tests on benchmark instances and comparison with standard integer linear programming techniques.

The Bin Packing Problem with Precedence Constraints / Dell'Amico, Mauro; DIAZ DIAZ, Jose Carlos; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 60:(2012), pp. 1491-1504. [10.1287/opre.1120.1109]

The Bin Packing Problem with Precedence Constraints

DELL'AMICO, Mauro;DIAZ DIAZ, Jose Carlos;IORI, MANUEL
2012

Abstract

Given a set of identical capacitated bins, a set of weighted items and a set of precedences among such items, we are interested in determining the minimum number of bins that can accommodate all items and can be ordered in such a way that all precedences are satised. The problem, denoted as the Bin Packing Problem with Precedence Constraints (BPP-P), has a very intriguing combinatorial structure and models many assembly and scheduling issues.According to our knowledge the BPP-P has received little attention in the literature, and in this paper we address it for the first time with exact solution methods. In particular, we develop reduction criteria, a large set of lower bounds, a Variable Neighborhood Search upper bounding technique and a branch-and-bound algorithm. We show the eectiveness of the proposed algorithms by means of extensive computational tests on benchmark instances and comparison with standard integer linear programming techniques.
60
1491
1504
The Bin Packing Problem with Precedence Constraints / Dell'Amico, Mauro; DIAZ DIAZ, Jose Carlos; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 60:(2012), pp. 1491-1504. [10.1287/opre.1120.1109]
Dell'Amico, Mauro; DIAZ DIAZ, Jose Carlos; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
1526-5463-2012-60-06-1491-2au-copy.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 353.66 kB
Formato Adobe PDF
353.66 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/684359
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 24
social impact