The Bin Packing Problem with Precedence Constraints
成果类型：
Article
署名作者：
Dell'Amico, Mauro; Diaz, Jose Carlos Diaz; Iori, Manuel
署名单位：
Universita di Modena e Reggio Emilia
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1120.1109
发表日期：
2012
页码：
1491-1504
关键词：
摘要：
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.