Minimization of the number of tool switches on a flexible manufacturing machine

The paper considers the problem of sequencing a set of jobs on a single machine having a limited capacity tool magazine. Each job requires a subset of tools for its processing. If these tools are not present in the magazine, one or more tools must be removed and replaced by others. The problem is to find the best job sequence such that the number of tool switches is minimized. This NP-hard problem has been proposed by Tang and Denardo. Two new heuristics are proposed. The first one is based on an insertion method and the second one is an adaptation of the general tabu search techniques. These two new heuristics are compared with the previous ones and tested on problems of different sizes. They give better results while requiring less computation time.