Research On The Algorithms For The Rectangular Strip Packing Problem

Nesting is the offspring of computer technology and modern economy. The aim of it is to put as many blanks as possible in the material so as to reduce the material loss. Computer Aided Nesting is one of computer aid technique which was used widely; it has the merit of high utilization, short running time, low expense and so on. The aim to use computer aid optimize nesting is to find some optimize layout that make the plane area's utilization better. All the industry that needed to process material division can use computer nesting technique.Nesting problem is the typical combination and optimization problem, it has widely used in our live, it has high compute complexity. For large scale nesting problem, no only nesting by handcraft is impossible, even if use computer also have to exploder high efficiency arithmetic to achieve the relatively high efficiency optimum cutting. This paper uses heuristic search method so as to have a near optimize result in a relatively short time.Use sheet with restricted in width but infinite in length to cut a group of rectangular blank with known size, minimize the used area of sheet, that is to say, minimize the used length of sheet with pack all the blanks. Require that the rectangular blank parallel with the sheet margin and can use in guillotine cut. This problem is called Rectangular Strip Packing, it is the RG subtype of two dimensional strip packing problem, here, R denote that the blank can be rotated by 90°,G denote that the blank can be guillotine cut. The paper discussed this problem in detail.The aim of this paper is to combine the produce need of the enterprise with advance the utilization and reduce the cost of raw material, exploder a packing software and give a packing pattern with a relatively high utilization of the sheet, which can be used in theory study and particle references.This paper has two parts:(1)The first part gives out an optimum heuristic recursive algorithm for the two-dimensional rectangular strip packing problem. It is based on a recursive structure combined with branch-and-bound techniques. Several betterment heuristic technique are tried to determine the minimal sheet length to hold all the items. Initially the sheet is taken as block. Considered the current block, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with a lever or plumb guillotine line, it can be solve by recursion method more convenience. Both lower and upper bounds are used to prune unpromising branches, used heuristic technique to shorten the running time. The computational results on a class of benchmark problems indicate that the algorithm performs quicker than a heuristic recursive algorithm which recently reported.(2) Second, use genetic algorithm (GA) to combine with the optimum heuristic recursive algorithm that say above. Introduce the Genetic Algorithm systematically, the characteristics of genetic algorithm, basic implement of GA used to solve the rectangular packing problem are also discussed in detail. Genetic Algorithm is a method searching for the optimum solution to a complex problem, based on the mechanics of natural selection, the process of evolution. It has the ability of doing a global searching quickly and randomly. It is flexible and robust. In the aspect of solving large, non-linear and poorly understood problems where expert knowledge is scare or difficult to encode and traditional methods fail, GA has great advantages. It is one of kernel techniques related with intelligent computing in 21 century.Discuss the design and the realize of how to use genetic algorithm to optimum packing problem in detail. This algorithm is mainly based on genetic algorithm and heuristic strategies combine with recursive structure. The algorithm also selects an item, puts it at the bottom-left corner of the sheet, and divides the unoccupied region into two smaller blocks with a lever or plumb guillotine line, recursive the algorithm like this. Uses heuristic rules and genetic algorithm to find better solution.The primary work of this paper is as follow:The main content of the article have two parts: the first part is use optimum heuristic to combine with recursion. Compositor the blank for its area from large to small, then we used the improved recursive algorithm advance in this paper to reduce unnecessary searches and shorten the packing time, through compare with the sheet utilization of different rectangle packing sequences, use recursion packing to have the packing result picture at last; the second part of the paper combine with the optimize algorithm exploder an optimum rectangle packing system by applying heuristic algorithm and genetic algorithm. First use genetic algorithm and optimum heuristic algorithm to have a better packing order and packing mode, then use recursion packing to have the packing result picture, through compare with sheet utilization of different rectangle packing sequence, we have the optimize packing project. One character of this article is: base on the optimize need, it can adjust the sequence of blank create by genetic algorithm, that is to say, it allow alternating the original chromosome gene's sequence in the recursion packing.Base on the proposed algorithm, a system of computer-aided optimizing nesting was realized. The experimental results indicate that the improved algorithm is flexible and effective. Research in this dissertation will contribute to economize raw materials, reduce operating costs and improve the enterprise's economic efficiency. In the end, summarizes the research on rectangular packing problem and puts forward the research of the next work in the future.