Heuristic placement routines for two-dimensional bin packing problem.
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 wher...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Science Publications
2009
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/14998/ http://psasir.upm.edu.my/id/eprint/14998/1/Heuristic%20placement%20routines%20for%20two.pdf |
| _version_ | 1848842554094649344 |
|---|---|
| author | Wong, L. Lee, Lai Soon |
| author_facet | Wong, L. Lee, Lai Soon |
| author_sort | Wong, L. |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T08:00:58Z |
| format | Article |
| id | upm-14998 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-15T08:00:58Z |
| publishDate | 2009 |
| publisher | Science Publications |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-149982015-10-22T00:58:38Z http://psasir.upm.edu.my/id/eprint/14998/ Heuristic placement routines for two-dimensional bin packing problem. Wong, L. Lee, Lai Soon 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. Science Publications 2009 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/14998/1/Heuristic%20placement%20routines%20for%20two.pdf 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 10.3844/jmssp.2009.334.341 English |
| spellingShingle | Wong, L. Lee, Lai Soon Heuristic placement routines for two-dimensional bin packing problem. |
| title | Heuristic placement routines for two-dimensional bin packing problem. |
| title_full | Heuristic placement routines for two-dimensional bin packing problem. |
| title_fullStr | Heuristic placement routines for two-dimensional bin packing problem. |
| title_full_unstemmed | Heuristic placement routines for two-dimensional bin packing problem. |
| title_short | Heuristic placement routines for two-dimensional bin packing problem. |
| title_sort | heuristic placement routines for two-dimensional bin packing problem. |
| url | http://psasir.upm.edu.my/id/eprint/14998/ http://psasir.upm.edu.my/id/eprint/14998/ http://psasir.upm.edu.my/id/eprint/14998/1/Heuristic%20placement%20routines%20for%20two.pdf |