Title

A survey on bin packing problems and their heuristic algorithms

Author

Elizabeth Li

Date of Publication

2001

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics Department

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

Abstract Format

html

Language

English

Format

Print

Accession Number

TU10728

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

66 leaves

This document is currently not available here.

Share

COinS