An efficient deterministic heuristic algorithm for the rectangular packing problem

This paper presents a deterministic heuristic algorithm for solving the NP-hard two-dimensional rectangular packing problem with the objective of maximizing the filling rate of a rectangular sheet. The key component of the proposed algorithm is a best-fit constructive procedure, according to which, the rectangles are packed into the sheet one by one and each rectangle is packed into the sheet by an angle-occupying placement with maximum fit degree. To further improve the algorithm's searching ability, a look-ahead strategy and a multistart method are introduced. The proposed algorithm is evaluated on five sets of 112 well-known test instances, and the computational results disclose that the proposed algorithm is competitive with the current state-of-the-art algorithms. The effects of the essential components of the proposed algorithm are investigated by a series of experimental analysis. Additionally, we adapt the proposed packing strategy to solve a variant of 2DRP, the constrained two-dimensional cutting (or packing) (CTDC) problem. Computational experiments on 21 classical CTDC problem instances and comparisons with two state-of-the-art algorithms verifies the effectiveness and efficiency of the adapted algorithm.