Research Article
Optimization of striplayout using graphtheoretic methodology for stamping operations on progressive die: a case study
Mechanical Engineering Department, Faculty of Engineering, Helwan University,
Cairo,
Egypt
^{*} email: shady_ali@heng.helwan.edu.eg
^{**} email: hmahuss@hotmail.com
Received:
12
January
2021
Accepted:
20
April
2021
The design of the progressive die stamping process is optimized through minimizing the number of die stamping stations in the strip layout to reduce the die cost. In order to accomplish such end, in this study, a graphtheoretic based method is implemented to model and optimize the strip layout design. This method starts with mapping stamping features into stamping operations. This step is followed by constructing two graphs to model the precedence and adjacency constraints among stamping operations based on a set of manufacturing rules. These two graphs are called: operation precedence graph and operation adjacency graph. In the next step, a topological sorting algorithm clusters the operations into partially ordered sets. Then, a graph coloring algorithm clusters the partially ordered operations sets into final sequence of operations. The graphtheoretic technique has been implemented on a part currently manufactured by laser cutting process technology in some Egyptian factory in Cairo. This study indicated that the graphtheoretic technique offers several advantages including the ease of programming and transparency in understanding the obtained strip layout design. This is besides being a systematic and logically approach to obtain an optimized strip layout design. In general, the progressive die manufacturing can increase productivity of sheet metal works in Egypt, only in situations of mass production. The limitation is that it requires considerable skill level and training for labor to conduct die strip layout design.
Key words: Progressive die stamping / strip layout design / graph theory / graph coloring algorithm / topological sorting algorithm
© S. Aly et al., Published by EDP Sciences, 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1 Introduction
Progressive die stamping process is used to produce a large number of parts in mass production to achieve minimum cost possible through economy of scale. Die design efficiency has a very significant impact on the die cost. This is particularly the situation in sheet metal progressive die stamping. The cost of the die depends primarily on optimization of the strip layout design, which means minimizing the total number of die stamping stations. Sheet metal die design types could be classified into 4 families: shearing dies, bending dies, deep drawing and forming dies. There are about 22 die types under the three families, as classified in [1]. Shearing Die types of sheet metal such as, blanking, piercing, punching, shaving, partingoff, slitting, etc. The first step in the sheet metal die design is the process planning. In case of progressive die design, the strip layout is considered as the process planning process. The strip layout design task depends on the skills and experience of designers, which can form one set of input to the layout process to define precedence and adjacency constraints among progressive die operations. Strip layout design involves laying out the metal or material strip ribbon, which is passed through the stamping press in order to produce the required stamping exactly as it will appear after performing all operations [2].
The interest of researchers and practitioners on progressive die design continues due to its high capability to increase productivity. Research on progressive work continues (e.g., [3–8]. [7]), analyzed and designed progressive die to combine cam and piercing operations previously done by different machine, in order to increase the machine utilization, decrease the time and costs for manufacturing [8], presented the forming features, layout and overall structure design of multistation progressive die, in addition to design key points of important parts of the highstrength steel plate of car mounting part. In fact, Progressive die design manufacturing extends to multiple applications [3], presented a technique for the design and development of progressive die for production of washers, [4], presented a design of progressive die for automobile dust cover [5], introduced a forming analysis and design of a progressive die for car bumper support [6], introduced design and development of a progressive die for manufacturing of chain link plate [9], investigated the cost of progressive die in the lamination stack production. They estimated the tooling cost based on the dimension and complexity of the stamping part, and by following design of the lamination and the selected stamping scenarios. Several methodologies and techniques were applied in modeling and optimizing the strip layout design. This includes: graphbased algorithms [10,11], such as, Petri net) [12], and Graphtheoretic methods [10–15], Knowledgebased systems [16,17], Singh and Sekhon (2006), [18,19] Genetic algorithm (GA) [20–22], and the Torque equilibrium methods [10,11,20,23].
Since this research focus on the implementation of the graphtheoretic approach we shall consider the review of literature on previous efforts in utilizing graphtheoretic methods in progressive die industry in Egypt. In striplayout, the graph theoretic method is another technique used successfully to solve the problem of strip layout. [10–15]) presented several contributions involving the application of the graphbased mathematical technique to produce a stamping sequence automatically in the design of progressive stamping dies and based on minimization of the torque difference between each two sides of the progressive die. Another approach is utilizing Petri net, pioneered by [12,24]. They applied Petri nets methodology in the planning and construction of a shearingcut progressive die's working conditions and workstations [25], presented a research work of developing graph theory to automatic generation of piercing sequence in the progressive dies design. They first classified stamping features by tolerance between features. Then, they clustered classes of features into workstation sets using a graph coloring algorithm and ordered these sets in order to determine an optimal sequence of workstations. They utilized an objective function for optimization as the minimization of the torque between two sides of the progressive die [26], introduced a system to extract the geometrical and topological information of a 3D CAD model of sheet metal parts design, complemented with enumerationbased graph traversal algorithms to address the manufacturability aspect. He analyzed and surveyed the flat patterns produced from current mathematicsbased search routines, specifically breadth first search (BFS) and depth first search (DFS) [27], presented a petrinet simulation model of strip layout. They presented two research contributions. The first applied the visual Petri net to simulate the sequential workstations in the strip layout of part and the second integrated the parametric design of strip layout and simulation using Petrinet technique.
In this research, we present a case study application of graphtheoretic approach for designing sheet metal strip layout design in Egypt. We analyzed the engineering design of a sheet metal part currently produced using laser cutting technology in some Egyptian factory in Cairo. We integrated the graphtheoretic techniques presented in the works of [13,15]. The implementation of the graph methodology was demonstrated on the case study part. Then, we stated the advantages and limitations, and potential utilization of such methodology in the Egyptian sheet metal industry.
The paper is organized as follows. Section 2 explains the concepts of modeling, generation and mapping of stamping features into stamping operations. Section 3 introduces the graphtheoretic concepts, roles and relationships related to the problem of strip layout design. Section 4 presents the methodological steps of the graphtheoretic based design of progressive die strip layout. A real strip layout design case study is introduced in Section 5. Finally, in the last section the conclusion is made.
Next section presents method of modeling, generating and mapping the stamping features.
2 Stamping feature modeling, generation and mapping
2.1 Defining stamping features
The geometric elements of the part design are translated into entities, called features. A sheet metal part may consist of the following standard sheet metal features:
Primary features: flat, tab, hem, drawing, etc.
Addon features: hole, cutout, slot, extrusion hole, emboss, countersink, etc.
Connective features: bend, jog, etc.
Featureoperation mapping is the transformation process of design and manufacturing information from stamping features into a set of stamping operations. Stamping operations are elements of a stamping process plan. Typical stamping operations include piercing, blanking, notching, cutoff, shaving, lancing, embossing, drawing, trimming, coining, etc. A stamping feature can be manufactured with one specific stamping operation or a combination.
2.2 Stamping features operations relationships
There are three critical types of relations among sheet metal features: isin, adjacentto, and precisionassociated. The isin relation indicates a negative feature (e.g., a hole, etc.) is in another feature (e.g. flat, etc.), while ison relation indicates a positive feature (e.g., emboss, etc.) is on another one (e.g. flat, etc.). The adjacentto relation is defined as connective feature which adjacent to another sheet metal feature (primary feature). The precisionassociated relation is used to indicate the case that a sheet metal feature does not directly connect to, but is associated with another sheet metal feature by a precision requirement referring to specific tolerance need. In the next section, we explain the 3rd dimension in modeling the stamping feature, which is the stamping features constraints.
2.3 Stamping operations constraints
The types of features' relations and manufacturability (i.e., ability of die stamping processes) add necessary elements to the modeling of the features structure contained in the sheet metal part and constitute important element to define problem constraints. In fact, the constraints in stamping are logic results of two types of natural restrictions:
The precedence constraints that there is the order of stamping operations to be followed based on overall stamped product feature.
The adjacency constraints that there is the due to the restriction of prohibiting performance of specific stamping features at the same stamping station.
Manufacturability rules are used to define precedence relationships, whereas dimensions and clearance restrictions are used to define the adjacency constraints.

Typical instances of precedence restrictions manufacturability rules are given below:
Progressive die stamping operation − Rule 1:
The piercing operations to stamp two pilot holes should be staged in the first station.
Progressive die stamping operation − Rule 2:
When embosses exist, if possible, they are embossed in the first station to prevent deformation of other stamping features.

Typical instances of adjacency restrictions manufacturability rules are given below:
Progressive die stamping operation − Rule 3:
If holes (except pilot holes) and scraps (that don't accommodate indirect pilot holes) cannot be stamped simultaneously in the same station, the process sequence is as follows: piercing operations precede notching operations.
Progressive die stamping operation − Rule 4:
If holes or scraps to be pierced are close to each other, then the adjacent holes or scraps should be shifted to next die stations to prevent weak die problem.
The featurebased part model is composed of a set of sheet metal features operations besides a set of precedence and adjacencies relationships, defined by the above stamping manufacturability rules. These stamping operations features, and relationships model defines the final product, but does not tell how the final product will be manufactured from the raw rolled sheet in progressive dies. Thus, an algorithm is needed to tell how those stamping operation features will be arranged into an optimal strip layout design. This will be achieved through utilizing a graphbased approach presented in this article, and to be implemented in the subsequent sections.
3 Graphtheoretic approach to stamping operation sequencing problem
3.1 Graph theory and representation of stamping constraints
A Graph G = (V, E) consists set of vertices denoted by V, or V(G) and set of edges E, or E(G). Graph may be directed (Fig. 1b), when lines connecting vertices (i.e., arcs) contains arrows at their ends, or may be undirected (Fig. 1a), when lines connecting vertices does not contain arrows at their ends.
In this research, simply vertices will represent stamping operations and edges and arcs will represent adjacency and precedence relationships, respectively. The adjacency relationships are represented by undirected graph whereas, the precedence relationships are represented by directed graph. Therefore, there are two types of constraint exist among each pair of stamping operations: Precedence constraints and Adjacency or cluster constraints. The two types of constraints can be described mathematically by two graphs and their equivalent matrices:
Operation precedence graph defined as Gp = (V,A), where V the vertices define the operations and the directed edges (arcs A) define the precedence constraints based on manufacturability rules. Each element in the operation precedence matrix can have a value of either 1,−1 or 0 where:
Operation adjacency graph is defined as G_{c} = (V,E), where V the vertices define the operations and the undirected edges E define the adjacency constraints. Two stamping operations cannot be arranged to the same stage only if the distance between their mapped feature are less than the minimum distance which is determined by the stamping material type and dimensions of standard dies and punches [14]. Each element in the operations adjacency matrix can have a value of either +1 or 0 where:
Fig. 1 (a) Undirected graph. (b) Directed graph. 
3.2 The problem statement of the sheet metal stamping
The problem of stamping operations sequencing can be stated as minimization of the number of die stations to reduce the die cost, while satisfying both the precedence and adjacency constraints. In terms of graph theory, the sequencing problem of stamping operations can be solved by partitioning the vertices V into a minimum number of sets of mutually independent vertices.
4 A graphtheoretic sheet metal die stamping methodology
In this section, we introduce the structured and systematic methodology following and integrating the works done in [13,15]. The methodology tabulated (Tab. 1) as follows. Six steps are followed to implement the graphtheoretic methodology to develop a stamping station sequence to create the required product sheet metal feature. The inputs and outputs of each step is given below.
Next section, we present the case study for implementing the graphtheoretic sheet metal die stamping
A methodology for graphtheoretic sheet metal die stamping.
5 Progressive die sheet metal stamping case study
This section presents a case study to illustrate the stamping operation sequencing algorithm. All computational steps of this methodology are performed starting from 3D CAD model of the part to the result of operation sequence.
Step A: Generate the stamping features in a strip model from the sheet metal features of the CAD model manually as shown in Figure 2.
Step B: Map stamping features (Design features) to stamping operations. An operation feature tree is created manually; Figure 3.
Step C: Generate the operation precedence matrix and adjacency matrix.

The precedence matrix (Tab. 2) is generated by the application of manufacturing rules (mentioned in Sect. 2.3).
Table 2Operation precedence matrix.

The adjacency matrices are generated manually as shown in Table 3.
Table 3Operation adjacency matrix.
The corresponding precedence and adjacency graphs are shown in Figures 4 and 5, respectively.
Step D:
Using the precedence matrix, cluster the operations into partially ordered sets utilizing a modified topological sorting algorithm. Get the clusters of operations as given below:
Step 1. Initialization. Copy the operation precedence matrix for use in this process; let the stamping step be 1; and initialize a operations list, L for the current stamping step i.
Step 2. Get all the nodes whose indegrees are zero and store them in list L.
Step 3. The corresponding row and column of operations in the list L, are then deleted from the precedence matrix and the remaining rows and columns are updated. This forms a new precedence matrix.
Step 4. Repeat Step 2, 3, until there is no operation left in the operation precedence matrix.
Step 5. Use the resulting operation lists to construct the operation sequence and stop.
For this part, the resulting operations step list sequence is as below:
Operation step list 1: Pierce hole 0, Pierce hole 4, Pierce slot 0, Pierce Pilo thole 0 hole1
Operation step list 2: Pierce hole 1, Pierce hole 2, Pierce hole 3, Pierce slot 1, Pierce slot 2, Pierce slot 3, Notch scrap 0,1
Operations step list 3: U Bend Bend 0_Bend 1
Operations step List 4: U Bend 2
Operations step list 5: U Bend 3
Operations step List 6: U Bend Bend 4_Bend 5
Operations step List 7: Notch Scrap 2
This gives up the minimum number of progressive die station, 7.
Step E:
Generate the SOAG (Fig. 5) by applying graph coloring algorithm through the following steps:
Arrange the vertices by decreasing order of degree.
Color a vertex of maximal degree with color 1.
Choose a vertex with a maximal saturation degree. If there is an equality, choose any vertex of maximal degree in the uncolored sub graph.
Color the chosen vertex with the least possible (lowest numbered) color.
If all the vertices are colored, stop. Otherwise, return to 3.
Now, after applying the graph coloring algorithm, this results in the 8 clusters, after moving down the operation: pierce slot 1, in a separate station because of adjacency with the pierce slot 2, in SOAG2. This results finally in 8 joint operations (JOPs) as shown in Figures 6 and 7.
Step F:
In this step, we verify stamping sequence in Figures 6 and 7 using index of priority (IOP) matrix in Table 4, through computing the priority index of each joint operation, by summing the individual priorities of its stamping operations list. Then, calculate IOP for each joint operation by summing its row. Now, the joint operations are sequenced using an iterative procedure. For the first iteration, operation JOP1 is selected first as its IOP has the largest positive value, 2. It should be moved to the first row and column, if not the case, and a submatrix is generated that excludes this operation; new IOP values are computed. The output of the first and second iterations is shown in Table 5.
This process is repeated until all operations have been ordered. The resulting sequence is JP1 > JP 2 > JP3 > JP4 > JP5 > JP6 > JP7 > JP8. Then, the sequence shown in Figures 6 and 7 is correct and verified. Therefore, the resulting progressive stamping operation sequence is:
Station 1: Pierce hole 0, Pierce hole 4, Pierce slot 0, Pierce Pilot hole 0 hole 1
Station 2: Pierce hole 1, Pierce hole 2, Pierce hole 3, Pierce slot 2, Pierce slot 3, Notch scrap 0,1
Station 3: Pierce solt 1
Station 4: U Bend Bend 0_Bend 1
Station 5: U Bend 2
Station 6: U Bend 3
Station 7: U Bend Bend 4_Bend 5
Station 8: Notch Scrap 2
The strip passes through 8 stations to produce the part, the final result is an optimal operations sequence (minimum number die stations) satisfying all the precedence constraints and closeness constraints among the constituent stamping operations. The resulting strip layout is in Figure 8. Figures 9 and 10 show the engineering drawing and 3D of the manufactured part, respectively.
Fig. 2 Featurebased model of the studied part. 
Fig. 3 Stamping features' operations tree of the part. 
Fig. 4 Operation Precedence Graph (OPG) is acyclic. 
Fig. 5 Operation Adjacency Graph (OAG). 
Fig. 6 Applying the modified topological sorting and DSATUR graph coloring algorithm. 
Fig. 7 Joint Operations resulting from graph coloring algorithm. 
Initial (unordered) operation precedence matrix.
IOP Matrix after 2nd iteration.
Fig. 8 Resulting strip layout. 
Fig. 9 Engineering drawing of the part. 
Fig. 10 3D drawings of the manufactured part. 
6 Conclusion
A graphtheoretic technique for designing the strip layout of the progressive die has been implemented on a part, that is currently manufactured by laser cutting in Egypt.
The graphbased technique is efficient in term of computational time, systematic, practical, understandable, and transparent. The technique logically analyzes the stamping features and corresponding operations yet maintain capability to satisfy precedence and adjacency constraints and limitations. It allows the designer to implement all manufacturability rules and achieve realistically reliable design.
The graph theoretic technique is simple, systematic, practical and computationally efficient approach, and can be considered an important factor to act to promotes the sheet metal progressive die industry in Egypt. In turn, the adotion of progressive die manufacturing will improve the productivity of the sheet metal stamping process in Egypt.
In general, the progressive die manufacturing can increase productivity of sheet metal works in Egypt, only in situations of mass production. The limitation is that it requires considerable skill level and training for labor to conduct the process of strip layout design.
References
 J.R. Paquin, Die Design Fundamentals, Industrial Press Inc., New York, N.Y., Machinery Publishing co., LTD, Brighton 1, England, 1992 [Google Scholar]
 B.K.A. Ngoi, C.K. Chua, A knowledgebased system for strip layout design, Comput. Ind. 25, 31–44 (1994) [Google Scholar]
 U.K. Annigeri, Y.P. Deepthi, Design and development of progressive tool for manufacturing washer. in: AIP Conference Proceedings, AIP Publishing LLC, Vol. 1859, No. 1, 2017, p. 020107 [Google Scholar]
 X. Chaohui, Design on progressive die for automobile dust cover, J. Forg. Stamp. Technol. 43, 129–134 (2018) [Google Scholar]
 W. Jie, Z. Xue, Z. Li et.al., Forming analysis and progressive die design for car bumper support, J. Forg. Stamp. Technol. 43, 122–125 (2018) [Google Scholar]
 I. Rehaman, P.S. Reddy, M. Manoj, N.G. Murthy, Design and analysis of progressive die for chain link plate, Int. J. Recent Technol. Eng. 8, 820–826 (2019) [Google Scholar]
 R. Rahul, M. Thenarasu, Design of combined cam and piercing progressive die set for a sheet metal component, Int. J. Emerg. Technol. 11, 570–573 (2020) [Google Scholar]
 Y. Gen, W. Yunong, Progressive stamping process and die design of high strength steel automobile structural parts, J. Phys. Conf. Ser. 1605, 012063 (2020) [Google Scholar]
 J. Zhang, D. Spath, Progressive die cost estimation based on lamination design and production scenario in the electric traction motor application, Procedia Manuf. 39, 635–644 (2019) [Google Scholar]
 C.Y. Chu, S.B. Tor, G.A. Britton, A graph theoretic for stamping operations sequencing, IMechEPart B 218, 467–471 (2004a) [Google Scholar]
 C.Y. Chu, S.B. Tor, G.A. Britton, A graph theoretic operations sequencing approach for progressive die design, in: Proceedings of the 34th International MATADOR Conference, 2004b, pp. 69– 74 [Google Scholar]
 Z.C. Lin, C.H. Deng, Application of PertiNet in the planning of a shearing cut and bending progressive die workstation, Int. J. Mater. Prod. Technol. 16, 579–591 (2001a) [Google Scholar]
 C.Y. Chu, A methodology for automatic operation Sequencing for progressive die design, PhD Thesis, School of Mechanical and Aerospace Engineering, Nanyang Technological University (2007) [Google Scholar]
 C.Y. Chu, S.B. Tor, G.A. Britton, A graph theoretic algorithm for automatic operation sequencing for progressive die design, Int. J. Prod. Res. 46, 2965–2988 (2008) [Google Scholar]
 C.Y. Chu, A graph and matrix based approach for stamping operation sequencing for progressive die design, Adv. Mater. Res. AMR, 421, 564–569 (2012) [Google Scholar]
 S.B. Tor, G.A. Britton, W.Y. Zhang, Knowledgebased blackboard framework for stamping process planning in progressive die design, Int. J. Adv. Manuf. Technol. 26, 774–783 (2005a) [Google Scholar]
 S.B. Tor, G.A. Britton, W.Y. Zhang, A hybrid intelligent system for stamping process planning in progressive die design, in: Innovation in Manufacturing Systems and Technology Conference, IOMST09, 2005b [Google Scholar]
 S. Kumar, R. Singh, ISSLD: an intelligent system for strip layout design for sheet metal operation on progressive die, in: 14th ISME International Conference on Mechanical Engineering in Knowledge Age, December 12–14, Delhi College of engineering, Delhi110042, India, Ref. 213, 2005 [Google Scholar]
 S. Salunkhe, S. Kumar, H.M.A. Hussein, An expert system for automatic design of compound dies, 2016. DOI: 10.1007/9789811022517_8. [Google Scholar]
 Z.C. Lin, C.H. Deng, Analysis of torque equilibrium model and the optimal strip working sequence for a shearingcut and bending progressive die, J. Mater. Process. Technol. 115, 301–312 (2001b) [Google Scholar]
 H.C. Chang, Y.T. Tsai, K.T. Chiu, A novel optimal working process in the design of parametric progressive dies, Int. J. Adv. Manuf. Technol. 33, 915–928 (2007) [Google Scholar]
 T. Serdar, Progressive die strip layout optimization for minimum unbalanced moments, J. Manuf. Sci. Eng. 132, 0245021–0245027 (2010) [Google Scholar]
 Z.C. Lin, C.C. Chen, The application of the moment equilibrium model to the offset of pressure center of trimming progressive die in IC packaging machine, J. Mater. Process. Technol. 140, 653–661 (2003) [Google Scholar]
 Z.C. Lin, J.M. Chang, W.C. Lu, Application of PetriNet in the planning of shearingcut progressive die's workstation, J. Chin. Soc. Mech. Eng. 20, 139–146 (1999) [Google Scholar]
 M.A. Farsi, B. Arezoo, Development of a new method to determine bending sequence in progressive dies, Int. J. Adv. Manuf. Technol. 43, 52–60 (2009) [Google Scholar]
 A. Qattawi, A. Mayyas, M.A. Omar, An investigation of graph traversal algorithms in folded sheet metal parts design, Int. J. Adv. Manuf. Technol., 2013. DOI: 10.1007/s0017001351819 [Google Scholar]
 H.M.A. Hussein, S. Kumar, E.S. Abouel Nasr, Computeraided design and simulation of strip layout for progressive die planning using Petri nets, Adv. Mech. Eng. 8, 1–9 (2016) [Google Scholar]
Cite this article as: Shady Aly, Hend Abdelaaty, Osama Muneer Dawood, Hussein M. A. Hussein, Optimization of striplayout using graphtheoretic methodology for stamping operations on progressive die: a case study, Int. J. Simul. Multidisci. Des. Optim. 12, 5 (2021)
All Tables
All Figures
Fig. 1 (a) Undirected graph. (b) Directed graph. 

In the text 
Fig. 2 Featurebased model of the studied part. 

In the text 
Fig. 3 Stamping features' operations tree of the part. 

In the text 
Fig. 4 Operation Precedence Graph (OPG) is acyclic. 

In the text 
Fig. 5 Operation Adjacency Graph (OAG). 

In the text 
Fig. 6 Applying the modified topological sorting and DSATUR graph coloring algorithm. 

In the text 
Fig. 7 Joint Operations resulting from graph coloring algorithm. 

In the text 
Fig. 8 Resulting strip layout. 

In the text 
Fig. 9 Engineering drawing of the part. 

In the text 
Fig. 10 3D drawings of the manufactured part. 

In the text 