UPM Institutional Repository

Heuristic placement routines for two-dimensional bin packing problem.


Wong, L. and Lee, Lai Soon (2009) Heuristic placement routines for two-dimensional bin packing problem. Journal of Mathematics and Statistics, 5 (4). pp. 334-341. ISSN 1549-3644


Problem statement: Cutting and packing (C and P) problems are optimization problems that are concerned in finding a good arrangement of multiple small items into one or more larger objects. Bin packing problem is a type of C AND P problems. Bin packing problem is an important industrial problem where the general objective is to reduce the production costs by maximizing the utilization of the larger objects and minimizing the material used. Approach: In this study, we considered both oriented and non-oriented cases of Two-Dimensional Bin Packing Problem (2DBPP) where a given set of small rectangles (items), was packed without overlaps into a minimum number of identical large rectangles (bins). We proposed heuristic placement routines called the Improved Lowest Gap Fill, LGFi and LGFiOF for solving non-oriented and oriented cases of 2DBPP respectively. Extensive computational experiments using benchmark data sets collected from the literature were conducted to assess the effectiveness of the proposed routines. Results: The computational results were compared with some well known heuristic placement routines. The results showed that the LGFi and LGFiOF are competitive when compared with other heuristic placement routines. Conclusion: Both LGFi and LGFiOF produced better packing quality compared to other heuristic placement routines.

Download File

PDF (Abstract)
Heuristic placement routines for two.pdf

Download (83kB) | Preview

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
Institute for Mathematical Research
DOI Number: https://doi.org/10.3844/jmssp.2009.334.341
Publisher: Science Publications
Keywords: Bin packing problem; Heuristic placement; Cutting and packing.
Depositing User: Najwani Amir Sariffudin
Date Deposited: 02 May 2014 07:09
Last Modified: 22 Oct 2015 00:58
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.3844/jmssp.2009.334.341
URI: http://psasir.upm.edu.my/id/eprint/14998
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item