A Quasi-Human Heuristic Algorithm for the 2D Rectangular Strip Packing Problem

Given a set of rectangular pieces and a container of fixed width and variable height, the 2D rectangular strip packing problem consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall height of the layout is minimized. It has many industrial applications such as wood or glass cutting, very large scale integration design, etc. To solve this problem, many algorithms based on different strategies have been proposed. According to the wisdom and experience of human being, a quasi-human heuristic algorithm for the 2D rectangular strip packing problem is recommended based on the existing research, some important packing strategies are presented in this paper. Twenty-one rectangle-packing, 13 random strip-packing and 10 classes strip-packing instances are used to test the performance of the algorithm developed. All of 21 rectangle-packing instances and three of 13 strip-packing instances are achieved optimal solutions, and the average relative distance of 10 classes strip-packing instances obtained by the developed algorithm is 2.28%. Experimental results demonstrate that the algorithm developed is fairly efficient in solving the 2D rectangular strip packing problem.