The Bin Packing Problem with Precedence Constraints
The Bin Packing Problem with Precedence Constraints
复制标题
DOI：
10.1287/opre.1120.1109
复制
发表时间：
2012-11
期刊：
影响因子：
--
通讯作者：
M. dell’Amico;J. Díaz;M. Iori
中科院分区：
文献类型：
--
作者：
M. dell’Amico;J. Díaz;M. Iori
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.
