Process Planning for Small Batch Manufacturing

Main Participants: Satyandra K. Gupta, Ujval Alva, Deepak Rajagopal, and Zhiyang Yao

Sponsor: This project was sponsored by the National Science Foundation. We have also received in-kind support from Spatial Technologies and Amada for this project.

Keywords: Process Planning, Tool Design, and Setup Planning

Motivation

Increasing emphasis on more personalized products and shrinking product lives is resulting in major changes in manufacturing practices. Increasingly, the manufacturing industry is moving towards high part mixes, which makes it important to reduce setup and tooling operations. For example, if a machine-tool is not configured to accommodate more than one part within a part family, then large amounts of time will repeatedly be spent on reconfiguring the machine-tool (i.e., loading new tools and fixtures into the machine-tool) each time a request is received for manufacturing a different part. Such reconfigurations are the major source of inefficiency in small batch manufacturing. If the machine-tool were configured from the beginning to accommodate several different parts within the part family, much of the cost of reconfiguring the machine-tool could be avoided. This requires considering all of the parts that need to be produced during the given operational period, and selecting tools and machine-tool configurations that can work for multiple different parts. We have developed a general planning framework for creating shared machine-tool configurations and have applied them to three application areas.

Main Results and Their Anticipated Benefits

Our main results in this project include the following:

  • 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:
  1. 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.
  2. 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:
  1. 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.
  2. 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.
  3. 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:

  1. 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.
  2. 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.

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.

  • 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.

Related Publications

The following papers provide more details on the above-described results.

  • 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. ASME Journal of Manufacturing Science and Engineering, 121:689–694, November 1999.

Some of these papers are available at the publications section of the website.

Contact

For additional information and to obtain copies of the above papers please contact:

Dr. Satyandra K. Gupta
Viterbi School of Engineering
University of Southern California
Los Angeles, California 90089-1453
Phone: 213-740-0491
Email: guptask [AT] usc [DOT] edu