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

A matheuristic for parallel machine scheduling with tool replacements

Author

Listed:
  • Dang, Quang-Vinh
  • van Diessen, Thijs
  • Martagan, Tugce
  • Adan, Ivo

Abstract

This paper addresses the problem of scheduling a set of jobs with tool requirements on identical parallel machines in a work center. This problem considers the following characteristics. First, each job may consist of an ordered set of operations due to reentrance to the work center. Moreover, operations have release times and due dates, and the processing of operations requires different tool sets of different sizes. Last, the objective is to minimize both tardiness of operations and tool setup times. Decisions concern the assignment of operations to machines, sequencing of operations, and replacement of tool sets on machines. We propose a mathematical model for the problem and a new matheuristic that combines a genetic algorithm and an integer linear programming formulation to solve industry-size instances. In the matheuristic, we propose two crossover operators which exploit the structure of the problem. We illustrate this approach through real-world case studies. Computational experiments show that our matheuristic outperforms the mathematical model and a practitioner heuristic. We also generate managerial insights by quantifying the potential room for improvement in current practice.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:291:y:2021:i:2:p:640-660
    DOI: 10.1016/j.ejor.2020.09.050
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720308547
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.09.050?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. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2013. "Pricing, relaxing and fixing under lot sizing and scheduling," European Journal of Operational Research, Elsevier, vol. 230(2), pages 399-411.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Quang-Vinh Dang & Cong Thanh Nguyen & Hana Rudová, 2019. "Scheduling of mobile robots for transportation and manufacturing tasks," Journal of Heuristics, Springer, vol. 25(2), pages 175-213, April.
    10. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    11. 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).
    12. 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.
    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. Djellab, Housni & Djellab, Khaled & Gourgand, Michel, 2000. "A new heuristic based on a hypergraph representation for the tool switching problem," International Journal of Production Economics, Elsevier, vol. 64(1-3), pages 165-176, March.
    15. 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.
    16. 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.
    17. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    18. 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.
    19. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2022. "Model-dependent task assignment in multi-manned mixed-model assembly lines with walking workers," Omega, Elsevier, vol. 113(C).
    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.

    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. 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.
    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. 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. 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. 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.
    9. 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.
    10. 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.
    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. 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.
    13. 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.
    14. 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.
    15. Moshe Dror & Mohamed Haouari, 2000. "Generalized Steiner Problems and Other Variants," Journal of Combinatorial Optimization, Springer, vol. 4(4), pages 415-436, December.
    16. 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.
    17. van der Gaast, J.P. & Rietveld, C.A. & Gabor, A.F. & Zhang, Y., 2011. "A Local Search Algorithm for Clustering in Software as a Service Networks," ERIM Report Series Research in Management ERS-2011-004-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    18. Atan, Tankut S. & Pandit, Ram, 1996. "Auxiliary tool allocation in flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 89(3), pages 642-659, March.
    19. 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.
    20. 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.

    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:291:y:2021:i:2:p:640-660. 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.