Research And Development Of The Optimal Layout System For Two Dimensional Irregular Parts

The aim of the computer aided optimal layout of the parts with different shapes is to find the arrangement of parts and producing the least waste. The problem of optimal layout belongs to the NP-complete problem with tiptop calculate complexity. It is very difficult to find the optimal solution for such a problem because of the high complexity of shpes and computation. Conventional layout works all adopt manual operations that have many shortcomings such as low yield, inefficient and long time consuming. People cry for a solution by the modern science and technology because of the need of production. Most of the papers published in this field are concerned with the packing problem of regular shapes (such as rectangle), only a few are about the irregular shapes.In this thesis, by the analysis of the current research status and the shortage of traditional GA, a partheno-genetic algorithm based on optimal solution kept has been presented to solve the irregular layout. The Partheno-Genetic Algorithm that repeals the crossover operators of traditional genetic algorithms while uses the reproduction manner with only parent. Comparing with traditional genetic algorithms, the genetic operation of partheno-genetic algorithm is simpler; it is easier to handle constrains during genetic operation; the initial population of partheno-genetic algorithm need not be varied; there is no "immature convergence" of partheno-genetic algorithm; the searching efficiency of partheno-genetic algorithm is higher. Through experimental verification, the algorithm's results in the calculation of precision and time is better than common algorithms and has higher accuracy, effectiveness and feasibility compared to conventional algorithms.Parallel technology and traditional PGA are combined to improve PGA's efficiency by utilizing the inherent parallel characteristic of PGA, this thesis realized parallel partheno-genetic algorithm in LAN to speed up the operating speed of partheno-genetic algorithm and break through the limitation of single computer's calculation capacity. Model of Parallel Computing base on model of Master/Slave of coarse grain during computing, at first master machine send the individual to every slave machine, then slave machine begin computing, after slave machine finish computing at intervals, it will migrate individual to master machine by some migratory policy. At the same time, slave machine will carry back other slave machine's individual that is also send to master machine and continue computing. When halting condition is satisfied, slave machine will stop computing. The result shows that the coarse-grained model can not only increase calculation speed but also optimize the solution.This thesis designs and develops a computer aided nesting system based on the core algorithms above by using the Visual C++ platform. The system has good data interface, and can read and save to DXF files; the system has a friendly interactive environment, users can easily enter and adjust parameters; the system has rapid response characteristics and can get nesting results in short time; the system has excellent nesting function and can get better nesting results; the system is easy to maintain and expand.