IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v38y2026i1p86-101.html

A Computational Study of the Tool Replacement Problem

Author

Listed:
  • Yuzhuo Qiu

    (School of Business, Nanjing University of Information Science and Technology, Nanjing 210044, China; and School of Management, University of Science and Technology of China, Hefei 230026, China)

  • Mikhail Cherniavskii

    (Laboratory of Discrete and Combinatorial Optimization, Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology, Dolgoprudny, Moscow region 141700, Russia)

  • Boris Goldengorin

    (Department of Discrete Mathematics, Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology, Dolgoprudny, Moscow region 141700, Russia; and Scientific and Educational Mathematical Center “Sofia Kovalevskaya Northwestern Center for Mathematical Research,” Pskov State University, Pskov, Pskovskaya oblast’ 180000, Russia)

  • Panos M. Pardalos

    (Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611; and LATNA, National Research University Higher School of Economics, Moscow 101000, Russia)

Abstract

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.

Suggested Citation

  • Yuzhuo Qiu & Mikhail Cherniavskii & Boris Goldengorin & Panos M. Pardalos, 2026. "A Computational Study of the Tool Replacement Problem," INFORMS Journal on Computing, INFORMS, vol. 38(1), pages 86-101, January.
    • Handle: RePEc:inm:orijoc:v:38:y:2026:i:1:p:86-101
    DOI: 10.1287/ijoc.2023.0474
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.0474
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.0474?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. CATANZARO, Daniele & GOUVEIA, Luis & LABBE, Martine, 2015. "Improved integer linear programming formulations for the job Sequencing and tool Switching Problem," LIDAM Reprints CORE 2699, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Ann E. Gray & Abraham Seidmann & Kathryn E. Stecke, 1993. "A Synthesis of Decision Models for Tool Management in Automated Manufacturing," Management Science, INFORMS, vol. 39(5), pages 549-567, May.
    3. Christopher S. Tang & Eric V. Denardo, 1988. "Models Arising from a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches," Operations Research, INFORMS, vol. 36(5), pages 767-777, October.
    4. Christopher S. Tang & Eric V. Denardo, 1988. "Models Arising from a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching Instants," Operations Research, INFORMS, vol. 36(5), pages 778-784, October.
    5. Dorothea Calmels, 2019. "The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends," International Journal of Production Research, Taylor & Francis Journals, vol. 57(15-16), pages 5005-5025, August.
    6. Catanzaro, Daniele & Gouveia, Luis & Labbé, Martine, 2015. "Improved integer linear programming formulations for the job Sequencing and tool Switching Problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 766-777.
    7. Tiago Tiburcio da Silva & Antônio Augusto Chaves & Horacio Hideki Yanasse, 2021. "A new multicommodity flow model for the job sequencing and tool switching problem," International Journal of Production Research, Taylor & Francis Journals, vol. 59(12), pages 3617-3632, June.
    8. Dang, Quang-Vinh & van Diessen, Thijs & Martagan, Tugce & Adan, Ivo, 2021. "A matheuristic for parallel machine scheduling with tool replacements," European Journal of Operational Research, Elsevier, vol. 291(2), pages 640-660.
    9. Crama, Yves & Moonen, Linda S. & Spieksma, Frits C.R. & Talloen, Ellen, 2007. "The tool switching problem revisited," European Journal of Operational Research, Elsevier, vol. 182(2), pages 952-957, October.
    10. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    11. Anupma Yadav & S.C. Jayswal, 2018. "Modelling of flexible manufacturing system: a review," International Journal of Production Research, Taylor & Francis Journals, vol. 56(7), pages 2464-2487, April.
    12. Daniele CATANZARO & Luis GOUEIA & Martine LABBE, 2015. "Improved integer linear programming formulations for the job. Sequencing and tool switching problem," LIDAM Reprints CORE 2773, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Van Hop, Nguyen & Nagarur, Nagendra N., 2004. "The scheduling problem of PCBs for multiple non-identical parallel machines," European Journal of Operational Research, Elsevier, vol. 158(3), pages 577-594, November.
    14. Raduly-Baka, Csaba & Nevalainen, Olli S., 2015. "The modular tool switching problem," European Journal of Operational Research, Elsevier, vol. 242(1), pages 100-106.
    15. Mark Daskin & Philip C. Jones & Timothy J. Lowe, 1990. "Rationalizing Tool Selection in a Flexible Manufacturing System for Sheet-Metal Products," Operations Research, INFORMS, vol. 38(6), pages 1104-1115, December.
    16. Beezão, Andreza Cristina & Cordeau, Jean-François & Laporte, Gilbert & Yanasse, Horacio Hideki, 2017. "Scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 257(3), pages 834-844.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Akhundov, Najmaddin & Ostrowski, James, 2024. "Exploiting symmetry for the job sequencing and tool switching problem," European Journal of Operational Research, Elsevier, vol. 316(3), pages 976-987.
    2. Calmels, Dorothea, 2022. "An iterated local search procedure for the job sequencing and tool switching problem with non-identical parallel machines," European Journal of Operational Research, Elsevier, vol. 297(1), pages 66-85.
    3. Dang, Quang-Vinh & van Diessen, Thijs & Martagan, Tugce & Adan, Ivo, 2021. "A matheuristic for parallel machine scheduling with tool replacements," European Journal of Operational Research, Elsevier, vol. 291(2), pages 640-660.
    4. Khadija Hadj Salem & Vincent Jost & Yann Kieffer & Luc Libralesso & Stéphane Mancini, 2022. "Minimizing makespan under data prefetching constraints for embedded vision systems: a study of optimization methods and their performance," Operational Research, Springer, vol. 22(3), pages 1639-1673, July.
    5. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    6. Beezão, Andreza Cristina & Cordeau, Jean-François & Laporte, Gilbert & Yanasse, Horacio Hideki, 2017. "Scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 257(3), pages 834-844.
    7. Furrer, Martina & Mütze, Torsten, 2017. "An algorithmic framework for tool switching problems with multiple objectives," European Journal of Operational Research, Elsevier, vol. 259(3), pages 1003-1016.
    8. M. Selim Akturk & Jay B. Ghosh & Evrim D. Gunes, 2003. "Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(1), pages 15-30, February.
    9. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    10. Konak, Abdullah & Kulturel-Konak, Sadan & Azizoglu, Meral, 2008. "Minimizing the number of tool switching instants in Flexible Manufacturing Systems," International Journal of Production Economics, Elsevier, vol. 116(2), pages 298-307, December.
    11. Sodhi, Manbir S. & Lamond, Bernard F. & Gautier, Antoine & Noel, Martin, 2001. "Heuristics for determining economic processing rates in a flexible manufacturing system," European Journal of Operational Research, Elsevier, vol. 129(1), pages 105-115, February.
    12. Crama, Yves, 1997. "Combinatorial optimization models for production scheduling in automated manufacturing systems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 136-153, May.
    13. Yves Crama & Joris van de Klundert, 1999. "Worst‐case performance of approximation algorithms for tool management problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 445-462, August.
    14. Catanzaro, Daniele & Gouveia, Luis & Labbé, Martine, 2015. "Improved integer linear programming formulations for the job Sequencing and tool Switching Problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 766-777.
    15. Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    16. Yazdani Sabouni, M.T. & Logendran, Rasaratnam, 2013. "Carryover sequence-dependent group scheduling with the integration of internal and external setup times," European Journal of Operational Research, Elsevier, vol. 224(1), pages 8-22.
    17. Christopher S. Tang, 2017. "OM Forum—Three Simple Approaches for Young Scholars to Identify Relevant and Novel Research Topics in Operations Management," Manufacturing & Service Operations Management, INFORMS, vol. 19(3), pages 338-346, July.
    18. Nagraj Balakrishnan & Amiya K. Chakravarty, 2001. "Opportunistic retooling of a flexible machine subject to failure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(1), pages 79-97, February.
    19. Chakravarty, Amiya K. & Balakrishnan, Nagraj, 1997. "Job sequencing rules for minimizing the expected makespan in flexible machines," European Journal of Operational Research, Elsevier, vol. 96(2), pages 274-288, January.
    20. Matzliach, Barouch & Tzur, Michal, 2000. "Storage management of items in two levels of availability," European Journal of Operational Research, Elsevier, vol. 121(2), pages 363-379, March.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:38:y:2026:i:1:p:86-101. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.