Heuristic Placement Routines for Two-Dimensional Bin Packing Problem
Abstract
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.
DOI: https://doi.org/10.3844/jmssp.2009.334.341
Copyright: © 2009 L. Wong and L. S. Lee. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,127 Views
- 3,240 Downloads
- 10 Citations
Download
Keywords
- Bin packing problem
- heuristic placement
- cutting and packing