New bin packing fast lower bounds

被引：16
作者：
Crainic, Teodor Gabriel
Perboli, Guido
Pezzuto, Miriam
Tadei, Roberto
机构：
[1] Politecn Torino, Dept Control & Comp Engn, I-10129 Turin, Italy
[2] Univ Montreal, Ctr Rech Transport, Montreal, PQ H3C 3J7, Canada
[3] Univ Montreal, Dept Management & Technol, UQAM, Montreal, PQ H3C 3J7, Canada
来源：
COMPUTERS & OPERATIONS RESEARCH | 2007年 / 34卷 / 11期
基金：
加拿大自然科学与工程研究理事会;
关键词：
bin packing; lower bounds;
D O I：
10.1016/j.cor.2006.02.007
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
In this paper, we address the issue of computing fast lower bounds for the Bin Packing problem, i.e., bounds that have a computational complexity dominated by the complexity of ordering the items by non-increasing values of their volume. We introduce new classes of fast lower bounds with improved asymptotic worst-case performance compared to well-known results for similar computational effort. Experimental results on a large set of problem instances indicate that the proposed bounds reduce both the deviation from the optimum and the computational effort. (C) 2006 Elsevier Ltd. All rights reserved.
引用
收藏
页码：3439 / 3457
页数：19
相关论文
共 21 条
[1]   A hybrid improvement heuristic for the one-dimensional bin packing problem [J].
Alvim, ACF ;
Ribeiro, CC ;
Glover, F .
JOURNAL OF HEURISTICS, 2004, 10 (02) :205-229
[2]  
BEASLEY JE, 1990, J OPER RES SOC, V41, P1069, DOI 10.1038/sj/jors/0411109
[3]   Transferring the principles of effective treatment into a "real world" prison setting [J].
Bourgon, G ;
Armstrong, B .
CRIMINAL JUSTICE AND BEHAVIOR, 2005, 32 (01) :3-25
[4]   A tight lower bound for optimal bin packing [J].
Chao, HY ;
Harper, MP ;
Quong, RW .
OPERATIONS RESEARCH LETTERS, 1995, 18 (03) :133-138
[5]   An improved lower bound for the bin packing problem [J].
Chen, BT ;
Srivastava, B .
DISCRETE APPLIED MATHEMATICS, 1996, 66 (01) :81-94
[6]  
Coffman, 1996, APPROXIMATION ALGORI
[7]  
CRAINIC TG, IN PRESS EUROPEAN J
[8]  
Falkenauer E., 1996, Journal of Heuristics, V2, P5, DOI 10.1007/BF00226291
[9]   New classes of fast lower bounds for bin packing problems [J].
Fekete, SP ;
Schepers, J .
MATHEMATICAL PROGRAMMING, 2001, 91 (01) :11-31
[10]  
Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
123