Study On The Heuristic Search Algorithm Based On Clustering And Region Positioning For The Component Nesting Problem

Layout problem exists widely in many fields of productive practice, such as satellite module layout, clothing cutting, plate material blanking and electronic circuit designing, etc., which has theoretical and practical application value. Packing and Nesting, also known as the loading problem and layout problem, are the two typical layout problems. Based on the company background of the large crane manufacture project, this paper studies the component layout problem based on clustering and regional optimization. The features of the components are many kinds of parts, and the shapes have very big difference. Besides, the shapes are usually irregular. The company source subject is developed in the United States the typesetting software SigmaNest10. But for the batch sheet of the large-scale shape parts row version, the problem solving is not as satisfactory as hope, which has no choice but to adjust the layout scheme manually. In this regard, this paper launches the research based on probability theory, operations research, computer graphics and artificial intelligence theory, which breaks the problem solving the bottleneck problems and technical difficulties and applies for a patent of invention. The work and innovation of this paper are as follows:(1) The DXF file encoding rule s of parts CAD graphics are proposed, and the software of the automatic generation of data files is developed. The coding rules and software are designed to be applied to the multi-shape 2D graphics composed of line segments, arcs and circles. As to the graphic element data file, it contains primitive minimum envelope rectangle. The computational complexity of the algorithm is low, and the solving speed is fast.(2) A heuristic search algorithm based on the regional optimization of multishape components envelope rectangle layout is presented. Based on the layout scheme of the regional optimization search heuristic algorithm, there is a gap between 2D and 2D parts. In this paper, we further propose a method based on Lagrange multiplier and kuhn- Tucker conditions of the adjacent boundary, making the graph as close as possible to get further optimization of the layout scheme.(3) In high- volume steel large-scale multi-shape parts layout problem, referring to the difficulties of the front typesetting utilization rate is high and the behind typesetting utilization rate is low, this paper proposes a clustering based heuristic search algorithm, and designs the layout process steps. The comparing experimental results show that the operating efficiency of the layout program is high, the layout effect is well, and the material utilization rate is high.Using a manufacturing enterprise of large crane parts layout problem as the research background, referring to the single rectangular plate layout problem, this paper proposes the region based search and heuristic search algorithm and based on Lagrange's and K uhn Tucker conditions adjacent to the calculation method; for the batch rectangular steel plate large-scale multi shaped parts layout problem, a clustering based heuristic search algorithm is put forward. Through experimental comparison, it is concluded that the algorithm has better performance.