International Journal of Information Engineering and Electronic Business (IJIEEB)
IJIEEB Vol. 4, No. 2, 8 Apr. 2012
Cover page and Table of Contents: PDF (size: 125KB)
A Novel GRASP Algorithm for Solving the Bin Packing Problem
Full Text (PDF, 125KB), PP.8-14
Views: 0 Downloads: 0
Author(s)
Abdesslem Layeb
1,*
Sara Chenche
2
Index Terms
Bin Packing Problem, Heuristics, GRASP procedure, Tabu Search
Abstract
The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems. This problem consists in packing a set of items into a minimum number of bins. There are several variants of this problem; the most basic problem is the one-dimensional bin packing problem (1-BPP). In this paper, we present a new approach based on the GRASP procedure to deal with the1-BPP problem. The first GRASP phase is based on a new random heuristics based on hybridization between First Fit and Best Fit heuristics. The second GRASP phase is based on Tabu search algorithm used for the enhancement of the solutions found in the first phase. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.
Cite This Paper
Abdesslem Layeb, Sara Chenche, "A Novel GRASP Algorithm for Solving the Bin Packing Problem", International Journal of Information Engineering and Electronic Business(IJIEEB), vol.4, no.2, pp.8-14, 2012. DOI:10.5815/ijieeb.2012.02.02
Reference
[1]Martello, S., and Toth, P. Bin-packing problem. In Knapsack Problems: Algorithms and Computer Implementations.Wiley, 1990, (8): 221–245.
[2]Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S. Approximation algorithms for bin packing: A survery. In D. Hochbaum, editor, Appoximation algorithms for NP-Hard Problems, 1996, 46–93. PWS Publishing, Boston.
[3]Fleszar, K., Hindi, K. S., 2002. New heuristics for one-dimensional bin-packing. Computers and Operations Research, 29 (7): 821-839.
[4]lvim, A.C.F., Ribeiro, C.C., Glover, F., Aloise, D.J. A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem. Journal of Heuristics, 2004, (10):205–229.
[5]Kao, C.-Y. and F.-T. Lin. A stochastic approach for the one-dimensional bin-packing problems. In Systems, Man and Cybernetics, 1992, (2): 1545–1551.
[6]Scholl, A., R. Klein, and C. Juergens (1997). Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research,1997, 24(7): 627–645.
[7]Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics,1996, (2):5–30.
[8]Wang, S., Shi, R., Wang, L. and Ge, M. Study on improved ant colony optimization for bin-packing problem, International Conference on Computer Desingn and Application, 2010,(4):489–491 .
[9]Luis, M., Salhi, S. and Nagy, G. A guided reactive GRASP for the capacitated multi-source Weber problem, Computers & Operations Research, 2011, 38( 7): pp. 1014-1024.
[10]Montoya-Torres, J.R., Aponte, A., Rosas, P., Caballero-Villalobos, J.P. Applying GRASP meta-heuristic to solve the single-item two-echelon uncapacitated facility location problem. Int. J. of Applied Decision Sciences, 2010, 3(4): 297 – 310.
[11]Moura, A.V. and Scaraficci, R.A. A GRASP strategy for a more constrained School Timetabling Problem. International Journal of Operational Research, 2010, 7(2): 152 – 170.
[12]Glover, F. and M. Laguna. Tabu Search. Kluwer, Norwell, MA, 1997.
[13]Jiamin Liu, Yong Yue, Zongran Dong, Carsten Maple, and Malcolm Keech. A novel hybrid tabu search approach to container loading. Computers & Operations Research, 2011, 38(4):797–807.