The Two-dimensional Rectangle Bin Packig Problem And Design Of Algorithm

The bin-packing problem is an important combinatorial optimization problem, which is widely applied in many industries. If we present some better algorithms to solve the bin-packing problem, it is not only the effective utilization of resources and cost savings, but also has a profound impact for various industries. The bin-packing problem is proved to be NP-complete, which has very high complexity, therefore more efficient approximation algorithms are designed to solve the bin packing prob-lem.In this thesis, we consider the two-dimensional rectangle bin-packing problem. Motivated by Lodi et al’s a4-approximation algorithm, we make some modifications based on the algorithm, i.e. under the conditions that height of strip bin containing items is more highly fine division and items are divided to three classes, then we design a3-approximation algorithm to solve this problem, and prove correctness of algorithm. Moreover, we analyse complexity of algorithm and then implement program of algorithm.