An Alternative Heuristics For Bin Packing Problem

by Nurul Afza Hashim, Faridah Zulkipli, Siti Sarah Januri and Dr. S.Sarifah Radiah Shariff

Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management

Bali, Indonesia, January 7 – 9, 2014

Abstract

This study describes an alternative development of metaheuristic approaches to automate a one dimensional problem. Extensive computational testing is done to demonstrate the effectiveness of the proposed heuristic, a Variable Neighbourhood Search (VNS)-based algorithm. Several heuristics algorithms that have been used for
solving the bin packing problem, Exact algorithm, Random Algorithm, First Fit Algorithm, Best Fit Algorithm, First Fit Decreasing Algorithm and Best Fit Decreasing Algorithm are incorporated into VNS and re-run for the
results. The procedures have been coded in Matlab 2010 version 7.11 and the statistic was calculated with SPSS version 17.0. This study used two classes of bin packing problem instances (uniform and triplets) available in the OR Library. Results are compared to the reference solutions or the best known lower bounds where the optimum is not known.

The results of the analysis showed that the combination with Best Fit Decreasing and First Fit
Decreasing are remarkably effective tools for solving the bin packing problem. However, First Fit Decreasing found the existing best known or optimal solution to 8 instances with the least processing time. The success of VNS with the basic algorithms indicates that the results of this study can provide an alternative heuristic for one dimensional bin packing problem.

Please request the Journal from us via the button below.

Q

Request Form

You might also be interested in