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/ .

We studied robustness of symmetrically coupled interdependent networks against load failures when the flow dynamics is dominated by global redistribution based on weighted betweenness centrality. Three kinds of weighting schemes, which are random, clustering-based, and degree-based, respectively, were compared. We demonstrated that both the clustering-based and degree-based weighting scheme outweigh random weighting on robustness against the cascade of load failures in the symmetrically coupled interdependent networks. In a limited range of weighting parameters, degree-based weighting scheme outweigh clustering-based scheme. Outside of that range, clustering-based weighting scheme outweigh degree-based scheme. And it will be easier for the symmetrically coupled interdependent network to achieve robustness against one-node removal and better cost configuration against the cascade of load failures when relative interconnection intensity was weaker under degree-based and clustering-based weighting schemes. Our findings might have great generality for characterizing load-failure-induced cascading dynamics in real-world weighted interdependent networks.