Research On The Heuristic Algorithm Based On Objective And Orthogonal Space Decomposition For Packing Problem

Packing problems with their NP-complete computational complexities are categorized as discrete combinatorial optimization problems with strong application background, and they occur in a variety of situations of modern industry and life. Heuristic algorithms are needed to solve the NP-complete problems, which is the method of this paper to study the packing problems. On the basis of lots of tests and the wide research on the packing problems, a heuristic algorithm based on objective and orthogonal decomposition of space is developed to solve the non-guillotine packing problem. The paper can be outlined as follows:It begins by analyzing the decomposition forms of space in the packing problems. The process of orthogonal decomposition of the packing space is addressed to satisfy the non-guillotine packing problem, which decomposes the residual space into the 1st sum-space and the 2nd sum-space. Several strategies including strategy of difference space, strategy of group which is discussed in detail, strategy of backdating, strategy of convergence, are used synthetically to implement the packing algorithm and to realize the continuous orthogonal decomposition of the packing space.The strategy of objective is developed through the analysis of the local optimization and the global optimization. It sets an objective which is the lowest solution to the local optimization at the beginning, thus, this algorithm can get a very good global solution.Phasic theory of the packing process and the characteristics of trim loss are applied to design the packing algorithm. Multiple pattern orientated approach is used in the heuristic algorithm based on objective and orthogonal decomposition of space to solve the large-scale packing problem. Finally, conclusions of the whole dissertation are made and further research directions are given.