Branch and fathoming algorithms for operation sequencing in process planning

This paper focuses on the operation sequencing problem in process planning, which is the problem of determining the sequence of operations required for producing a part with the objective of minimizing the sum of machine, set-up and tool change costs. In general, operation sequencing in process planning has been a difficult optimization problem, since it has combinatorial characteristics and complex precedence relations. This paper first suggests a precedence-directed graph to describe the precedence relations among operations with a compact form. Then, using the directed graph, the authors develop optimal and heuristic branch and fathoming algorithms that can give optimal and near optimal solutions respectively. Application of the two algorithms is illustrated using an example part. Also, to show the performance of the suggested algorithms, computational experiments were done on randomly generated problems and the results show that the heuristic algorithm gives optimal solutions for all the general problems with much shorter computation time.