A Weighted Surplus Rectangle Algorithm for Rectangle Packing Problem

This paper presents a weighted surplus rectangle algorithm to solve two-dimensional non-guillotine rectangle packing problem. According to four weighting factors, including horizontal axis and vertical axis of the bottom left coordinate, difference value of width and height the rectangle item and the surplus rectangle, a weighted matching function is created to implement the best fit between the rectangle item and the surplus rectangle. The weight values are not fixed and dynamic, and are changed with different test instances. The particle swarm optimization algorithm with the inertial weight linear decreasing is employed to search the weight values for the best fit. Experimental results with the benchmark test instances prove that the proposed algorithm can improve the performance and decrease the packing height comparing with the original surplus rectangle algorithm.