Research And Application Of Polygon's Packing Optimization With Multiple Constriants

Packing problem is to search out locations of parts within some process constraints and to achieve some optimization goals, such as producing the least waste. Packing problem exists in manufacturing industry widely, and has important influence on enhancing productivity and decreasing cost. It is both academically and practically meaningful to study packing algorithm and realize automatic nesting by using computer technology.Overseas and domestic research and trend about packing problem is discussed firstly. Aiming at solving irregular polygon packing problem with process constriants, classification of constriants and corresponding solutions are discussed in detail. An improved pair-wise offset method is proposed to acquire the parts' offsetting, which is used to meet distance constriants in packing.The special constriant of placing parts partly beyond materials has influenced packing process inherently, so that many packing algorithms raised before can not be applied to. Based on analyzing packing example with this constriant, this thesis presents a hybrid algorithm to acquire the parts' layout position while the parts' order and rotate angle have been determined. Firstly the parts located at the border of the material which might be beyond the material partly, are placed by using a heuristic location algorithm. Secondly other parts which are all inside the material are located by using an improved location algorithm for irregular polygon. This hybrid algorithm is able to increase the material's utilization within the constriant of placing parts partly outside. Particle swarm optimization algorithm is combined with the hybrid location algorithm mentioned, aiming at finding out optimal packing sequence.The theory and algorithms are adopted to develop the automatic layout software system, which includes modules of importing part and material, automatic layout, interactive layout, exporting layout result and so on. This system is applied for some institute's layout program, and has good performance and utility.