Tool switching problems with tool order constraints

This article addresses four different variants of the well-known Tool Switching Problem (ToSP). For each variant, we discuss its complexity and propose a mathematical formulation. Motivated by a real -world application in the color printing industry, the third and fourth variants introduce a novel requirement into ToSP: the tool order constraint. Under this requirement, during the processing of each job, the selected tools must be sorted along the slot sequence in the machine, and the machine will use them for processing the job applying the tools in that order. We show that the new problem variants are NPhard even when the job sequence is given as part of the input and the setup times are binary. We solve them by using dedicated arc flow models. We evaluate the effectiveness of the models on several instances that were generated with the aim of covering different scenarios of interest. Our code finds proven optimal solutions for most of the instances with up to 30 jobs, 60 tools and 10 slots. (c) 2024 Elsevier B.V. All rights reserved.