Conceptions Related To Bin Packing Computer Science Essay

Published:

In this chapter we present conceptions related to Bin packing. This chapter goes through the Variety of combinatorial optimization questions where the set of feasible solution is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. The packing problems which we study are theoretical, but serve as benchmarks to many algorithmic techniques. The Ideas which originated in the study of the bin packing problem have helped shape computer science as we know it today.

A well known packing problem which is one of the oldest and most thoroughly studied problems in computer science and combinatorial optimization is the bin packing algorithm which is a combinatorial NP- hard problem.

The importance of this problem is that it has spawned off whole areas of research, including the field of approximation algorithms. The bin packing optimization problem packs a set of object into finite number of bins of capacity V in a way that minimizes the number of bins used. We intend to concentrate on number of problems which have many important applications in areas such as multi processor scheduling, resource allocation, packet routing, paged computer memory systems, storage, multiprocessor scheduling, stock cutting, loading trucks with weight capacity, creating file backup in removable media and technology mapping in FPGA implementation of custom hardware and many others.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

In this research proposal we discuss theoretical problems which include the classical bin packing problem, for general and restricted inputs. We present this problem as well as its application in storage. The classical bin packing problem models a situation when a set of items( having scalar sizes, which can be seen as size of files that needs to be stored on disks), need to be partitioned into subsets of total size at most 1( called bins). Bins can be seen as disks of size 1(assuming that all sizes were scaled). The goal is to minimize the number of bins (or disks). Restricted inputs of this problem include the parametric case, where sizes of items are much smaller than the size of recipients. Other generalizations are variable- sized bin packing (where bins of several sizes are available) and cardinality constrained bin packing(when a limited number of items can be placed in each bin).

Thesis Overview

CHAPTER 2

PRELIMINARIES

Bin packing

The classical one dimensional bin packing has long served as a proving ground for new approaches to analysis of approximation algorithms. The classical bin packing problem, which we discuss first, was one of the first combinatorial optimization problem which was introduced in early 1970's. We are given a sequence of items ={1,2,…,n} with sizes s1, s2,…,sn€ (0,1]. The goal is to find a partition of the items into sets called bins, where the total size of each set is at most 1, so that the number of sets in the partition is minimized.

Further, the sum of the sizes of the pieces assigned to any bin may not exceed its capacity. A bin is empty if no piece is assigned to it, otherwise it is used. We say that an item that belongs to a given bin(set) is "packed" into this bin. The goal is to minimize the number of bins used. Basically, we want to find an algorithm which incurs cost which is within a constant factor of the minimum possible cost, no matter what the input is. For the classic bin packing problem can have a cost within a constant factor r of the minimum number of required bins for r < 3/2 unless P=NP. This constant factor is known as the asymptotic performance ratio. We define the asymptotic performance ratio more precisely. For a given input sequence σ, let be the sum of the capacities of the bins used by algorithm A on σ. Let cost(σ) be the minimum possible cost to pack pieces in σ. The asymptotic performance ratio for an algorithm A is defined to be

Approximation algorithms for classical Bin packing:

The first studies of the bin packing problem suggested natural and easy to implement algorithms First Fit(FF) and Next Fit(NF). These algorithms assume an arbitrary ordering of the input.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

For the general bin packing algorithm we assume that the entire list and its item sizes are known before the packing begins. A common situation is where the items arrive in some order, and must be assigned to a bin as soon as they arrive, without knowledge of the remaining items. A bin packing algorithm that can construct its packing under the regime is on-line bin packing for which items in the list must be processed in exactly the same order as they are given, one at a time. The on-line processing is difficult owing to unpredictable item sizes that may appear. In general, the performance of an on-line bin-packing algorithm is substantially affected by the permutation of items in a given list. In fact, it's easy to convince ourselves that a ONLINE algorithm cannot always get the optimal solution.

The NEXT-FIT and FIRSTFIT are two well-known and simplest on-line bin-packing algorithms where that r(NEXT-FIT) = 2, while the proof of r(FIRST-FIT) = 1.7

Next fit: The simplest algorithm for classical one dimensional bin packing problem is Next Fit which is a bounded space online algorithm in which the only partially filled bin that is open is the most recent one to be started This algorithm starts at the beginning of the Elements array and steps through each one.  Once Bin 1 is full, it moves on and starts placing elements into Bin 2, never looking back to see if an Element in the future may fit inside Bin 1.  This process continues until there are no more Elements.  This is least efficient of the algorithms but it does have a practical benefit. For instance, consider the conveyor belt placing items in boxes to be shipped to a single customer.  You wouldn't want to have to reverse the conveyor belt to go back to a partially empty box to fit in an item that the customer ordered. For FF, no matter how the items are ordered, all the "-items are placed in the same bin. In total, at most one bin is not completely filled, and FF uses at most n(t - ½)+ 1 bins. For increasingly large n, the ratio approaches from below. Johnson showed that Approximation ratio is 2 which runs in a linear time.

For easy understanding of Next Fit

Description: This heuristic places the next item in the currently open bin. If it does not fit the bin is closed and a new bin is opened

Initialization:

Given a list of item weights L={ .

Place item 1 in bin 1and remove L. let i=1. j=2.

Iterations:

If item j fits in bin I, place j in i. If not open a new bin i+1 and place j in bin i+1. Let i=i+1

Remove item j from L. Let j = j+1.

While items remains in L, repeat from Step 1.

Lets take an example of (using Bin Height = 80, Elements = {26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 3 512 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68})

http://www.developerfusion.com/res/content/5540/Next%20Fit/

Here the graph represents

 Bin Numbers along the bottom, Bin Height/Amount along the left side, Actual Fill Amount along the top, Individual Element Amount inside entirely and of bars. 

Theorem: If M is the number of bins in the optimal solution, then Next Fit never uses more than 2M bins. There exist sequences that force Next Fit to use 2M-2 bins.

Proof.

Consider any two adjancent bins. The sum of items in these two bins must be > 1; otherwise, NextFit would have put all the items of second bin into the first. Thus, total occupied space in (B1 + B2) is > 1. The same holds for B3+B4 etc....

Thus, at most half the space is wasted, and so Next Fit uses at most 2M bins.

For the lower bound, consider the sequence in which si = 0.5 for i odd, and si = 2/N for i even. (Suppose N is divisible by 4.)Then, the optimal puts all 0.5 items in pairs, using N/4 bins. All small items fit in a single bin, so the opt is N/4 + 1. Next Fit will put 1 large, 1 small in each bin, requiring N/2 bins.

Lower Bound:

0.5 0.5 ... 0.5 2/N

0.5 0.5 ... 0.5 2/N

...

B1 B2 B_{N/4} B_{N/4 + 1}

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

empty empty ... empty empty

2/N 2/N 2/N 2/N

0.5 0.5 0.5 0.5

B1 B2 B_{N/2}

First Fit

 The algorithm processes the items in arbitrary order. In the First Fit algorithm restriction is removed entirely and we consider all partially filled bins as possible destinations for the item to be packed. In this algorithm the particular rule is followed: First we place an item in the first called lowest indexed bin into which it will fit , i.e.., if there is any partially filled bin with level ()+s() 1, then we place in the lowest indexed bin. Otherwise, we start a new bin with as its first item. In simple terms we can say that, For each item, it attempts to place the item in the first bin until the items are accomodated. If no bin is found, it opens a new bin and puts the item within the new bin. This algorithm achieves an approximation factor of 2.  This is due to the observation that at any given time, it is impossible for 2 bins to be at most half full. The reason is that if at some point a bin was at most half full, meaning it has at least a space of V / 2, the algorithm will not open a new bin for any item whose size is at most V / 2. Only after the bin fills with more than V / 2 or if an item with a size larger than V / 2 arrives, the algorithm may open a new bin. Thus if we have B bins, at least B − 1 bins are more than half full. therefore  > V Because  is a lower bound of the optimum value OPT, we get that B − 1 < 2OPT and therefore B ≤ 2OPT[1]. It is possible to construct the First Fit packing in time O(nlogn) using an appropriate data structure which is the best possible for a comparision based implementation, since one can use the first fit packing rule to sort. FIRST-FIT is an O(n)-space algorithm, since in this case all nonempty bins remain active until the end of the processing. A question was raised by Johnson [6] as to whether or not there exists a polynomial-time on-line algorithm A better than FIRST-FIT (i.e., with r(A) < 1.7). and was recently resolved by Yao. To be precise, Yao has presented an algorithm, dubbed REFINED FIRST-FIT, with a worst-case performance ratio of 5/3 = 1.666 . . . , which is the best ratio achieved by an on-line bin packing algorithm .In addition to the performance ratio, we also consider the time and the space complexity of on-line bin-packing algorithms. We use TA(n) to denote the total time required by on-line bin-packing algorithm A to pack the list L whose size is n, and refer to algorithm A as a TA(n)-time algorithm. Thus, NEXT-FIT is an O(n)-time algorithm, whereas FIRST-FIT and REFINED FIRST-FIT are both

O(n log n)-time algorithms. For convenience, a nonempty bin during the processing is called "filled" if it is not intended to pack any more items and "active" if it is. Using the uniform cost criterion for space, we need one storage location for each active bin. As soon as a bin becomes filled, it is among the output of the algorithm used, and we do not count its storage location in defining the space complexity of the algorithm. Specifically, we use SA(n) to denote the maximum number of storage locations (for active bins) needed by algorithm A during the processing of the list L whose size is n, and refer to algorithm A as an SA(n)-space algorithm. For example, NEXT-FIT is an 0( I)-space algorithm, since it involves only one active bin at all times, and FIRST-FIT is an O(n)-space algorithm, since in this case all nonempty bins remain active until the end of the processing.

For easy understanding of First fit

Description: This keeps all unfill bins open. It places the next item in the lowest numbered bin in which the item fits. It it does not fit in any bin, a new bin is opened.

Initialization:

G Given a list of item weights L={ .

Place item 1 in bin 1and remove L. let i=1. j=2.

Iterations:

Find the lowest numbered bin I in which item j fits, and place j in i. If I does not fit in any bin, open a new bin and number it m+1, let m=m+1, and place j in bin m+1.

Remove item j from L. Let j=j + 1.

While items remain in L, repeat from Step 1.

With the same set of data as the last example, this algorithm will lay out something like this in memory: 

http://www.developerfusion.com/res/content/5540/First%20Fit/

Theorem: First Fit never uses more than 2M bins, if M is the optimal.

Proof. At most one bin can be more than half empty: otherwise the

contents of the second half-full bin would be placed in the first.

Theorem: If M is the optimal number of bins, then First Fit never uses more than 1.7M bins. On the other hand, there are sequences that force it to use at least 17/10 (M-1) bins.

The upper bound proof is quite complicated.

We show an example that forces First Fit to use 10/6 times optimal. Consider the sequence: 6M items of size 1/7 + e; followed by 6M items of size 1/3 + e; followed by 6M items of size 1/2 + e. Optimal strategy is to pack each bin with one from each group, requiring 6M bins. When First Fit is run, it packs all small items first, in 1 bin. It then packs all medium items, but requires 6M/2 = 3M bins. (Only 2 per bin fit.) It then requires 6M bins for the large items. Thus, in total First Fit uses 10M bins.

empty empty empty

1/7

1/7

...

1/7 1/3

1/7

1/7

...

1/7 1/3 + e

1/7 1/3 + e 1/2 + e

Best Fit:

It is the best known algorithm for on-line bin packing which emerges as the winner among the various online algorithms: It is simple which behaves well in practice, and no algorithm beats both worst case and the average uniform case. we study the expected performance ratio, taking the worst-case multiset of items L, and assuming that the elements of L are inserted in random order. Here lower bound acquires an approximation ratio of 1.08 . . . and an upper bound of 1.5 Any on-line bin-packing algorithm has performance ratio at least 1.54 in which case Best fit has an approximation ratio of 1.7 which is same as First Fit and in the average uniform case the items generally draw in the interval[0,1] (then Best-fit has expected wasted space O(n'/2(log n)"/")). But the worst-case performance ratio and

the uniform-distribution performance ratio are not quite satisfactory measures for evaluating on-line bin-packing algorithms.

The BF algorithm picks the Bin with the least amount of free space in which it can still hold the current Element. 

For easy understanding Best Fit algorithm cam be wriiten as:

Description:

This algorithm tries to create the fullest bin possible each time an item is assigned. All unfill bins are kept open.It plces the next item j in the bin whose current contents are largest, but should not exceed Q-. If it does not fit in any bin , new bin is opened.

Initialization:

Given a list of item weights L={ .

Place item 1 in bin 1 and remove from L. let j=2, m=1.

Iterations:

Find the bin i whose remaining capacity is minimum but greater than (if are the items in bin i, is the remaining capacity of bin i) and place j in i. If j does not fit in any bin, open a new bin and number it m+1, place j in bin m+1 and let m=m+1

Remove item j from L. Let j=j + 1.

While items remain in L, repeat from Step 1.

Lets take an example of (using Bin Height = 80, Elements = {26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 3 512 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68})

http://www.developerfusion.com/res/content/5540/Best%20Fit/

It is east to implement in O(N log N) time.

Best Fit and First Fit never uses more than 1.7 times optimal.

Offline algorithms:

If no limit on re-packing is imposed then we perform offline algorithms, it does simply be re packing everything according to algorithm each time an item arrives.s