Two heuristics for the one-dimensional bin-packing problem

被引：38

作者：

Singh, Alok ^{[1
]}

Gupta, Ashok K. ^{[1
]}

机构：

[1] Univ Allahabad, Fac Sci, J K Inst Appl Phys & Technol, Allahabad 211002, Uttar Pradesh, India

来源：

OR SPECTRUM | 2007年 / 29卷 / 04期

关键词：

combinatorial optimization; grouping genetic algorithm; heuristic; one-dimensional bin-packing;

D O I：

10.1007/s00291-006-0071-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we have proposed two heuristics for the one-dimensional bin-packing problem. One is a hybrid steady-state grouping genetic algorithm, whereas the other is an improved version of Perturbation MBS' heuristic (Fleszar and Hindi in Comput Oper Res 29:821-839, 2002). A combined approach using these two heuristics gives results which are comparable with the best methods known so far.

引用

页码：765 / 781

页数：17

共 16 条

[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]

Bhatia AK, 2004, LECT NOTES COMPUT SC, V3316, P181

[3]

Coffman, 1996, APPROXIMATION ALGORI

[4]

de Carvalho JMV, 1999, ANN OPER RES, V86, P629

[5]

Falkenauer E., 1996, Journal of Heuristics, V2, P5, DOI 10.1007/BF00226291

[6]

Falkenauer E, 1995, P 6 INT C GEN ALG, P492

[7] New heuristics for one-dimensional bin-packing [J].

Fleszar, K ;

Hindi, KS .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (07) :821-839

[8] Hybrid evolutionary algorithms for graph coloring [J].

Galinier, P ;

Hao, JK .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 1999, 3 (04) :379-397

[9]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[10] A new heuristic algorithm for the one-dimensional bin-packing problem [J].

Gupta, JND ;

Ho, JC .

PRODUCTION PLANNING & CONTROL, 1999, 10 (06) :598-603

← 1 2 →