Two-dimensional Sheet Metal Row Of The Nesting Algorithm And Software Design

Cutting stock problems frequently occur in industries of sheet metal cutting, apparel and furniture production, and are NP-hard problems mathematically. It has been a researching focus in the fields of CAD/CAM and automation. This paper makes a investigation on the nesting algorithms of arbitrary sheet metal parts and puts forward a local greedy search method. The keynotes of this thesis are as follows: A heuristic search method for 2D CSPs is presented. Aiming at stock efficiency and based on present packing algorithms, this method first nests some small items into the holes of the big ones so as to form a sequence of GROUPs which have a better local stock efficiency, then packs these groups to get a preliminary global result, and in the end fills the gaps among the groups in the previous result to get the last optimal result. The method of calculating the no fit polygon (NFP) is improved. The NFP is a powerful and effective tool for handling the geometry required for a range of solution approaches to 2D irregular CSPs. However, unless all the pieces are convex, it is difficult to implement, and its use has therefore been somewhat limited. Although the method is based on previous approaches which use the mathematical concept of Minkowski sums, this new method can be easier to understand. The result is an approach that is both very general and easy to use. The paper gives out a method to combine non-convex figures into a convex one, a method to get bumping region by using NFP, and a scanning-line method to search the gaps among adjacent figures; these methods can well solve the local optimal problem in packing and nesting process, and improve the stock efficiency. A CAD/CAM software for cutting and nesting of sheet metals is designed. Some designing and developing principles are presented and some key techniques of one CAD/CAM software for cutting and nesting of sheet metals are solved. The software mainly gives resolutions for design and calculation, optimal packing and nesting, as well as numerical control process in cutting of sheet metals. A lot of new ideas and methods are used in the software for geometry and feature design and heuristic search strategies. In particular, the software successfully solves the problems of cutting leader-line and tool path optimization.