IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v316y2024i3p976-987.html
   My bibliography  Save this article

Exploiting symmetry for the job sequencing and tool switching problem

Author

Listed:
  • Akhundov, Najmaddin
  • Ostrowski, James

Abstract

The Job Sequencing and Tool Switching Problem (SSP), a well-known combinatorial optimization problem in the domain of Flexible Manufacturing Systems (FMS), is studied in this article. The aim of this research is to improve the currently known exact solution methodology for this NP-hard problem. We propose a new integer linear programming approach with symmetry-breaking and tightening cuts that provably outperformed the existing methodology described in the literature. The computational study conducted on a data set with 1,050 instances showed that the developed method can solve hard instances that were not solvable with the state-of-the-art methods presented in the literature.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:3:p:976-987
    DOI: 10.1016/j.ejor.2024.02.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724001632
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.02.030?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    3. Schwerdfeger, Stefan & Boysen, Nils, 2017. "Order picking along a crane-supplied pick face: The SKU switching problem," European Journal of Operational Research, Elsevier, vol. 260(2), pages 534-545.
    4. Kusiak, Andrew, 1986. "Application of operational research models and techniques in flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 24(3), pages 336-345, March.
    5. Hirvikorpi, Mika & Salonen, Kari & Knuutila, Timo & Nevalainen, Olli S., 2006. "The general two-level storage management problem: A reconsideration of the KTNS-rule," European Journal of Operational Research, Elsevier, vol. 171(1), pages 189-207, May.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    11. 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.
    12. 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.
    13. 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.
    14. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    15. 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.
    16. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    17. 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).
    18. Maghsud Solimanpur & Reza Rastgordani, 2012. "Minimising tool switching and indexing times by ant colony optimisation in automatic machining centres," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 13(4), pages 465-479.
    19. 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.
    20. Ahmed Ghoniem & Farbod Farhadi, 2015. "A column generation approach for aircraft sequencing problems: a computational study," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(10), pages 1717-1729, October.
    21. 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.
    22. Samuel Eilon & Nicos Christofides, 1971. "The Loading Problem," Management Science, INFORMS, vol. 17(5), pages 259-268, January.
    23. Adil Baykasoğlu & Fehmi Burcin Ozsoydan, 2018. "Minimisation of non-machining times in operating automatic tool changers of machine tools under dynamic operating conditions," International Journal of Production Research, Taylor & Francis Journals, vol. 56(4), pages 1548-1564, February.
    24. Burak Gökgür & Brahim Hnich & Selin Özpeynirci, 2018. "Parallel machine scheduling with tool loading: a constraint programming approach," International Journal of Production Research, Taylor & Francis Journals, vol. 56(16), pages 5541-5557, August.
    25. 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.
    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. 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.
    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. 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.
    4. 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.
    5. 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.
    6. Raduly-Baka, Csaba & Nevalainen, Olli S., 2015. "The modular tool switching problem," European Journal of Operational Research, Elsevier, vol. 242(1), pages 100-106.
    7. 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.
    8. Guopeng Song & Roel Leus, 2022. "Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3059-3079, November.
    9. 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.
    10. Schwerdfeger, Stefan & Boysen, Nils, 2017. "Order picking along a crane-supplied pick face: The SKU switching problem," European Journal of Operational Research, Elsevier, vol. 260(2), pages 534-545.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Weckenborg, Christian & Schumacher, Patrick & Thies, Christian & Spengler, Thomas S., 2024. "Flexibility in manufacturing system design: A review of recent approaches from Operations Research," European Journal of Operational Research, Elsevier, vol. 315(2), pages 413-441.
    18. Claudia Archetti & Natashia Boland & Grazia Speranza, 2017. "A Matheuristic for the Multivehicle Inventory Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 377-387, August.
    19. Sakine Batun & Brian T. Denton & Todd R. Huschka & Andrew J. Schaefer, 2011. "Operating Room Pooling and Parallel Surgery Processing Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 220-237, May.
    20. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 103-120, February.

    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:eee:ejores:v:316:y:2024:i:3:p:976-987. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.