IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v27y2021i1d10.1007_s10732-020-09439-9.html
   My bibliography  Save this article

An automatic constructive matheuristic for the shift minimization personnel task scheduling problem

Author

Listed:
  • Reshma Chirayil Chandrasekharan

    (KU Leuven)

  • Pieter Smet

    (KU Leuven)

  • Tony Wauters

    (KU Leuven)

Abstract

The shift minimization personnel task scheduling problem is an NP-complete optimization problem that concerns the assignment of tasks to multi-skilled employees with a view to minimize the total number of assigned employees. Recent literature indicates that hybrid methods which combine exact and heuristic techniques such as matheuristics are efficient as regards to generating high quality solutions. The present work employs a constructive matheuristic (CMH): a decomposition-based method where sub-problems are solved to optimality using exact techniques. The optimal solutions of sub-problems are subsequently utilized to construct a feasible solution for the entire problem. Based on the study, a time-based CMH has been developed which, for the first time, solves all the difficult instances introduced by Smet et al. (Omega 46:64–73, 2014) to optimality. In addition, an automated CMH algorithm that utilizes instance-specific problem features has also been developed that produces high quality solutions over all current benchmark instances.

Suggested Citation

  • Reshma Chirayil Chandrasekharan & Pieter Smet & Tony Wauters, 2021. "An automatic constructive matheuristic for the shift minimization personnel task scheduling problem," Journal of Heuristics, Springer, vol. 27(1), pages 205-227, April.
    • Handle: RePEc:spr:joheur:v:27:y:2021:i:1:d:10.1007_s10732-020-09439-9
    DOI: 10.1007/s10732-020-09439-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-020-09439-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-020-09439-9?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. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    2. Haroldo G. Santos & Túlio A. M. Toffolo & Rafael A. M. Gomes & Sabir Ribas, 2016. "Integer programming techniques for the nurse rostering problem," Annals of Operations Research, Springer, vol. 239(1), pages 225-251, April.
    3. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    4. Krishnamoorthy, M. & Ernst, A.T. & Baatar, D., 2012. "Algorithms for large scale Shift Minimisation Personnel Task Scheduling Problems," European Journal of Operational Research, Elsevier, vol. 219(1), pages 34-48.
    5. D. Dowling & M. Krishnamoorthy & H. Mackenzie & D. Sier, 1997. "Staff rostering at a large international airport," Annals of Operations Research, Springer, vol. 72(0), pages 125-147, January.
    6. Federico Della Croce & Andrea Grosso & Fabio Salassa, 2014. "A matheuristic approach for the two-machine total completion time flow shop problem," Annals of Operations Research, Springer, vol. 213(1), pages 67-78, February.
    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. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    2. Wang, Wenshu & Xie, Kexin & Guo, Siqi & Li, Weixing & Xiao, Fan & Liang, Zhe, 2023. "A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements," European Journal of Operational Research, Elsevier, vol. 310(1), pages 360-378.
    3. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    4. Ferdinand Kiermaier & Markus Frey & Jonathan F. Bard, 2020. "The flexible break assignment problem for large tour scheduling problems with an application to airport ground handlers," Journal of Scheduling, Springer, vol. 23(2), pages 177-209, April.
    5. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.
    6. Sara Ceschia & Rosita Guido & Andrea Schaerf, 2020. "Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods," Annals of Operations Research, Springer, vol. 288(1), pages 95-113, May.
    7. Suk Ho Jin & Ho Yeong Yun & Suk Jae Jeong & Kyung Sup Kim, 2017. "Hybrid and Cooperative Strategies Using Harmony Search and Artificial Immune Systems for Solving the Nurse Rostering Problem," Sustainability, MDPI, vol. 9(7), pages 1-19, June.
    8. Di Martinelly, Christine & Meskens, Nadine, 2017. "A bi-objective integrated approach to building surgical teams and nurse schedule rosters to maximise surgical team affinities and minimise nurses' idle time," International Journal of Production Economics, Elsevier, vol. 191(C), pages 323-334.
    9. Juan P. Cavada & Cristián E. Cortés & Gustavo Henríquez & Pablo A. Rey, 2023. "A ground crew shift rostering model for Santiago International Airport," Operational Research, Springer, vol. 23(1), pages 1-26, March.
    10. Florian Mischek & Nysret Musliu, 2019. "Integer programming model extensions for a multi-stage nurse rostering problem," Annals of Operations Research, Springer, vol. 275(1), pages 123-143, April.
    11. Marco Schulze & Jürgen Zimmermann, 2017. "Staff and machine shift scheduling in a German potash mine," Journal of Scheduling, Springer, vol. 20(6), pages 635-656, December.
    12. Lishun Zeng & Mingyu Zhao & Yangfan Liu, 2019. "Airport ground workforce planning with hierarchical skills: a new formulation and branch-and-price approach," Annals of Operations Research, Springer, vol. 275(1), pages 245-258, April.
    13. De Bruecker, Philippe & Van den Bergh, Jorne & Beliën, Jeroen & Demeulemeester, Erik, 2015. "Workforce planning incorporating skills: State of the art," European Journal of Operational Research, Elsevier, vol. 243(1), pages 1-16.
    14. Lai, David S.W. & Leung, Janny M.Y. & Dullaert, Wout & Marques, Inês, 2020. "A graph-based formulation for the shift rostering problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 285-300.
    15. Elín Björk Böðvarsdóttir & Niels-Christian Fink Bagger & Laura Elise Høffner & Thomas J. R. Stidsen, 2022. "A flexible mixed integer programming-based system for real-world nurse rostering," Journal of Scheduling, Springer, vol. 25(1), pages 59-88, February.
    16. Caballini, Claudia & Paolucci, Massimo, 2020. "A rostering approach to minimize health risks for workers: An application to a container terminal in the Italian port of Genoa," Omega, Elsevier, vol. 95(C).
    17. Mohammad Reza Hassani & J. Behnamian, 2021. "A scenario-based robust optimization with a pessimistic approach for nurse rostering problem," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 143-169, January.
    18. Julie Poullet & Axel Parmentier, 2020. "Shift Planning Under Delay Uncertainty at Air France: A Vehicle-Scheduling Problem with Outsourcing," Transportation Science, INFORMS, vol. 54(4), pages 956-972, July.
    19. Mansini, Renata & Zanella, Marina & Zanotti, Roberto, 2023. "Optimizing a complex multi-objective personnel scheduling problem jointly complying with requests from customers and staff," Omega, Elsevier, vol. 114(C).
    20. David Rea & Craig Froehle & Suzanne Masterson & Brian Stettler & Gregory Fermann & Arthur Pancioli, 2021. "Unequal but Fair: Incorporating Distributive Justice in Operational Allocation Models," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2304-2320, July.

    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:spr:joheur:v:27:y:2021:i:1:d:10.1007_s10732-020-09439-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.