Optimizing Cutting Pattern In Rectangular Packing Problem By Genetic Algorithm

After China's accession to the World Trade Organization ,manufacturing enterprise face more intensive market competition. In order to win the market ,one important task is to increase economic income ,which can be realized by decreasing production cost. Improving material usage may reduce the costs of production and thus it is an efficient way to increase the profits of the enterprises. Layout of rectangle parts has been widely used in various industries . Cutting of two-dimensional(2-D) shaped parts from 2-D sheets ,with a minimum wastage of materials is an important task. The research of optimizing cutting stock problem is to study how to generate cutting patterns to improve material usage .So research on the problem is of importance in theory and practice. Rectangular packing problem(RPP) is a combinatorial optimization and NP-complete problem. It is difficult to find its exact global optimum for such a problem because of the high complexity of computation. The traditional goal of RPP is to minimize the trim loss. For the rectangular packing problem ,no algorithm is sufficient to solve the problem . Up to now there are varieties of heuristic algorithms to solve the rectangular packing problem because of its high complication. Many factors should be considered to get a good solution, such as production management, cutting stock process, and decision support. For the cutting stock process, the key problem is to construct an efficient algorithm . Research on the rectangular packing problem not only deals with the layout problem of a set of 2D rectangular parts onto a rectangular object but also plays important role in solving of irregular cutting stock problem . The unconstrained two-dimensional non-guillotine cutting problem consists of packing rectangular pieces of predetermined sizes into a sheet ,which is restricted in width but infinite in length, where any cuts that are made are unrestricted . The objective of most solution techniques is to find 'cutting pattern 'that minimize the unused area(trim loss) .This paper discussed this problem in detail. Genetic Algorithm (GA) is a method for 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 scarce 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. This paper introduced genetic algorithm systematically, which include the relationship between GA and natural evolution and the characteristics of genetic algorithm , basic implement techniques of GA and so on .The design and implement of GA used to solve the rectangular packing problem are also discussed in detail. The primary work of this paper as follows:First ,we analyze the actuality of the packing problem ,the algorithms of layout of rectangle parts mostly in use were compared . On the basis of the Lowest Horizontal Line –Search Algorithm(LHL-SA) , an improved algorithm for rectangular packing problem is proposed in this paper , that is, Lowest Horizontal Line-Waste Area Can Reused Searching Algorithm(LHL-WARSA),which meets the BL condition and overcome the shortcomings of other algorithm for some patterns . The proposed algorithm can combine small waste areas that produced during the process of packing to large areas ,then use them again,so it can improve the using ratio of material more efficiently . The size of each rectangle is compared with that of waste area , therefore better sequence and better location of each rectangle on the sheet can be obtained . We solve the rectangular packing problem by applying the genetic algorithm .The most important is that we use the genetic algorithm to find the sequence in which the small rectangles are packed ,then we used the improved algorithm advanced in this paper to pack the rectangular pieces .By comparison ,the best cutting pattern was obtained. Based 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 , author summarizes the research on rectangular packing problem and puts forward the orientation of the next work in the future.