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

Algorithms for large scale Shift Minimisation Personnel Task Scheduling Problems

Author

Listed:
  • Krishnamoorthy, M.
  • Ernst, A.T.
  • Baatar, D.

Abstract

In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:219:y:2012:i:1:p:34-48
    DOI: 10.1016/j.ejor.2011.11.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711010435
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.11.034?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. Matteo Fischetti & Silvano Martello & Paolo Toth, 1989. "The Fixed Job Schedule Problem with Working-Time Constraints," Operations Research, INFORMS, vol. 37(3), pages 395-403, June.
    2. Ilya Gertsbakh & Helman I. Stern, 1978. "Minimal Resources for Fixed and Variable Job Schedules," Operations Research, INFORMS, vol. 26(1), pages 68-85, February.
    3. Leo G. Kroon & Marc Salomon & Luk N. Van Wassenhove, 1997. "Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem," Operations Research, INFORMS, vol. 45(4), pages 624-638, August.
    4. A.T. Ernst & H. Jiang & M. Krishnamoorthy & B. Owens & D. Sier, 2004. "An Annotated Bibliography of Personnel Scheduling and Rostering," Annals of Operations Research, Springer, vol. 127(1), pages 21-144, March.
    5. Matteo Fischetti & Silvano Martello & Paolo Toth, 1987. "The Fixed Job Schedule Problem with Spread-Time Constraints," Operations Research, INFORMS, vol. 35(6), pages 849-858, December.
    6. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    7. 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.
    8. Oliver Bastert & Benjamin Hummel & Sven de Vries, 2010. "A Generalized Wedelin Heuristic for Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 93-107, February.
    9. Matteo Fischetti & Silvano Martello & Paolo Toth, 1992. "Approximation Algorithms for Fixed Job Schedule Problems," Operations Research, INFORMS, vol. 40(1-supplem), pages 96-108, February.
    10. Valls, Vicente & Perez, Angeles & Quintanilla, Sacramento, 1996. "A graph colouring model for assigning a heterogeneous workforce to a given schedule," European Journal of Operational Research, Elsevier, vol. 90(2), pages 285-302, April.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Emilio Zamorano & Annika Becker & Raik Stolletz, 2018. "Task assignment with start time-dependent processing times for personnel at check-in counters," Journal of Scheduling, Springer, vol. 21(1), pages 93-109, February.
    6. Wim Vancroonenburg & Patrick Causmaecker & Greet Vanden Berghe, 2016. "A study of decision support models for online patient-to-room assignment planning," Annals of Operations Research, Springer, vol. 239(1), pages 253-271, April.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.

    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. Antoon W.J. Kolen & Jan Karel Lenstra & Christos H. Papadimitriou & Frits C.R. Spieksma, 2007. "Interval scheduling: A survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 530-543, August.
    2. Bekki, Özgün BarIs & Azizoglu, Meral, 2008. "Operational fixed interval scheduling problem on uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 112(2), pages 756-768, April.
    3. Kroon, Leo G. & Salomon, Marc & Van Wassenhove, Luk N., 1995. "Exact and approximation algorithms for the operational fixed interval scheduling problem," European Journal of Operational Research, Elsevier, vol. 82(1), pages 190-205, April.
    4. 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.
    5. Kroon, Leo G. & Edwin Romeijn, H. & Zwaneveld, Peter J., 1997. "Routing trains through railway stations: complexity issues," European Journal of Operational Research, Elsevier, vol. 98(3), pages 485-498, May.
    6. 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.
    7. Türsel Eliiyi, Deniz & Azizoglu, Meral, 2011. "Heuristics for operational fixed job scheduling problems with working and spread time constraints," International Journal of Production Economics, Elsevier, vol. 132(1), pages 107-121, July.
    8. Yim, Seho & Hong, Sung-Pil & Park, Myoung-Ju & Chung, Yerim, 2022. "Inverse interval scheduling via reduction on a single machine," European Journal of Operational Research, Elsevier, vol. 303(2), pages 541-549.
    9. Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
    10. Brucker, Peter & Qu, Rong & Burke, Edmund, 2011. "Personnel scheduling: Models and complexity," European Journal of Operational Research, Elsevier, vol. 210(3), pages 467-473, May.
    11. Ivan Kovynyov & Ralf Mikut, 2019. "Digital technologies in airport ground operations," Netnomics, Springer, vol. 20(1), pages 1-30, April.
    12. A. Mingozzi & M. A. Boschetti & S. Ricciardelli & L. Bianco, 1999. "A Set Partitioning Approach to the Crew Scheduling Problem," Operations Research, INFORMS, vol. 47(6), pages 873-888, December.
    13. 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.
    14. Elina Rönnberg & Torbjörn Larsson, 2010. "Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study," Health Care Management Science, Springer, vol. 13(1), pages 35-53, March.
    15. 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.
    16. Lee, Soonhui & Turner, Jonathan & Daskin, Mark S. & Homem-de-Mello, Tito & Smilowitz, Karen, 2012. "Improving fleet utilization for carriers by interval scheduling," European Journal of Operational Research, Elsevier, vol. 218(1), pages 261-269.
    17. Young-Chae Hong & Amy Cohn & Stephen Gorga & Edmond O’Brien & William Pozehl & Jennifer Zank, 2019. "Using Optimization Techniques and Multidisciplinary Collaboration to Solve a Challenging Real-World Residency Scheduling Problem," Interfaces, INFORMS, vol. 49(3), pages 201-212, May.
    18. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    19. Lotfi Hidri & Achraf Gazdar & Mohammed M. Mabkhot, 2020. "Optimized Procedure to Schedule Physicians in an Intensive Care Unit: A Case Study," Mathematics, MDPI, vol. 8(11), pages 1-24, November.
    20. Broos Maenhout & Mario Vanhoucke, 2008. "Comparison and hybridization of crossover operators for the nurse scheduling problem," Annals of Operations Research, Springer, vol. 159(1), pages 333-353, March.

    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:219:y:2012:i:1:p:34-48. 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.