A Memetic Algorithm for the Tool Switching Problem

This paper deals with the Tool Switching Problem (ToSP), a well-known problem in operations research. The ToSP involves determining a job sequence and the tools to be loaded on a machine with the goal of minimizing the total number of tool switches. This problem has been tackled by a number of algorithmic approaches in recent years. Here, we propose a memetic algorithm that combines a problem-specific permutational genetic algorithm with a hill-climbing procedure. It is shown that this combined approach outperforms each of the individual algorithms, as well as an ad-hoc beam search heuristic defined in the literature for this problem.