Abstract
The nesting of two-dimensional shapes is a common problem, where raw material has to be economically cut. As for the single-pass single-row strip layout, several algorithms, based on established methods, have been proposed. Moreover, it should be noticed that the optimum layout should also consider a few constraints, like grain orientation for subsequent forming operation, correct bridge width, and the commercial roll of metal width in order to make solutions applicable in real industrial environments. Most of the procedures until now shown in literature are quite complex and often ignore these real constraints. They usually make use of sliding techniques and are not able to effectively work with relatively multiple-connected figures. In particular, most of the different proposed procedures are based on the No Fit Polygon (NFP) computation of non-convex polygons, which often generates holes. This work is a proposal for a more efficient method, which can be used in heuristic procedures. In order to overcome some faults of most of the former methods presented in literature, in this paper a new geometric entity called “No Fit Path” (NFPh) of non-convex polygons is applied. It allows researchers to find solutions of nesting problems even when there are NFP faults due to degenerate solutions. Moreover, the No Fit Path allows researchers to easily read, modify, or share their results, overcoming all those problems arising from the usual large amount of information and from the different origins and formats of the obtained data. Given two non-convex polygons, the algorithm is able to calculate their NFPh very quickly and without any approximation by a polygon clipping method. In this paper a totally automated procedure has been developed. This procedure firstly obtains the “No Fit Path” (NFPh); secondly, between all the existing positions on the NFPh, the algorithm searches the optimal one, minimizing the global waste. The proposed approach also allows designers to set an optimal orientation of the shapes on the roll of metal, taking account of the grain orientation in order to obtain the best mechanical characteristics for the cut pieces.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Wascher G, Haussner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 127(3):1109–1130, Elsevier
Bennell J-A, Oliveira J-F (2008) The geometry of nesting problems: a tutorial. Eur J Oper Res 184:397–415
Lo Valvo E, Piacentini M, Ruisi V-F (1993) Computer aided blank layout optimum design. Manuf Syst 22:143–146
Lo Valvo E (1995) Nesting of irregular shapes on a strip in metal stamping blanks operations. Proc of II Convegno AITeM, 31–38
Nye T-J (2000) Stamping strip layout for optimal raw material utilization. J Manuf Syst 19:239–248
Nye T-J (2001) Optimal nesting of irregular convex blanks in strip via an exact algorithm. J Mach Tool Manuf 41:991–1002
Lam T-F, Sze W-S, Tan S-T (2007) Nesting of complex sheet metal parts. Comput Aid Des Appl 4:169–179
Crispin A-J, Clay P, Taylor G, Bayes T, Reedman D (2005) Genetic algorithm coding methods for leather nesting. Appl Intell 23–1:9–20
Rajender S, Sekhon G-S (1998) A low-cost modeller for two dimensional stamping layout. J Mater Process Technol 84:79–89
Dean H-T, Tu Y, Raffensperger J-F (2006) An improved method for calculating the no-fit polygon. Comput Oper Res 33:1521–1539
Bennell J-A, Song X (2008) A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums. Comput Oper Res 35:267–281
Burke E-K, Kendall G (1999) Applying ant algorithms and the No Fit Polygon to the Nesting problem. Proceedings of the 12th Australian Joint Conference on Artificial Intelligence (AI'99), Sydney, Australia, December 6th–10th December 1999, Springer Lecture Notes in Artificial Intelligence 1747:454–464
Watson P-D, Tobias A-M (1999) An efficient algorithm for the regular packing of polygons in the infinite plane. J Oper Res Soc 50:1054–1062
Agarwal P-K, Flato E, Halperin D (2000) Polygon decomposition for efficient construction of Minkowski Sums. Proc of ESA 8th Annual European Symposium on Algorithms
Lo Valvo E, Licari R (2007) A more efficient method for clustering sheet metal shapes. Key Eng Mater 344:921–927
Lo Valvo E, Licari R (2008) A proposal for a new scheme for No Fit Polygon using XML. 5th ESICUP Meeting
http://paginas.fe.up.pt/∼esicup/tiki-index.php?page = NestingXML
Nee A-YC (1984) A heuristic algorithm for optimum layout of metal stamping blanks. CIRP Ann 33:317–320
Ismail H-S, Hon KK-B (1992) New approaches for the nesting of two dimensional shapes for press tool design. Int J Prod Res 30:825–837
Joshi S, Sudit M (1994) Procedures for solving single-pass strip layout problems. IIE Trans 26:27–37
Prasad YKD-V, Somasundaram S, Rao KP (1995) A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks. Int J Prod Res 33(6):1505–1520
Rajender S, Sekhon G-S (1996) A computerized diagraph and matrix approach for evaluation of metal stamping layout. J Mater Process Technol 59:285–293
Vamanu V, Nye T-J (2002) Stamping die strip optimization for paired parts. Proc ASME, Manuf Eng Div 13:91–96
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Licari, R., Lo Valvo, E. Optimal positioning of irregular shapes in stamping die strip. Int J Adv Manuf Technol 52, 497–505 (2011). https://doi.org/10.1007/s00170-010-2772-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-010-2772-6