Research And Application Of Two-dimensional Cutting-stock Problem For Flaw

Packing problem arises from a variety of situations including pallet loading, textile cutting, container stuffing and placement problems. This problem is a kind of optimization problem that is concerned with finding a good arrangement of multiple different-sized objects in a large containing region without overlap and minimizing the waste. It belongs to be NP-Complete problem which is a great challenge to us. It has very important research value and attracts people's attention, and as a greater challenge, the minor-restricted situation is more complicated. Combinatorial optimization, Artificial intelligence, Computational geometry and other theories are adopted to research this problem.Because it is a NP-Complete problem, In order to solve the subject about time and energy, the classic packing algorithm is discussed in the thesis. That is the classical algorithm in the artificial intelligence. Such as Genetic Algorithms and some traditional artificial intelligence approaches such as Heuristic Search or operations research methods such as First Fit. In recent years, Genetic Algorithms are being widely applied in this area, and it has been proved to be an effective way to resolve packing problem.In this thesis, the two-dimensional cutting-stock problem about rectangle objects with minor fault in the materials and irregular objects is mainly researched, a Genetic Algorithm based packing algorithm with minor faults in the materials is presented. Based on the Genetic Algorithm, two Layout Algorithms are presented, and with the help of AutoCAD, a approach of two dimensional collision detection is presented, it makes the collision detection easy. The computing efficiency and the utilization rate are improved well. The two-dimensional cutting-stock problem with minor faults in material is elementary researched, and a approach to resolve the minor is presented, which is proved to be effective.The thesis mainly adopted Genetic Algorithm, Layout Algorithm and collision detection arithmetic to optimize and arrange the figures. In the meantime, using the computer figures processing software Autocad2002 and its second development software ObjectARX, a program is designed which can solve the two-dimensional cutting-stock problem of rectangle objects and irregular objects, and finally a result with high utilization rate is stored in an AutoCAD file. And, it also solves the problem well when there is minor faults in the material.The result of experiments indicated, the Genetic Algorithm with the Layout Algorithm is effective to the two-dimensional problems and can successfully handle the minor defaults. At last the utilization rate can be improved well.