Abstract
Determining a process plan in the early phase of the sheet metal forming process is a mandatory task for a process planner. The objective of a process planner is to find a feasible and cost optimal process plan which, in particular, optimizes the assignment of processing elements to processing steps of the production process. We propose to find such an assignment in an automatic way for all the hole features by splitting the entire task into three subsequent steps. At each step, the combinatorial optimization problem is modeled as a bin packing problem with conflicts, and heuristically solved by a specifically designed ant colony optimizer. It is ensured that, at each step, the process plan is feasible while minimizing the tooling costs. In our computational results, we compare our approach to the existing greedy heuristic when computing a process plan for five different practice-relevant sheet metal parts, and show that we can save up to 50 % of the entire tooling costs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Emrich A, Compensation of springback based on the formability analyses results, in: The Press Plant facing shifting requirements, volume 8 of Automotive Circle International Conference, p. 160
Schrempp G, Werteveränderung durch modifizierte Allokationen auf der Prozesskette Blech, Vortrag, 2007. Available online at http://logistics.de/downloads/4f/2a/i_file_45370/ allokation-prozesskette-dlk-2007-schrempp-pwo.pdf; visited on April 24th 2012
Schuh G, Boos W (2004) Werkzeugfunktionen als Kalkulationsbasis, Plastverarbeiter 6
Kubli W, Prabhakar V (2008) Digital process planning for automotive body panels, in: Proceedings of the 7th International Conference and Workshop on Numerical Simulation of 3D Sheet Metal Forming Processes (Numisheet)
Pietsch M, Wagner S, Computer aided method for an associative process layout generation, in: Proceedings of the 7th International Conference and Workshop on Numerical Simulation of 3D Sheet Metal Forming Processes (Numisheet) 2008
Li W, Ong S, Nee A (2003) A hybrid method to recognizing interacting machining features. International Journal of Production Research 41:1887–1908
Owodunni O, Hinduja S, Systematic development and evaluation of composite methods for recognition of three-dimensional subtractive features, in: Proceedings of Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, volume 219, pp. 871–890
Rahmani K, Arezoo B (2007) A hybrid hint-based and graph-based framework for recognition of interacting milling features. Computers in Industry 58:304–312
Verma A, Rajotia S (2009) Hybrid machining feature recognition system. International Journal of Manufacturing Research 4:343–361
Nasr EA, Kamrani AK (2007) Computer-based design and manufacturing: an information-based approach. Springer, Berlin
Sunil V, Pande S (2008) Automatic recognition of features from freeform surface cad models. Computer-Aided Design 40:502–517
Zhang C, Zhou X, Li C (2009) Automatic recognition of intersecting features of freeform sheet metal parts. Journal of Zhejiang University Science A 10:1439–1449
Danzberg J (2001) Einsatz hierarchischer parametrisierter Konstruktionsmetodik zur Planung und Optimierung von Karosserieblechteilen, Ph.D. thesis, ETH Zurich
Hillmann M, Kubli W (2005) Bestimmung von Prozessoperationen zur Beschreibung von Umformprozessen an einem Umformteil
Ehrlenspiel K, Kiewert A, Lindeman U (2005) Kostengünstig Entwickeln und Konstruieren, Springer Verlag Berlin Heidelberg
Fischer J (2008) Kostenbewusstes Konstruieren, Springer Verlag Berlin Heidelberg
Pahl G, Beitz W, Feldhusen J, Grote KH (2007) Konstruktionslehre, Springer Verlag Berlin Heidelberg
Verlinden B, Duflou JR, Collins P, Cattrysse D (2008) Cost estimation for sheet metal parts using multiple regression and artificial neural networks: a case study. International Journal of Production Economics 111(2):484–492
A. Wittmann, A.-W. Scheer (2000) FIT Featurebasiertes Integriertes Toleranzinformationssystem, Technical Report, Universitat Saarbrücken, Institut für Wirtschaftsinformatik
Tangelder JW, Veltkamp RC (2008) A survey of content based 3d shape retrieval methods. Multimedia Tools and Applications 39:441–471
Romanowski RNCJ (2005) On comparing bills of materials: a similarity/distance measure for unordered trees. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 35:249–260
Karadgi S, Müller U, Metz D, Schafer W, Grauer M Cost estimation of automotive sheet metal components using knowledge-based engineering and case-based reasoning, in: IEEE International Conference on Industrial Engineering and Engineering Management, pp. 1518–1522.
Grauer M, Metz D, Müller U, Karadgi S, Sch¨afer W, Barth T (2010) Towards an integrated virtual value creation chain in sheet metal forming. Lecture Notes in Business Information Processing 46:186–197
Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, Chichester
Wächer G, Häusner H, Schumann H (2007) An improved typology of cutting and packing problems. European Journal of Operational Research 183:1109–1130
Alves C, de Carvalho JMV (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Computers & OR 35:1315–1328
Alvim ACF, Ribeiro CC, Glover F, Aloise DJ (2004) A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics 10:205–229
Anily S, Bramel J, Simchi-Levi D (1994) Worst-case analysis of heuristics for the bin packing problem with general cost structures. Oper Res 42:287–298
Belov G (2003) Problems, models and algorithms in one and twodimensional cutting, Ph.D. thesis, Technical University of Dresden
Coffman J, Garey EG, Johnson DS et al (1997) Approximation algorithms for bin packing: a survey. In: Approximation algorithms for NP-hard problems. PWS, Boston, pp 46–93
Fekete SP, Schepers J New classes of lower bounds for bin packing problems, in: IPCO: 6th Integer Programming and Combinatorial Optimization Conference, volume 1412 of Lecture Notes in Computer Science, pp. 257–270
Gendreau M, Laporte G, Semet F (2004) Heuristics and lower bounds for the bin packing problem with conflicts. Computers & Operations Research 31:347–358
Gent I (1998) Heuristic solution of open bin packing problems. Journal of Heuristics 3:299–304
Gupta JND, Ho JC (1999) A new heuristic algorithm for the one dimensional bin-packing problem. Production Planning & Control 6:598–603
Kao C-Y, Lin F-T (1992) A stochastic approach for the one-dimensional bin-packing problems. IEEE International Conference on Systems, Man and Cybernetics 2:1545–1551
Scholl A, Klein R, Jürgens C (1997) Bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & OR 24:627–645
Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys 35:268–308
Loh K, Golden BL, Wasil EA (2008) Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & OR 35:2283–2291
Brugger B, Doerner K, Hartl RF, Reimann M, Antpacking—an ant colony optimization approach for the one-dimensional bin packing problem, in: EvoCOP, pp. 41–50.
Levine J, Ducatelle F (2004) Ant colony optimisation and local search for bin packing and cutting stock problems. Journal of the Operational Research Society 55:705–716
Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Computers & OR 29:821–839
Mladenovic N, Hansen P (1997) Variable neighborhood search. Computers & OR 24:1097–1100
Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2:5–30
Falkenauer E (1994) A new representation and operators for genetic algorithms applied to grouping problems. Evol Comput 2:123–144
Iima H, Yakawa T (2003) A new design of genetic algorithm for bin packing, in: Evolutionary Computation, CEC’03. The 2003 Congress on, volume 2, pp. 1044–1049
Jing X, Zhou X, Xu Y (2006) A hybrid genetic algorithm for bin packing problem based on item sequencing. Journal of Information and Computing Science 1:61–64
Khüri S, Schütz M, Heitkotter J (1995) Evolutionary heuristics for the bin packing problem. In: Pearson DW, Steele NC, Albrecht RF (eds) Artificial Neural Nets and Genetic Algorithms. Proceedings of the International Conference in Ales, France, pp 285–288
Reeves C (1996) Hybrid genetic algorithms for bin-packing and related problems. Annals of Operations Research 63:371–396
Rohlfshagen P, Bullinaria JA, A genetic algorithm with exon shuffling crossover for hard bin packing problems, in: GECCO, pp. 1365–1371.
Singh A, Gupta A (2007) Two heuristics for the one-dimensional bin-packing problem. OR Spectrum 29:765–781
Stawowy A (2008) Evolutionary based heuristic for bin packing problem. Computers & Industrial Engineering 55:465–474
Sathe M, Schenk O, Burkhart H (2009) Solving bi-objective many-constraint bin packing problems in automobile sheet metal forming processes. In: Ehrgott M, Fonseca C, Gandibleux X, Hao J-K, Sevaux M (eds) Evolutionary Multi-Criterion Optimization, volume 5467 of Lecture Notes in Computer Science. Springer Berlin, Heidelberg, pp 246–260
D. S. Liu, K. C. Tan, C. K. Goh, W. K. Ho, On solving multiobjective bin packing problems using particle swarm optimization, in: G. G. Y. et al. (Ed.), Proceedings of the 2006 I.E. Congress on Evolutionary Computation, IEEE Press, Vancouver, BC, Canada, 2006, pp. 2095–2102
Geiger MJ, Bin packing under multiple objectives a heuristic approximation approach, in: The Fourth International Conference on Evolutionary Multi-Criterion Optimization: Late Breaking Papers, Matsushima, Japan, pp.53–56.
Lara O, Labrador M (2010) A multiobjective ant colony-based optimization algorithm for the bin packing problem with load balancing, in: Evolutionary Computation (CEC), IEEE Congress on, pp. 1–8.
Dorigo M, Birattari M, Stützle T (2006) Ant colony optimization. Computational Intelligence Magazine, IEEE 1:28–39
Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344:243–278
Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge, USA
Stützle T, Hoos H (2000) Max-min ant system. Future Gener Comput Syst 16:889–914
AutoForm Development GmbH, CostCalculator Reference Manual, 2009
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wagner, S., Sathe, M. & Schenk, O. Optimization for process plans in sheet metal forming. Int J Adv Manuf Technol 71, 973–982 (2014). https://doi.org/10.1007/s00170-013-5515-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-5515-7