A Steplike Stacking Heuristic Algorithm for Solving Rectangle Packing Problem

A steplike stacking algorithm was proposed to solving 2D rectangular packing problem. The algorithm was based on a steplike heuristic rule and probabilistic backtracking algorithm. The algorithm can give satisfactory results for solving both the maximum packing problem given a fixed width and fixed height container and the minimum height packing problem given a fixed width rectangle container. For the zero-wasted problem, the algorithm spends less on finding the optimal solution than other methods. It also demonstrated fairly good performance in solving none-zero-waste problems. Three well known test cases were executed, and verified that our proposed algorithm was very effective.