A Computational Study of the Tool Replacement Problem

In the Tool Replacement Problem (TRP) for the given sequence of jobs, we consider a discretized interval where each point in time corresponds to a specific job and its collection of tools sufficient to complete that job. A passive interval w.r.t. a specific tool is an interval where that tool is not used at any point within that interval but is used at the boundary points in time. The TRP aims to find a loading schedule of tools (tool switches) that minimizes the total number of tool loadings in the magazine. Based on the concept of a passive interval, we introduce our reformulation of the TRP as follows. The minimum total number of tool loadings (switches) in the TRP is equal to the difference between the total number of tools for all scheduled jobs with tool repetitions and the maximum total number of passive intervals. We solve the TRP to optimality by designing and implementing two algorithms: one for finding the optimal objective function value (Insertion Greedy Algorithm (IGA)) and the other (To Full Magazine (ToFullMag) algorithm) for finding an optimal solution, that is, an optimal sequence of tool loadings. We apply our reformulation of the TRP to design the IGA full algorithm starting with IGA and continuing with ToFullMag. The IGA full achieves the best possible running time and thus settles the computational complexity of TRP. We prove that IGA full outperforms the most popular Keep Tool Needed Soonest (KTNS) algorithm by at least an order of magnitude in terms of CPU time. Moreover, after replacing the KTNS algorithm by IGA full within the state-of-the-art Hybrid Genetic Searches heuristic for solving the job Scheduling and tool Switching Problem (SSP), our computational study shows the reduction of CPU times by at least an order of magnitude for medium- and large-scale SSP data sets. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research of Y. Qiu and P. M. Pardalos is supported by the National Natural Science Foundation of China [Grant 72371135], the National Foreign Expert Program from the Ministry of Science and Technology of China [Grant G2021014038L], and the Key Project from Jiangsu Social Science Foundation [Grant 23GLA001]. M. Cherniavskii and B. Goldengorin were supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye), Project No. FSMG-2024-0025. The work of P. M. Pardalos was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE). The article was prepared within the framework of the project “Scientific and Educational Mathematical Center, North-West Center for Mathematical Research named after Sofia Kovalevskaya”, 2025. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0474 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0474 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .