Bin Packing Problem with General Precedence Constraints

In this paper we study the bin packing problem with general precedence constraints, in which a set of weighted items has to be packed in the minimal number of capacitated bins, while satisfying precedence relationships among pair of items. The problem generalizes the well- known Simple Assembly Line Balancing problem, and models relevant real-world situations. To solve the problem we propose a series of lower and upper bounding techniques, including an iterated local search algorithm. Preliminary computational results show the efficiency of the proposed approach in solving complex instances.