Improved heuristic algorithms for the Job Sequencing and Tool Switching Problem

In flexible manufacturing systems, a single machine can be configured with different tools for processing different jobs, each requiring a specific set of tools. There is a limit to the maximum number of tools that can be loaded simultaneously in the machine; between the processing of two different jobs, it may be necessary to switch these tools, causing interruptions in the production line. The Job Sequencing and Tool Switching Problem (SSP) aims to determine a job sequence and the tool-loading order for a flexible machine, in order to minimize the number of tool switches. These two tasks can be separated into Sequencing, an NP-hard problem, and Tooling, which is a P problem if the job sequence is given. This paper proposes a methodology that uses graph representations, heuristic methods, and local search methods to solve the sequencing problem. These contributions are combined in an Iterated Local Search scheme, which is then combined with a classical tooling method, in order to solve the SSP. Comprehensive computational experiments show that the resulting method is competitive and can establish new best solutions for literature instances, while outperforming the current state-of-the-art method.