Some Researches About Bin Packing Problem

Bin packing problem not only has values in theory but also finds many practical applications in real life. We know that bin packing problem is NP—hard, so the method of solving this problem is to find its approximate solution only. The new approximation algorithms, LSCPF-A(Long Same Color Packed First) and JCBP, to solve the coloring BPP is proposed in this paper. After classifying the objects according to the same colors, the LSCPF-A algorithm packs the objects in the same class with the most firstly. After classifying the objects according to the same colors, the SCPF-A (Same Color Packed First) algorithm packs the objects in the same class with the same color firstly. After arranging the objects according to the length, JCBP packs the objects from two sides. Experiment shows better results and fewer boxes for LSCPF-A than that for SCPF-A algorithm. A demonstration is also made to show the better performance ratio of LSCPF-A in theory. But JCBP can reach the optimal solutions in many cases. This paper also formulates a three-dimensional strip-packing problem as a nonlinear programming problem and establishes the first-order optimality conditions for the nonlinear programming problem.