**A new setup design algorithm for generated shared pres-brake setups for sheet metal bending**. Sheet metal bending press-brakes can be setup to produce more than one type of part without requiring a setup change. To exploit this flexibility, we need setup planning techniques so that press-brake setups can be shared among many different parts. To solve this problem, we have developed the following two new algorithms:

A part family formation algorithm:We showed that the part family formation problem is NP hard by reducing it to the bin packing problem. We developed a greedy algorithm to generate part families using a bottom-up approach. This algorithm makes use of the mixed integer linear programming formulation (described below) for generating setup for each part family.A mixed integer programming based single setup generation algorithm:We developed a new approach to solve this problem on based on mixed integer programming and offers the following two advantages over the earlier approach. First, for moderate sized problems (30 total bends and 5 tooling stages) it finds the optimal setups as opposed to approximate solutions generated by earlier approach. Second, as opposed to only minimizing the number of stages, it also allows us to minimize the total stage length and allows us to place the stages on a press brake such that the press brake length used up is minimal. We can therefore accommodate greater number of parts in a single setup.

We expect that by producing many different types of parts on the same setup, we can significantly reduce the number of setup operations, improve machine tool utilization and enable cost-effective small-batch manufacturing.

**A new algorithm for selecting shared bending punches**. In sheet-metal bending, bends are formed using a combination of a punch and a die. These tools need to be able to withstand the bending forces, and their shapes should be such that there is no tool-part interference. Our methodology for automatically synthesizing shapes of bending punches involves the following three steps:

- Extract constraints on punch parameters, by performing intersection checks between geometric entities that define the parametric punch shape and geometric entities that define various intermediate workpiece shapes resulting during the bending process. We use parametric geometric models of punches to describe the family of possible punch shapes. The resulting constraints on punch parameters are quadratic in nature for sash type (i.e., 2.5D) parts.
- Find a punch shape that does not intersect with any intermediate workpiece shape and has the maximum strength. For this, we use a combination of state-space search and mixed integer programming to try to find a punch shape that satisfies all intersection constraints generated in the previous step and maximizes the punch strength.
- Verify that the designed punch can withstand stresses resulting from the bending forces.

Our approach provides a systematic methodology for designing punches for sash type (i.e., 2.5D) parts. The approach naturally extends to multi-part tool design problems for 2.5D parts. This approach offers the following two benefits. First, it helps process planners in selecting a single punch shape that will work for multiple types of parts. This will help in reducing the setup times and setup costs for the small batch manufacturing environment. For the example of ten parts, a single-part planning approach would have resulted in ten setup changes while multi-part planning reduces the number of setups to one. Second, a single tool is used to bend multiple parts. This leads to a reduction in the cost of tools. For the example of ten parts, a single tool for each part would have resulted in ten different tools while our results in one tool for all the ten parts.

**A new algorithm for selecting shared milling tools for multiple parts.**For the manufacture of milled parts, it is well known that the size of the milling cutters significantly affects the machining time. However, for small-batch manufacturing, the machine-tool reconfiguration time (i.e., the time spent on loading tools into the tool magazine and establishing z-length compensation value) is just as important. If we can select a set of milling tools that will produce good machining time on more than one type of parts, then several unnecessary machine-tool reconfiguration operations can be eliminated and the machine-tool can be used for longer periods without requiring reconfiguration.

We have developed a geometric algorithm for finding an optimal sequence of milling cutters for multi-pass machining of sets of 2.5D parts. In selecting milling cutters we consider both the tool loading time and the machining time and generate solutions that allow us to minimize the total manufacturing time. Our problem formulation addresses the general problem of how to cover a target region to be milled with a cylindrical cutter without intersecting with the obstruction region; this general definition allows us to handle both open and closed edges in the target region. Our algorithm works as follows:

Our tool selection algorithm improves upon previous work in the tool selection area in following ways: (1) it can handle both closed as well as open edges, (2) in selecting cutters it accounts for the tool loading time, and (3) it can simultaneously consider multiple different parts and select the optimal set of cutters to minimize the total manufacturing time.

- Given a set of available cutters, compute the area that each cutter is capable of covering. In general, smaller the cutter size, the more area it can cover. We find the coverable area by first offsetting the obstruction region, and then doing inverse-offsetting.
- Formulate the problem of finding an optimal sequence of milling cutters as a shortest path problem on a digraph, and use Dijkstra's algorithm to solve it.

**A new virtual node generation scheme for sheet metal bending.**A large number of manufacturing operation planning problems can be formulated as state-space search problems. In case of sheet-metal bending operation planning, processing a search node involves extensive geometric reasoning. Such computation-intensive node-processing limits the number of search nodes that can be expanded in a reasonable amount of time, making it difficult to solve real-life operation planning problems. We have developed a new scheme to speed up operation planning by virtual generation of state-space nodes. In this scheme, we eliminate unnecessary computation at the time of node generation by extracting the required information from already generated nodes. Although generation of two different search nodes rarely involves identical computation steps, there is considerable overlap in node generation steps. We have divided the node generation step into a number of computation subproblems. When we need to generate a new node, we first try to see if any of the node generation subproblems have been solved for any of the already generated nodes. If any subproblem has already been solved for some other node, then we use the solution of that subproblem to save computation time. In such cases, we do not perform node generation computation steps, and therefore we call such node generation virtual. This scheme increases the node generation capability and allows us to consider many more search nodes. The ability to consider more search nodes helps us in solving more complex problems and finding better operation plans.

- S.K. Gupta, S.K. Saini, B.W. Spranklin, and Z. Yao. Geometric algorithms for computing cutter engagement functions in 2.5D milling operations. Computer Aided Design, 37(14):1469-1480, 2005.
- Z. Yao and S.K. Gupta. Cutter path generation for 2.5D milling by
combining multiple different cutter path patterns. International Journal of Production
Research, 42(11):2141—2161, 2004.

- Z. Yao, S.K. Gupta, and D. Nau. Algorithms for Selecting Cutters
in
Multi-Part Milling Problems.
*Computer Aided Design*, 35(9):825--839, 2003. - S.K. Gupta and D. Rajagopal. Sheet metal bending: Forming part
families
for shared setup generation.
*Journal of Manufacturing Systems*, 21(5):329--350, 2002. - U. Alva and S.K. Gupta. Automated design of sheet metal punches
for
bending multiple parts in a single setup.
*Robotics and Computer Integrated Manufacturing*, 17(1/2):33--47, 2001. - S.K. Gupta. Sheet metal bending operation planning: Using virtual
node
generation to improve search efficiency.
*Journal of Manufacturing Systems*, 18(2):127--139, 1999. - S.K. Gupta and D.A. Bourne. Sheet metal bending: Generating
shared
setups. A
*SME Journal of Manufacturing Science and Engineering*, 121:689--694, November 1999.

Dr. Satyandra K. Gupta

Department of Mechanical Engineering and Institute for Systems Research

2135 Martin Hall

University of Maryland College Park, Md-20742

Phone: 301-405-5306

FAX: 301-314-9477

WWW: http://www.glue.umd.edu/~skgupta/