The Bin Packing Problem with Precedence Constraints

Mauro Dell'Amico (), José Carlos Díaz Díaz () and Manuel Iori ()
Additional contact information
Mauro Dell'Amico: DISMI, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
José Carlos Díaz Díaz: DISMI, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Manuel Iori: DISMI, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy

Operations Research, 2012, vol. 60, issue 6, 1491-1504

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 satisfied. 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 effectiveness of the proposed algorithms by means of extensive computational tests on benchmark instances and comparison with standard integer linear programming techniques.

Keywords: bin packing problem; precedence constraints; branch-and-bound (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1109 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:6:p:1491-1504

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().