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

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

Author

Listed:
  • Lin, Shih-Wei
  • Ying, Kuo-Ching

Abstract

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:237:y:2014:i:1:p:323-334
    DOI: 10.1016/j.ejor.2014.01.035
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714000563
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.01.035?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. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    2. Hesham Alfares, 2004. "Survey, Categorization, and Comparison of Recent Tour Scheduling Literature," Annals of Operations Research, Springer, vol. 127(1), pages 145-175, March.
    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. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    5. 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.
    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. Panta Lučić & Dušan Teodorović, 2007. "Metaheuristics approach to the aircrew rostering problem," Annals of Operations Research, Springer, vol. 155(1), pages 311-338, November.
    8. 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.
    9. Luca Di Gaspero & Johannes Gärtner & Guy Kortsarz & Nysret Musliu & Andrea Schaerf & Wolfgang Slany, 2007. "The minimum shift design problem," Annals of Operations Research, Springer, vol. 155(1), pages 79-105, November.
    10. 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.
    11. Jeroen Beliën & Erik Demeulemeester, 2007. "On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem," Annals of Operations Research, Springer, vol. 155(1), pages 143-166, November.
    12. Hertz, Alain & Lahrichi, Nadia & Widmer, Marino, 2010. "A flexible MILP model for multiple-shift workforce planning under annualized hours," European Journal of Operational Research, Elsevier, vol. 200(3), pages 860-873, February.
    13. Ruiz, Ruben & Stutzle, Thomas, 2008. "An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1143-1159, June.
    14. Ulusam Seckiner, Serap & Gokcen, Hadi & Kurt, Mustafa, 2007. "An integer programming model for hierarchical workforce scheduling problem," European Journal of Operational Research, Elsevier, vol. 183(2), pages 694-699, December.
    15. G. Hao & K.K. Lai & M. Tan, 2004. "A Neural Network Application in Personnel Scheduling," Annals of Operations Research, Springer, vol. 128(1), pages 65-90, April.
    16. Hojati, Mehran & Patil, Ashok S., 2011. "An integer linear programming-based heuristic for scheduling heterogeneous, part-time service employees," European Journal of Operational Research, Elsevier, vol. 209(1), pages 37-50, February.
    17. Leslie C. Edie, 1954. "Traffic Delays at Toll Booths," Operations Research, INFORMS, vol. 2(2), pages 107-138, May.
    18. S M Al-Yakoob & H D Sherali, 2008. "A column generation approach for an employee scheduling problem with multiple shifts and work locations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 34-43, January.
    19. G Laporte & G Pesant, 2004. "A general multi-shift scheduling system," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(11), pages 1208-1217, November.
    20. Thompson, Gary M. & Goodale, John C., 2006. "Variable employee productivity in workforce scheduling," European Journal of Operational Research, Elsevier, vol. 170(2), pages 376-390, April.
    21. Auke Pot & Sandjai Bhulai & Ger Koole, 2008. "A Simple Staffing Method for Multiskill Call Centers," Manufacturing & Service Operations Management, INFORMS, vol. 10(3), pages 421-428, December.
    22. Restrepo, María I. & Lozano, Leonardo & Medaglia, Andrés L., 2012. "Constrained network-based column generation for the multi-activity shift scheduling problem," International Journal of Production Economics, Elsevier, vol. 140(1), pages 466-472.
    23. Guy Eitzen & David Panton & Graham Mills, 2004. "Multi-Skilled Workforce Optimisation," Annals of Operations Research, Springer, vol. 127(1), pages 359-372, March.
    24. Beddoe, Gareth R. & Petrovic, Sanja, 2006. "Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering," European Journal of Operational Research, Elsevier, vol. 175(2), pages 649-671, December.
    25. Burke, Edmund K. & Li, Jingpeng & Qu, Rong, 2010. "A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 484-493, June.
    26. 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.
    27. K-C Ying, 2009. "An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(6), pages 810-817, June.
    28. Seyda Topaloglu & Irem Ozkarahan, 2004. "An Implicit Goal Programming Model for the Tour Scheduling Problem Considering the Employee Work Preferences," Annals of Operations Research, Springer, vol. 128(1), pages 135-158, April.
    29. E K Burke & T Curtois & R Qu & G Vanden Berghe, 2010. "A scatter search methodology for the nurse rostering problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1667-1679, November.
    30. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    31. S Casado & M Laguna & J Pacheco, 2005. "Heuristical labour scheduling to optimize airport passenger flows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 649-658, June.
    32. Burke, Edmund K. & Curtois, Timothy & Post, Gerhard & Qu, Rong & Veltman, Bart, 2008. "A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 188(2), pages 330-341, July.
    33. E K Burke & T Curtois & L F van Draat & J-K van Ommeren & G Post, 2011. "Progress control in iterated local search for nurse rostering," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 360-367, February.
    34. Bellanti, F. & Carello, G. & Della Croce, F. & Tadei, R., 2004. "A greedy-based neighborhood search approach to a nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 28-40, February.
    35. Fowler, John W. & Wirojanagud, Pornsarun & Gel, Esma S., 2008. "Heuristics for workforce planning with worker differences," European Journal of Operational Research, Elsevier, vol. 190(3), pages 724-740, November.
    36. Niklas Kohl & Stefan Karisch, 2004. "Airline Crew Rostering: Problem Types, Modeling, and Optimization," Annals of Operations Research, Springer, vol. 127(1), pages 223-257, March.
    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. 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).
    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. 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. 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. 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.
    3. Marta Rocha & José Oliveira & Maria Carravilla, 2014. "A constructive heuristic for staff scheduling in the glass industry," Annals of Operations Research, Springer, vol. 217(1), pages 463-478, June.
    4. Banu Sungur & Cemal Özgüven & Yasemin Kariper, 2017. "Shift scheduling with break windows, ideal break periods, and ideal waiting times," Flexible Services and Manufacturing Journal, Springer, vol. 29(2), pages 203-222, June.
    5. Burke, Edmund K. & Curtois, Tim, 2014. "New approaches to nurse rostering benchmark instances," European Journal of Operational Research, Elsevier, vol. 237(1), pages 71-81.
    6. Sanja Petrovic, 2019. "“You have to get wet to learn how to swim” applied to bridging the gap between research into personnel scheduling and its implementation in practice," Annals of Operations Research, Springer, vol. 275(1), pages 161-179, April.
    7. 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.
    8. 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.
    9. De Bruecker, Philippe & Beliën, Jeroen & Van den Bergh, Jorne & Demeulemeester, Erik, 2018. "A three-stage mixed integer programming approach for optimizing the skill mix and training schedules for aircraft maintenance," European Journal of Operational Research, Elsevier, vol. 267(2), pages 439-452.
    10. Mark W. Isken & Osman T. Aydas, 2022. "A tactical multi-week implicit tour scheduling model with applications in healthcare," Health Care Management Science, Springer, vol. 25(4), pages 551-573, December.
    11. Dohn, Anders & Mason, Andrew, 2013. "Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation," European Journal of Operational Research, Elsevier, vol. 230(1), pages 157-169.
    12. Jaime Miranda & Pablo A. Rey & Antoine Sauré & Richard Weber, 2018. "Metro Uses a Simulation-Optimization Approach to Improve Fare-Collection Shift Scheduling," Interfaces, INFORMS, vol. 48(6), pages 529-542, November.
    13. Doi, Tsubasa & Nishi, Tatsushi & Voß, Stefan, 2018. "Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time," European Journal of Operational Research, Elsevier, vol. 267(2), pages 428-438.
    14. Federico Della Croce & Fabio Salassa, 2014. "A variable neighborhood search based matheuristic for nurse rostering problems," Annals of Operations Research, Springer, vol. 218(1), pages 185-199, July.
    15. Salem Al-Yakoob & Hanif Sherali, 2007. "Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations," Annals of Operations Research, Springer, vol. 155(1), pages 119-142, November.
    16. Valouxis, Christos & Gogos, Christos & Goulas, George & Alefragis, Panayiotis & Housos, Efthymios, 2012. "A systematic two phase approach for the nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 219(2), pages 425-433.
    17. 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.
    18. 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.
    19. Eyjólfur Ingi Ásgeirsson & Guðríður Lilla Sigurðardóttir, 2016. "Near-optimal MIP solutions for preference based self-scheduling," Annals of Operations Research, Springer, vol. 239(1), pages 273-293, April.
    20. Chapados, Nicolas & Joliveau, Marc & L’Ecuyer, Pierre & Rousseau, Louis-Martin, 2014. "Retail store scheduling for profit," European Journal of Operational Research, Elsevier, vol. 239(3), pages 609-624.

    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:237:y:2014:i:1:p:323-334. 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.