The Research On Computer Aided Nesting Algorithems And Their Realization

This paper is devoted to the research on computer aided tube sizing and two-dimensional nesting algorithms and their realizations. Tube sizing and two-dimensional nesting are one of the links in the production chain in manufacturing industries. Computer aided tube sizing and two-dimensional nesting can improve productivity greatly and cut down cost of production, therefore has wide prospects for its applications.The research on them began in the 1960s. With the development of computer technology, the research has been done more deeply and their applications have attracted more attentions. Two-dimensional nesting is a complete NP problem. It has quite high computational complexity. So far no common effective algorithm that is suitable to be realized on computers has appeared. In this paper, deeper and more careful research and probe on computer aided two-dimensional nesting are made. The contents include:Research on tube sizingThe author sets up the optimal mathematical model for tube sizing and give a linear programming-based computer realization algorithm with high efficiency, by which the optimal scheme for tube sizing can be achieved, so that the cost of materials can be as little as possible. The algorithm has high operation speed and can be suitable to large-scale production demand because nice tube sizing scheme can be obtained with this algorithm in which special strategy is adopted.Research on two-dimensional nestingThe author divides two-dimensional nesting problem into polygon connection, polygon merging, convex hull of polygon etc., then makes research on these problems and gives the corresponding algorithms to these problems. And finally the automatic heuristic-based search algorithm for two-dimensional nesting is obtained by combining these algorithms. The automatic algorithm uses knowledge about initial state space and heuristic information related to the problem to be solved to determine how parts are put together so that the algorithm is more reasonable. Besides, interactive two-dimensional nesting algorithm is given, which includes operations for graphs of parts, auxiliary functions, automatic maintenance and save of data and the link between automatic nesting and interactive nesting etc.Structure design for software system of tube sizing and nesting.The design idea and functions are described. From the view of users, the system includes data input, data display, automatic nesting, interactive nesting and data operations, and manages data (parts and materials) effectively by database technology. The software has nicer interface and higher operation efficiency than any other software in the same field.