The Variable-cost Bin Packing Problem

The bin packing problem is a classical combinatorial optimization problem. In the one-dimensional bin packing problem, we are given a list L of n items whose sizes belong to (0,1] and a list of unit capacity bins, we are asked to pack all items into unit capacity bins such that the sum of sizes of the items in a bin does not exceed1, the objective is to minimize the number of bins used.The variable-cost bin packing problem is a generalization of the one-dimensional bin packing problem, it can be formatted as follows:we let L be a set of n items whose sizes belong to (0,1] and are given k types of bins, the capacity and the cost of bins may vary, each type bin is inexhaustible, the capacity of bins belongs to (0,1], it is asked to pack all items into bins such that the sum of sizes of the items in a bin does not exceed the capacity of the bin, the objective is to minimize the sum of costs of bins used.In this thesis, using the strategy of the FFD algorithm, we design an asymp-totic approximation algorithm to solve the variable-cost bin packing problem. We obtain conclusions:(1) the asymptotic performance value of the algorithm is2;(2) In two special circumstances, the asymptotic performance values of the algorithm are3/2, its complexity is O(nlogn). Finally, we give the MATLAB program of the algorithm and use it to realize the example.