×

Minimization of the number of tool switches on a flexible manufacturing machine. (English) Zbl 0814.90038

Summary: 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.
We propose two new heuristics. 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.

MSC:

90B30 Production models
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
PDFBibTeX XMLCite