A effective heuristic algorithm for two-dimensional rectangle-packing problems

This paper presents a new heuristic algorithm (NHA) for a two-dimensional rectangle-packing problem. First, we present a space selecting strategy which determines the packing space. Then a fitness strategy is proposed to determine which rectangle is to be packed first into the packing space. Finally, a two-lever greedy search strategy is designed to enhance the accuracy for selecting the packed rectangle. The approach is tested on large sets of test instances from the literature and compared with other approaches. Computational results obtained in less than 60 seconds of computation validate the quality of the solution and the effectiveness of the proposed algorithm.