Rectangle-packing problem involves many industrial applications, such as shipping, timber cutting, very large scale integration (VLSI) floor planning, and so on. This problem has shown to be NP hard, and many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on the wisdom and experience of human being, an efficient heuristic algorithm is proposed in this paper. Two group benchmarks are used to test the performance of the produced algorithm, 19 instances of first group and 3 instances of second group having achieved optimal solutions. The experimental results demonstrate that the presented algorithm is rather efficient for solving the rectangle-packing problem.
Rectangle-packing problem involves many industrial applications. For example, in shipping industry, various size boxes have to be loaded as many as possible in a larger container. In wood or glass industries, rectangular components have to be cut from large sheets of material. In very large scale integration (VLSI) floor planning, various chips have to be laid on the chip board, and so on. The rectangle-packing problem belongs to a subset of classical cutting and packing problems and has shown to be NP hard [1]. For more extensive and detailed descriptions of packing problem, please refer to [2] and [3]. Various algorithms based on different strategies have been suggested to solve this problem. In general, these algorithms can be classified into two major categories: non-deterministic algorithms and deterministic algorithms. The key aspect of non-deterministic algorithms, such as simulated annealing and genetic algorithm [4] and [5], is to design data structure that can represent the topological relations among the rectangles. The key aspect of deterministic algorithms is to determine the packing rules, such as less flexibility first principle [6].
Optimal algorithm for orthogonal two-dimensional cutting is proposed in [7], but it might not be practical for large problems. In order to improve the quality of solution, some scholars combine genetic algorithm or simulated annealing with deterministic method and obtain hybrid algorithms [8] and [9]. Some heuristic and meta-heuristic algorithms are presented in [10], [11], [12] and [13]. In recent years, some people began to formalize the wisdom and experience of human being and obtain the quasi-human heuristic algorithms [6], [14], [15], [16] and [17]. The “quasi-human” tries to simulate the behavior of human being in related special work such as bricklaying.
In [17], the authors presented a heuristic algorithm based on two important concepts, namely, the corner-occupying action and caving degree. Based on [17], an efficient heuristic algorithm (HA) for rectangle-packing problem is proposed on the basis of the wisdom and experience of human being in this paper. The objective is to maximize the area usage of the box. The key point of this algorithm is that the rectangle packed into the box always occupies a corner, even a cave, if possible. Furthermore, the rectangle should occupy as many corners and overlap as many edges with other previously packed rectangles as possible. In this way, the rectangles will be close to each other wisely, and the spare space is decreased. As compared with reviewed literatures, the results from HA are much improved. For 21 rectangle-packing test instances taken from [11], optimal solutions of 19 instances are achieved by HA, and two and three ones by the algorithm in [6] and [12], respectively. For each of 13 random instances taken from [13], the container height obtained by HA is smaller than that by best fit (BF) heuristic [13]. Furthermore, optimal solutions of three instances are achieved by HA. Experimental results show that HA is rather efficient for solving the rectangle-packing problem.
In this paper, an efficient heuristic algorithm (HA) for rectangle-packing problem is proposed. High area usage of the box can be obtained by this algorithm. Optimal solutions of 19 of 21 test instances taken from [11] and 3 of 13 instances taken from [13] are achieved by HA. The experimental results demonstrate that HA is rather efficient for solving the rectangle-packing problem.
