New resolution algorithm and pretreatments for the two-dimensional bin-packing problem

The two-dimensional bin-packing (2BP) problem involves packing a given set of rectangles A into a minimum number of larger identical rectangles called bins. In this paper, we introduce the concept of dependent orientation items that have special characteristics, and give the formulation that characterizes these items. Then we propose three pretreatments for the non-oriented version of the problem. These pretreatments allow finding optimal packing of some items subsets of the given instance. They enable increasing the total area of the items and consequently the continuous lower bound. Finally, we propose a new heuristic method based on a best-fit algorithm adapted to the 2BP problem. Numerical experiments show that this method is competitive with the heuristic and metaheuristic algorithms proposed in the literature for the considered problem in respect of both the quality of the solution and the computing time.