Research On Heuristic Algorithms For The Two-dimensional Packing Problem

The packing problem is a typical combinatorial optimization problem. Simply, the packing problem is to pack the objects of different sizes into a defined space so as to obtain the specified optimal objective. The packing problem has been widely applied to the fields of computer science and industry, such as multiprocessor scheduling, memory management, goods loading and stock cutting, so the packing problem has great significance not only in theory but also in practice.Many researchers have done a lot of researches on the packing problem since 1970s. Because the packing problem is NP complete and of high complexity, the general mathematical methods are hard to solve it, so heuristic algorithms have been widely applied to the packing problem in latest years.The article reviews the research progress, and also summarizes the classification and algorithms for the packing problem. The main work of the article focuses on the two-dimensional rectangular strip packing. Based on the current HR and PH method, two new heuristic algorithms SA+HR and SA+LWFBDL are presented. SA+HR uses simulated annealing (SA) to search better orders of objects so as to get better solutions, in which HR is the basic packing strategy and the neighborhood is defined by exchanging the positions of two objects randomly. The least wasted first packing strategy based on dynamic layers is presented in SA+LWFBDL, which still uses the random search technology SA to search better solutions.The computational results on several classes of benchmark problems have shown that SA+HR and SA+LWFBDL improve the solutions of HR and PH. SA+HR can find better solution than BF, SA+BLF and GA+BLF. SA+LWFBDL can get optimal solutions for many instances by several runs, which can compete with excellent algorithms such as SPGAL, HRBB and HRP.