An algorithmic framework for tool switching problems with multiple objectives

The tool switching problem is a classical and extensively studied problem in flexible manufacturing systems. The standard example is a CNC machine with a limited number of tool slots to which tools for drilling and milling have to be assigned, with the goal of minimizing the number of necessary tool switches and/or the number of machine stops over time. In this work we present a branch-and-bound based algorithmic framework for a very general and versatile formulation of this problem (involving arbitrary setup and processing times) that allows addressing both of these objectives simultaneously (or only of them), and that improves over several known approaches from the literature. We demonstrate the usefulness of our algorithm by rigorous theoretical analysis and by experiments with both large real-world and random instances.