This paper addresses a joint part sequencing and tool replacement problem on a machining center. The objective is to minimize the expected production cost subject to available tool spares. In literature, it has been shown that the sequencing problems with sequence-dependent setups are equivalent to the `travelling salesman problem` (TSP) and thus are NP-complete. In the problem under consideration, the cost components associated with tool replacement and defective part cost may be different if their position relative to other parts in the sequence is changed. This, coupled with the sequence-dependent setups, precludes optimal solutions for any meaningful sized problems. To provide quick and reasonably good solutions, we propose a `nearest neighbor heuristic` (NNH). The efficiency of the NNH algorithm is demonstrated with an example problem. The effects of tool spare level on the expected production cost are also discussed.

Keywords