The Bin Packing Problem with Precedence Constraints

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. Subject classifications: bin packing problem; precedence constraints; branch-and-bound. Area of review: Optimization. History: Received May 2010; revisions received May 2011, September 2011; accepted November 2011. Published online in Articles in Advance November 20, 2012.