This paper considers the problem of operation sequencing in nonlinear process planning, which is the problem of selecting and sequencing operations required to produce a part with the objective of minimizing the sum of operation processing costs and machine, setup and tool change costs. Main constraints are the precedence relations among operations. The problem can be decomposed into two subproblems: operation selection and operation sequencing. We suggest four simulated annealing algorithms, which solve the two subproblems iteratively until a good solution is obtained. Here, the operation selection problem can be solved using a shortest path algorithm. Application of the algorithms is illustrated using an example. Also, to show the performances of the suggested algorithms, computational experiments were done on randomly generated test problems and the results are reported. In particular, one of the suggested algorithms outperforms an existing simulated annealing algorithm.