Wednesday, October 15, 2008

Bin Packing Heuristics

by Your Name 0 comments

Tag


Share this post:
Design Float
StumbleUpon
Reddit

Abstract—The bin packing problem is well known as an NP-hard problem. Our project analyzes polynomial-time approximation algorithms, i.e., algorithms that construct packing that use relatively few bins, although not necessarily the smallest possible number. We will try to analyze the efficacy of various approximation algorithms by implementing in a software. We will make an empirical study of various approximation algorithms by generating test cases and eval- uate the performance of the algorithms by comparing these approximation algorithms against each other and see how close each of them gets to optimal solution.

Keywords- Bin packing, Empirical study of algorithms, Heuristics, Operational complexity, Run time complexity, Approximation algorithm.

 INTRODUCTION

Bin packing problem is known to be NP-hard. Therefore the research focus has been on approximation algorithms. Approximation algorithms are algorithms used to find approximate solutions to optimization problems. In the classical one-dimensional bin packing problem, one is given a list of elements, with an element height for each element in the list. One desires to pack the elements into a minimum number of fixed capacity (of capacity bin height) bins. In other words this problem can be translated as a partition of the items into disjoint subsets such that the sum of the sizes of the items in each subset is no more than the bin size, and such that the number of the bins used is as small as possible. This problem finds many industrial applications such as filling up containers, loading trucks with weight capacity, and creating file

backup in removable media.The approximation algorithms use heuristics. A heuristic is a method to help solve a problem in an informal way by using educated guesses, intuitive judgments or simply common sense. Heuristics give a solution that is usually reasonably close to the best possible answer. By using heuristics in bin packing problem we can accomplish results which, though very good in most cases, may not be the optimal solution.

Heuristics help us make algorithms that compromises with the optimal solution for an improvement in run

time. Each approximation algorithm that is used for bin packing will make a choice between good running time and proximity to optimal solution for different number of object quantities.

PROJECT OBJECTIVE

To make an empirical study of the performance of different approximation algorithms for the bin packing

problem and, to evaluate the experimental performance against the claimed theoretical performance and compare the various algorithms.

 PROJECT METHODOLOGY

1) To design and implement a system which incorporates alternative approximate algorithms for the bin

packing problem

2) Simulate the system with suitable family of test cases.

3) Analyze the results and evaluate the performance of each approximation algorithm against each other.

 SYSTEM DESCRIPTION

Basically the whole system is divided into 3 modules.

1) Problem Generator:

• Given the number n of objects to be packed, this module randomly generates n objects whose height lies between 0 and 1.

• The option to select the distribution from which the element heights are to be selected is also

given in automatic element generation.

 • The option to enter the height of the n objects manually is also provided.

2) Simulator:

• Given an array of n objects to be sorted into bins, this module utilizes the different approximation

algorithms to carry out the sorting.

• The defined parameters such as number of bins, running time, number of operations, etc are

output and stored in files.

3) Analyzer:

• Analyzes the output parameters, using statistical tools if suitable.

• Displays the analysis in suitable formats, graphs, charts etc.

 

Comments 0 comments

Subscribe feeds via e-mail
Subscribe in your preferred RSS reader

Subscribe feeds rss Recent Entries

Advertise on this site Sponsored links

Categories

Subscribe feeds rss Recent Comments

Technorati

Technorati
My authority on technorati
Add this blog to your faves