Heuristic Placement Routines For Two-Dimensional Rectangular Bin Packing Problems

Abstract

In this study, we consider non-oriented and oriented cases of Two-Dimensional Rectangular Bin Packing Problems where a given set of small rectangles is packed without overlaps into a minimum number of identical large rectangles. In non-oriented case the rectangles are allowed to be rotated at 90° while the rectangles have fixed orientation in oriented case. We propose new heuristic placement routines called the Improved Lowest Gap Fill (LGFi) (for nonoriented case) and LGF􀝅􀯈􀮿 (for oriented case) for solving the non-oriented and oriented cases of the problems respectively. These new approaches dynamically select the best rectangle for placement during the packing stage. Extensive computational experiments are conducted using benchmark problem instances proposed in the literature. The results show that the proposed routines are competitive when compared with other heuristic placement routines. The Two Factors Factorial Design Repeated on Both Factors is used to analyse the computational results using SAS package. The statistical result of the non oriented case shows that Floor Ceiling, Lowest Gap Fill, Touching Perimeter and LGFi which are not significantly difference and their performance are better than the Bottom-Left Fill. The statistical result of the oriented case indicates that Alternate Direction, Floor Ceiling and LGF􀝅􀯈􀮿 are not significantly difference. This means that three of these heuristic placement routines are equally good. However, these results are not that efficient because the normality assumptions of the error of the model are not met. This maybe due to the present of the unexpected outliers in the error terms.