Study On The Technology Of Computer-aided Packing For Two-dimensional Parts

The packing problem belongs to stock-cutting and layout problem, which is widely encountered in all kinds of industry such as mechanical machining, shipbuilding, automobile manufacturing, aviation and light industry, etc. The traditional manual packing method impedes corporation's development because of its inefficiency and the quality dependence on the worker's experience. CAN (Computer Aided Nesting) is much more effective, better quality and steadier than manual packing method. So it can enhance corporation's competition by improving operating efficiency and reduce operating costs.At present, one-dimension and one-and-half dimension packing problem has been resolved by the rules we known. There are some mature methods for resolving rectangular nesting problems. But the packing problem of irregular shapes is still under investigation.This paper summarized 2-D (two-dimensional) packing types and their CAN methods. Based on the summary, a further research on nesting irregular-shaped parts on irregular-shaped stock was made. At last, Study the designing method of a universal packing system.The contents of this thesis go into detail as following:1. Design a rapid decoding algorithm for nesting irregular-shaped parts on irregular-shaped stock. GA (genetic algorithm) technology applied in packing needs decoding operation, which usually is quite time-consuming. In this novel decoding algorithm, firstly the parts and stock is parallelized, and then the BL strategy is used to pack the parts on the stock. During the parts packing, a method for vertex collision detection is introduced to speed up the part's positioning process along x coordinate; the stock-baseline increased strategy is proposed to get the part's position along y coordinate quickly. Results show that this algorithm is quick in decoding speed and easy for program implementation.2. Design two kinds of parallel genetic algorithm model for nesting irregular-shaped parts on irregular-shaped stock. They utilized client/server structure and were realized in LAN. In the first case, the master-slave model was used. The server coordinates the process of GA and spreads individuals of the population to clients; the client gets individual's fitness by decoding and sends the fitness back. In...