A survey on bin packing problems and their heuristic algorithms
This thesis gives a survey of the bin packing problems. Bin packing problems address the problem of packing a given set of items into a minimum number of bins. Further, a discussion of some heuristic and approximation algorithms that provide good and feasible solutions to the bin packing problems is...
Saved in:
| Main Author: | |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Animo Repository
2001
|
| Online Access: | https://animorepository.dlsu.edu.ph/etd_bachelors/17166 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Language: | English |
| Summary: | This thesis gives a survey of the bin packing problems. Bin packing problems address the problem of packing a given set of items into a minimum number of bins. Further, a discussion of some heuristic and approximation algorithms that provide good and feasible solutions to the bin packing problems is given to address this NP-hard problem which, in practice, is extremely difficult to solve.
The researcher zeroes in on the discussion of the three-dimensional bin packing problem--the generalization of the one- and two-dimensional bin packing problem--which is the least discussed, analyzed, and understood among the three types of bin packing problem. In addition to the presentation of an approximation algorithm for the three-dimensional bin packing problem, lower bounds which could be used to estimate the optimum solutions to instances of the three-dimensional bin packing problem were presented and discussed based on the formula given by Silvano Martelo, David Pisinger, and Daniele Vigo (2000) in their article entitled "The Three-Dimensional Bin Packing Problem". |
|---|