Research And Application Of Two-Dimensional Irregular Part Packing Algorithm

Packing problem,which means how to find out the optimal layout of parts in a given area to promote the utilization of raw material,is the key to save costs in mass production.Among all,two-dimensional packing has been most widely used in areas like fabric cutting,shipbuilding,leather nesting etc.Excellent packing algorithm may effectively save raw material and promote industrial production efficiency.Howev er,packing problem is a typical NP-hard combinational optimization problem with great computational complexity.So it is of great theoretical and practical significance to research and design a more efficient irregular packing algorithm.Having studied the two-dimensional irregular packing algorithm based on principle of minimum potential energy deeply,this paper has proposed a two-dimensional part packing algorithm based on dynamic updating of packing point set to improve the way of selecting packing points and reference points to reduce the part packing testing times.For the problem of parts sequence optimization of packing algorithm,this paper has studied the application of intelligent optimization algorithms in combinational optimization and proposed an improved algorithm of discrete particle swarm optimization algorithm to solve two-dimensional irregular packing problem.This discrete particle swarm algorithm was optimized by combining with crossover and mutation principle of genetic algorithm.This algorithm has been proved effective in increasing material utilization rate via massive benchmark datasets while we can still do a lot to optimize its time performance.So based on Map Reduce this paper has researched into parallelization o f two-dimensional packing algorithm,broke the single processing mode restrictions,and effectively improved the packing performance.This paper has attempted to simulate the actual "shake bottle" process,and designed a two-dimensional irregular packing algorithm based on shake-bottle strategy.It takes all the parts involved in packing as a whole,and fully consider influencing factors of all the parts around each single part to find better fitting positions among parts.Meanwhile,with gravitational pote ntial energy taking into consideration,the algorithm proposed in this paper has made the final position of all parts lower,and effectively solve the two-dimension irregular part packing problem.Based on the algorithms proposed in this paper and using Vi sual Studio 2010 technology,the researcher has developed a two-dimensional irregular simulation system with perfect functions and user-friendly interface,which has verified the effectiveness of the above-mentioned packing algorithms.