Heuristics for two-dimensional strip packing problem with 90° rotations

• Proposes a constructive phase based on the greedy placement and a partial tree search phase based on the backtracking strategy.
• Proposes a new sorting rule for all candidate placements based on the definition of action space in a greedy constructive phase.
• Attained highly competitive results in comparison with the state-of-the-art algorithms in the literature.

This paper proposes a deterministic heuristic algorithm (DHA) for two-dimensional strip packing problem where 90° rotations of pieces are allowed and there is no guillotine packing constraint. The objective is to place all pieces without overlapping into a strip of given width so as to minimize the total height of the pieces. Based on the definition of action space, a new sorting rule for candidate placements is proposed such that the position for the current piece is as low as possible, the distance between the current piece and other inside pieces is as close as possible, and the adverse impact for further placements is as little as possible. Experiments on four groups of benchmarks showed the proposed DHA achieved highly competitive results in comparison with the state-of-the-art algorithms in the literature. Also, as a deterministic algorithm, the DHA could achieve high quality solutions by only one independent run on both small-scale and large-scale problem instances and the results are repeatable.