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

Abstract

In this paper we consider 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. In this article we propose two new heuristics. The first one is based on an insertion method andthe 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.