New Lower Bound for the Bin Packing Problem
作者： Bassem Jarboui , Abdelwaheb Rebai
DOI:
关键词:
摘要: In this paper, we present new classes of lower bound for the one-dimensional bin packing problem, prove that worst-case asymptotic performance ratio is 3/4. Extensive numerical experiments show outperforms best bounds from literature.
mistaconference.org 参考文章(15)
M. R. Garey, E. G. Coffman, D. S. Johnson, Approximation algorithms for bin packing: a survey Approximation algorithms for NP-hard problems. pp. 46- 93 ,(1996)
Adriana C.F. Alvim, Celso C. Ribeiro, Fred Glover, Dario J. Aloise, A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem Journal of Heuristics. ,vol. 10, pp. 205- 229 ,(2004) , 10.1023/B:HEUR.0000026267.44673.ED
François Vanderbeck, Computational study of a column generation algorithm for bin packing and cutting stock problems Mathematical Programming. ,vol. 86, pp. 565- 594 ,(1999) , 10.1007/S101070050105
Mohamed Haouari, Anis Gharbi, Fast lifting procedures for the bin packing problem Discrete Optimization. ,vol. 2, pp. 201- 218 ,(2005) , 10.1016/J.DISOPT.2005.06.002
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Samir Elhedhli, Ranking lower bounds for the bin-packing problem European Journal of Operational Research. ,vol. 160, pp. 34- 46 ,(2005) , 10.1016/J.EJOR.2003.06.019
Armin Scholl, Robert Klein, Christian Jürgens, BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem Computers & Operations Research. ,vol. 24, pp. 627- 645 ,(1997) , 10.1016/S0305-0548(96)00082-2
Silvano Martello, Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations ,(1990)
Teodor Gabriel Crainic, Guido Perboli, Miriam Pezzuto, Roberto Tadei, Computing the asymptotic worst-case of bin packing lower bounds European Journal of Operational Research. ,vol. 183, pp. 1295- 1303 ,(2007) , 10.1016/J.EJOR.2005.07.032
Jean-Marie Bourjolly, Vianney Rebetez, An analysis of lower bound procedures for the bin packing problem Computers & Operations Research. ,vol. 32, pp. 395- 405 ,(2005) , 10.1016/S0305-0548(03)00244-2