Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
Debajit Sensarma*1, Samar Sen Sarma*2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems. The main objective of the problem is to minimize the number of bins used and pack the items with different sizes in finite number of bins efficiently. This paper introduces a new graph based algorithm for one dimensional bin packing problem. The proposed algorithm is implemented and tested with the well known benchmark instances and a comparison with existing First-Fit Decreasing (FFD) algorithm is given with respect to number of bins and waste space. In most of the cases the new algorithm produces near optimal solutions and performs better than FFD.
Keywords |
| Graph, Bin Packing Problem, Combinatorial Optimization, Heuristics |
INTRODUCTION |
In one-dimensional Bin Packing Problem, a sequence of
items L = (a1, a2, …, an) is given, each of size S(ai), i=1,.., n and
the goal is to pack them into minimum number of bins with pre
specified capacity C (i.e. partition them into a minimum
number m of subsets B1, B2, …, Bm such that  1≥ j≥ m). In the view of constraint satisfaction problem Bin
Packing problem is a problem of partitioning the set L under a
sum constraint i.e. divide L into a minimum number of blocks,
called bins such that the sum of sizes of the items in each bin is
at most a given capacity C>0. There are various real world
applications of bin packing problem e.g. stock cutting problem,
Television programming problem, computer storage allocation
problem, Transportation problem. In many of the problems Bin
Packing has been presented as the primary combinatorial
optimization problem, secondary problem or an embedded
special case. For example, in container loading problem Bin
Packing is embedded. |
| Bin packing can be defined in several ways. One classification is based on their dimension. There is onedimensional, two-dimensional, three-dimensional and multidimensional Bin packing. On the other hand the problem has two types of packing, fixed sized Bin packing problem and variable sized Bin packing problem. In case of the fixed sized, the bin capacity is fixed and it may not have different capacity. The objectives are: |
| i) To minimize the number of bins that will not exceed its capacity. |
| ii) To minimize the Waste Space. |
| iii) To minimize the time of execution. |
| In case of variable sized packing problem the capacity of the bins varies. The objective is to pack the items with above constraints and minimizing the cost associated with the chosen bins. |
| The paper is organized as follows. Section 2 gives the problem formulation. The existing algorithms of Bin Packing Problem are depicted in section 3. In section 4 the proposed algorithm is described. The experimental results are given in section 5 and section 6 concludes the paper. |
2. PROBLEM FORMULATION |
| Given „B‟ identical bins of capacity „C‟ and a list of n items with sizes a1, a2,…, an to pack and a compatibility graph G (V, E), where V is the set of size of the items and E is the set of edges such that (i, j) E if item i and j are compatible (i.e. S (i) + S (j) V). The problem is to assign items to bins, using a minimum number of bins, while ensuring that the total size of the items assigned to a bin does not exceed the bin capacity C and that two items that are compatible are assigned to the same bin. The number B is assumed to be large enough to guarantee feasibility; more precisely it is a valid upper bound on the number of bins in an optimal solution (note that B n). The possible integer programming formulation of the problem is: |
 |
| Where k y =1 if bin k is used, 0 otherwise and ik x =1 if item i is put into bin k, 0 otherwise. |
| In the Constraint (i) the objective function is to minimize the total number of bins and pack all the items with identical capacity. Constraint (ii) guarantees that the size of items ( i a ) filled in the bin k do not exceed the bin capacity. Constraint (iii) ensures that each item is placed only in one bin. Constraint (iv) formulate the compatibility. |
3. BIN PACKING ALGORITHMS |
| Bin packing is a NP-Hard problem [1, 2]. Many heuristic and approximation algorithms have been proposed to reach the near optimal solution. Mainly the algorithms are online and offline. |
| On-line algorithms permanently assign the objects to a bin in the sequence they arrive. There is an initial condition for all the on-line heuristics that the first object is already packed bin. There are various online algorithms. Some of them are: |
A. Next Fit Heuristic . |
| In this algorithm items are placed in the order in which they arrive. The task is to place the next item as well as it arrives into the current bin if it fits, otherwise close that bin and start a new bin. |
B. First Fit Heuristic . |
| In this algorithm items are placed in the order in which they arrive. As soon as the item arrives, the algorithm places the item into the lowest numbered bin in which it fits. If the item does not fit into any open bin, start a new bin. |
C. Best Fit Heuristic . |
| This algorithm place the items in the order in which they arrive. Place the next item into that bin which will leave smallest residual capacity after the item is placed in the bin. If item does not fit in any bin, start a new bin. |
D. Worst Fit Heuristic . |
| This algorithm places the items in the order in which they arrive and place the next item into that bin which will leave the largest residual capacity after the item is placed in the bin. If it does not fit in any bin, start a new bin. |
| Off-line algorithms have all the objects available before the packing starts. Two well known off-line algorithms are described below: |
E. First Fit Decreasing Heuristic . |
| The algorithm first Sort the items in decreasing order then place the next item into the lowest numbered bin in which it fits. If it does not fit into any open bin, start a new bin. |
F. Best Fit Decreasing Heuristic . |
| The algorithm first sort the items in decreasing order and place the next item into that bin which will leave the smallest residual capacity after the item is placed in the bin. If it does not fit in any bin, start a new bin. |
| Besides the development of approximation algorithms for the classical problem [4], there exist some variants of the problem. (a) Bin Packing Problem with number of items maximized. [5] (b) Bin Packing Problem with a bound on number of items can be packed in each bin. [6] (c) Class constrained Bin Packing Problem. [8] (d) Dynamic Bin Packing Problem. [7] (e) Bin Packing with constrained on data. [9, 10] (f) Bin stretching problem. [11] |
4. PROPOSED ALGORITHM |
| The algorithm proposed here is graph [3] based. It is designed for offline one dimensional bin packing problem. The algorithm is a collection of two algorithms. (a) Algorithm B: Bin Counting and (b) Algorithm C: Construct Compatibility graph. Algorithm C creates the compatibility graph from the given set of sizes of the input items and Algorithm B count the number of bins required. Waste Space per bin is calculated as difference between total capacity of the bin and sum of sizes of selected item set. The algorithm finds minimal number of bins in reasonable amount of time and space. The two algorithms are depicted below. |
 |
 |
5. EXPERIMENTAL RESULTS |
The program is done on Intel® Atom™ Processor, 1.60 GHz,
1.0 GB DDR2 RAM and with Borland C++ 5.5 compiler. This section evaluates results of FFD algorithm and the
proposed algorithm with respect to i) Number of bins ii) Waste |
| Here j y is sum of sizes of items in bin j, C= capacity of each bins. The test instances are taken from the OR-library [12]. The benchmark datasets are divide into three classes; easy, medium and hard class instances. Table-I contains the results of easy instances. Out of 5 instances the proposed algorithm produces optimal solution for all but FFD produces for 3 instances. Table-II contains results for the medium class instances. Out of 5 instances proposed algorithm produces optimal solution for 4 instances and near optimal solution for 1 instance but FFD produces optimal solution for only 1 instance. Lastly results of Hard class instances are shown in Table-III where out of 5 instances proposed algorithm produces near optimal solution for all 5 instances and which is better than FFD. From the above three tables its can be seen that the Waste Space (%) of the proposed algorithm is comparatively less than FFD. Here, N represents number of items, C represents bin capacity. We have chosen q= 2, 3, 4, 5. |
 |
 |
6. CONCLUSION |
| In this paper a heuristic is proposed to tackle one-dimensional bin packing problem. The proposed algorithm is a graph based offline algorithm. A compatibility graph is constructed from the set of item sizes where item sizes are acts as nodes of the graph and two nodes as connected if they are compatible with respect to a capacity constraint. Experiment on some problem instances show the supremacy over existing offline FFD algorithm with respect to number of bins and total waste space. |
| In future we will experiment the proposed algorithm with other instances and will try to apply the algorithm in real life problem solving. |
ACKNOWLEDGMENT |
| The authors would like to thank University Of Calcutta, West Bengal, India, Department of Science & Technology (DST), New Delhi, for financial support and the reviewers for their constructive and helpful comments and specially the Computer without which no work was possible. |
References |
|