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.

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021