Study Of Algorithms Of Graphic-Matching, Control Of Packing And Contacting In Two-Dimensional Packing System

Packing Cutting of two-dimensional (2-D) parts from 2-D sheets is a common problem in wood-, glass-, steel-, leather and paper industry. It is a key component from designing to cutting in automation of manufacturing. To realize the automation of packing will be helpful to increase efficiency of labor and utilization of materials and to realize the automation of manufacturing.Its goal is to put more parts without overlaps in the given sheets and get the maximal utilization of materials. There are many different constrains in different industry. However, they are all NP-hard problems. In particular, with the the increasing of dimentions of regular packing-graphics and irregular graphics, the complexity of computation increases rapidly. How to recrease the time of packing and increase the utilization ratio of materials is the focus that is cared about by researchers and discussed in the dissertation.The following are main work done in the dissertation:(1) Clustering idea is induced into packing problem. Effective data features of matching packing-graphics are extracted and are analysed. Clustering algorithm and classification algotithm that adapt to packing of matching-graphics is designed.(2) In order to make sure that the characteristics of packing-graphics are extracted effectively, practical algorithms of enveloping circle and enveloping rectangles set and approximately ratio of long axes and short axes are brought out. The principles of choosing proper enveloping algorithm are brought out.(3) Coding of packing graphics is studied and applying the graphics characteristics results gotten from (2) to add features information of packing graphics into packing-database. The speed of indexing increases in the process of packing.(4) Immune principles are introduced into genetic algorithm soving packing problem to avoid the shortcoming of prematurity cenvergence of genetic algorithm. And a more effective definition of similarity base on packing problem is brought out.(5) In order to judge if the immue operator works or not, immue operator hypothesis is brought out. And statistics analysis test algorithm is brought out and designed to test the hypothesis. Results of statistic analysis test are used to guild the definition of similariry and setting of parameters.