A Quasi-human Heuristic Algorithm for Rectangle Packing Problem
一种求解矩形块装填问题的拟人算法

Rectangle packing/cutting problem is often raised in loading,timber cutting,Very Large Scale Integration (VLSI)design,and so on.For solving this problem,many algorithms such as simulated annealing,genetic algorithm, and other heuristic algorithms have been proposed.In this paper,an efficient quasi-human heuristic rectangle packing algorithm is proposed according to ten-thousand-year experience and wisdom of human being.The algorithm utilizes two important strategies,i.e.,how to select the rectangle based on its value and how to pack it according to the corner occupying place.21 rectangle packing test instances are tested by the produced algorithm,16 instances of them achieve optimum solutions,and the runtime is less than 2 seconds for each instance.The integrated performance of the pro- duced algorithm is rather satisfied.Experimental results demonstrate that the algorithm proposed in this paper is rather efficient for solving rectangle packing problem.