A Novel GRASP Algorithm for Solving the Bin Packing Problem
Автор: Abdesslem Layeb, Sara Chenche
Журнал: International Journal of Information Engineering and Electronic Business(IJIEEB) @ijieeb
Статья в выпуске: 2 vol.4, 2012 года.
Бесплатный доступ
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.
Bin Packing Problem, Heuristics, GRASP procedure, Tabu Search
Короткий адрес: https://sciup.org/15013116
IDR: 15013116
Список литературы A Novel GRASP Algorithm for Solving the Bin Packing Problem
- Martello, S., and Toth, P. Bin-packing problem. In Knapsack Problems: Algorithms and Computer Implementations.Wiley, 1990, (8): 221–245.
- 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.
- Fleszar, K., Hindi, K. S., 2002. New heuristics for one-dimensional bin-packing. Computers and Operations Research, 29 (7): 821-839.
- 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.
- 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.
- 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.
- Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics,1996, (2):5–30.
- 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 .
- 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.
- 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.
- 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.
- Glover, F. and M. Laguna. Tabu Search. Kluwer, Norwell, MA, 1997.
- 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.
