Improved Best Fit Heuristics for Offline Not Oriented Two-dimensional Rectangular Strip Packing Problem

Abstract

Cutting and Packing problems have been recognized as a sub-discipline of operation research for more than half a century. Such problems are involved in a range of circumstances such as pallet loading, wood or glass cutting, strip packing, and positioning problems. The focus of this study is on 2D rectangular strip packing problems in which rectangle items are not oriented and guillotine constraint is not considered aiming to pack all these items without overlapping into an open-ended bin called a strip of fixed width while the objective is obtaining the minimum total height of cutting. The main aim of this paper is to introduce two proposed heuristics for solving the problem under study. The two heuristics are improved versions of the known Best Fit heuristics, Tower Checker Best Fit (TCBF) and Waste Priority Best Fit (WPBF). The performance of the proposed heuristics is tested using well-known benchmark problems. The computational analysis of the results shows that the proposed heuristics can generate near-optimal solutions to large-scale problems. In addition, the performance of the heuristics outperforms other well-known heuristics from literature by 3%.