The Variable-capacity Bin Packing Problem

The one-dimensional bin packing problem is to pack a list of items into bins of unit capacity, its objective is to minimize the number of the bins used. In this thesis, we study a generalization of the one-dimensional bin packing problem, i.e. the variable-capacity bin packing problem. It is defined as follows:given a list L=(a1,a2,..., an) of n items, each item ai with size s(ai)∈(0,1], where i=1,2,...,n, and given an inexhaustible supply of bins with k different types, each type of bin with capacity s(Bj)∈(0,1], where j=1,2,..., k, we are asked to put these n items into some bins, and the sum sizes of the items in each bin can not exceed the capacity of the bin. The objective is to minimize the sum capacities of the bins used.For the variable-capacity problem, Friesen and Langston designed three effi-cient asymptotic approximation algorithms, i.e. NFL algorithm, FFDLR algorithm and FFDLS algorithm, their asymptotic approximation values were respectively2,3/2,4/3. In this thesis, we modify some strategies of the FFDLS algorithm, then design a5/4-asymptotic approximation algorithm, its complexity is O(nlogn).