A survey on bin packing problems and their heuristic algorithms

• Main Author: Li, Elizabeth
• Format: text
• Language: English
• Published: Animo Repository 2001
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/17166
• Institution: De La Salle University

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".