A branch-and-price algorithm for the temporal bin packing problem

被引:43
作者
Dell'Amico, Mauro [1 ]
Furini, Fabio [2 ]
Iori, Manuel [1 ]
机构
[1] Univ Modena & Reggio Emilia, DISMI, Via Amendola 2, I-42122 Reggio Emilia, Italy
[2] PSL Res Univ, Univ Paris Dauphine, LAMSADE, F-75016 Paris, France
关键词
Bin packing problem; Branch-and-price algorithm; Temporal bin packing problem; LINEAR-PROGRAMMING APPROACH; CUTTING STOCK PROBLEMS; FAST LOWER BOUNDS; KNAPSACK-PROBLEM; COLUMN GENERATION; DECOMPOSITION; MODELS; INSTANCES; PROPERTY; TYPOLOGY;
D O I
10.1016/j.cor.2019.104825
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A polynomial-size formulation, an exponential-size formulation, and a number of lower and upper bounds are studied. A branch-and-price algorithm for solving the exponential-size formulation is introduced. An overall algorithm combining the different methods is then proposed and tested through extensive computational experiments. (C) 2019 Elsevier Ltd. All rights reserved.
引用
收藏
页数:16
相关论文
共 57 条
[1]   A branch and bound algorithm for the strip packing problem [J].
Alvarez-Valdes, R. ;
Parreno, F. ;
Tamarit, J. M. .
OR SPECTRUM, 2009, 31 (02) :431-459
[2]   Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem [J].
Alves, Claudio ;
de Carvalho, Jose Valerio ;
Clautiaux, Francois ;
Rietz, Juergen .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 233 (01) :43-63
[3]   Optimal interval scheduling with a resource constraint [J].
Angelelli, Enrico ;
Bianchessi, Nicola ;
Filippi, Carlo .
COMPUTERS & OPERATIONS RESEARCH, 2014, 51 :268-281
[4]   On the complexity of interval scheduling with a resource constraint [J].
Angelelli, Enrico ;
Filippi, Carlo .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) :3650-3657
[5]  
Aydin N., 2019, TECHNICAL REPORT
[6]  
Baldacci B., 2018, INFORMS J COMPUT
[7]   Branch-and-price: Column generation for solving huge integer programs [J].
Barnhart, C ;
Johnson, EL ;
Nemhauser, GL ;
Savelsbergh, MWP ;
Vance, PH .
OPERATIONS RESEARCH, 1998, 46 (03) :316-329
[8]  
Bartlett M, 2005, LECT NOTES COMPUT SC, V3524, P34
[9]   LP Bounds in an Interval-Graph Algorithm for Orthogonal-Packing Feasibility [J].
Belov, Gleb ;
Rohling, Heide .
OPERATIONS RESEARCH, 2013, 61 (02) :483-497
[10]   Dual-optimal inequalities for stabilized column generation [J].
Ben Amor, Hatem ;
Desrosiers, Jacques ;
Valerio de Carvalho, Jose Manuel .
OPERATIONS RESEARCH, 2006, 54 (03) :454-463