A new directed graph approach for automated setup planning in CAPP

Abstract

The task of setup planning is to determine the number and sequence of setups and the machining features or operations in each setup. Now there are three main methods for setup planning, i.e., the knowledge-based approach, the graph-based approach and the intelligence algorithm-based approach. In the knowledge-based and graph-based approaches reported in the literature, the main problem is that there is no guarantee that all precedence cycles between setups can be avoided during setup formation. The methods to break precedence cycles between setups are to split one setup into smaller setups. However, the implementation of this method is difficult and complex. In the intelligence algorithm-based approach, the method to handle the precedence constraints is a penalty strategy, which does not reflect the influence of precedence constraints on setup plans explicitly. To deal with the above deficiencies, a new directed graph approach is proposed to describe precedence constraints explicitly, which consists of three parts: (1) a setup precedence graph (SPG) to describe precedence constraints between setups. During the generation of the SPG, the minimal number of tolerance violations is guaranteed preferentially by the vertex clusters algorithm for serial vertices and the minimal number of setups is achieved by using variants of the breadth-first search. Precedence cycles between setups are avoided by checking whether two serial vertex clusters can generate a cycle; (2) operation sequencing to minimise tool changes in a setup; and (3) setup sequencing to generate optimal setup plans, which could be implemented by a topological sort. The new directed graph approach will generate many optimal or near-optimal setup plans and provide more flexibility required by different job shops. An example is illustrated to demonstrate the effect of the proposed approach.

Keywords:

• CAPP
• setup planning
• directed graph
• vertex clusters
• operation precedence graph
• setup precedence graph

Acknowledgements

The project was supported by the National High-Tech. R&D Program for CIMS, China (No. 2007AA04Z140), National Natural Science Foundation, China (No. 50375097), the Research Fund for Doctoral Program of Higher Education, China (No. 20070248020), and Shanghai Leading Academic Discipline (No. Y0102). The authors express sincere appreciation to the anonymous referees for their helpful comments to improve the quality of the paper.