In the classical bin packing problem one receives a sequence of n items 1, 2,..., n with sizes s1, s2, . . . ,sn where each item has a fixed size in (0, 1]. One needs to find a partition of the items into sets of size1, called bins, so that the number of sets in the partition is minimized and the sum of the sizes of the pieces assigned to any bin does not exceed its capacity. This combinatorial optimization problem which is NP hard has many variants as well as online and offline versions of the problem. Though the problem is well studied and numerous results are known, there are many open problems. Recently bin packing has gained renewed attention in as a tool in the area of cloud computing. We give a survey of different variants of the problem like 2D bin packing, strip packing, bin packing with rejection and emphasis on recent results. The thesis contains a discussion of a newly claimed tight result for First Fit Decreasing by Dosa et.al. as well as various new versions of the problem by Epstein and others.
展开▼
