A heuristic approach based on magazine configurations to solve the Job Sequencing and Tool Switching Problem

This paper addresses the Job Sequencing and Tool Switching Problem (SSP) in its uniform version, where the objective is to minimize the total number of tool switches on a single machine with limited magazine capacity. A new heuristic framework based on a configurationdriven interpretation of the problem is presented, in which solutions are constructed by selecting and sequencing a reduced subset of magazine configurations. The method combines a multi-start strategy with diversified configuration generation mechanisms guided by Next Job and Next Tool selection strategies, along with a controlled level of randomness. An additional mixing and improvement phase exploits information gathered across iterations to refine the configuration pool. Computational experiments on small benchmark instances from the literature show that the proposed approach is promising in identifying high-quality solutions, achieving optimality in 93% of the small tested instances with known optimal solutions, while maintaining low computational effort.