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

Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce

Author

Listed:
  • Gérard, Matthieu
  • Clautiaux, François
  • Sadykov, Ruslan

Abstract

In this paper, we address a multi-activity tour scheduling problem with time varying demand. The objective is to compute a team schedule for a fixed roster of employees in order to minimize the over-coverage and the under-coverage of different parallel activity demands along a planning horizon of one week. Numerous complicating constraints are present in our problem: all employees are different and can perform several different activities during the same day-shift, lunch breaks and pauses are flexible, demand is given for 15 minutes periods. Employees have feasibility and legality rules to be satisfied, but the objective function does not account for any quality measure associated with each individual’s schedule. More precisely, the problem mixes simultaneously days-off scheduling, shift scheduling, shift assignment, activity assignment, pause and lunch break assignment.

Suggested Citation

  • Gérard, Matthieu & Clautiaux, François & Sadykov, Ruslan, 2016. "Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce," European Journal of Operational Research, Elsevier, vol. 252(3), pages 1019-1030.
    • Handle: RePEc:eee:ejores:v:252:y:2016:i:3:p:1019-1030
    DOI: 10.1016/j.ejor.2016.01.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716000813
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.01.036?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. Thompson, Gary M. & Pullman, Madeleine E., 2007. "Scheduling workforce relief breaks in advance versus in real-time," European Journal of Operational Research, Elsevier, vol. 181(1), pages 139-155, August.
    2. 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.
    3. 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.
    4. Kabak, Ozgur & Ulengin, Fusun & Aktas, Emel & Onsel, Sule & Topcu, Y. Ilker, 2008. "Efficient shift scheduling in the retail sector through two-stage optimization," European Journal of Operational Research, Elsevier, vol. 184(1), pages 76-90, January.
    5. 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.
    6. Guy Eitzen & David Panton & Graham Mills, 2004. "Multi-Skilled Workforce Optimisation," Annals of Operations Research, Springer, vol. 127(1), pages 359-372, March.
    7. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    8. Marie-Claude Côté & Bernard Gendron & Louis-Martin Rousseau, 2013. "Grammar-Based Column Generation for Personalized Multi-Activity Shift Scheduling," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 461-474, August.
    9. Stolletz, Raik, 2010. "Operational workforce planning for check-in counters at airports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(3), pages 414-425, May.
    10. 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.
    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. 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.
    2. Rana Shariat & Kai Huang, 2024. "A large-scale neighborhood search algorithm for multi-activity tour scheduling problems," Journal of Heuristics, Springer, vol. 30(5), pages 225-267, December.
    3. 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.
    4. 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.
    5. 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.

    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. 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. 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. 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. 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.
    6. 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.
    7. 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.
    8. Rana Shariat & Kai Huang, 2024. "A large-scale neighborhood search algorithm for multi-activity tour scheduling problems," Journal of Heuristics, Springer, vol. 30(5), pages 225-267, December.
    9. Restrepo, María I. & Gendron, Bernard & Rousseau, Louis-Martin, 2017. "A two-stage stochastic programming approach for multi-activity tour scheduling," European Journal of Operational Research, Elsevier, vol. 262(2), pages 620-635.
    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. Sana Dahmen & Monia Rekik & François Soumis, 2018. "An implicit model for multi-activity shift scheduling problems," Journal of Scheduling, Springer, vol. 21(3), pages 285-304, June.
    12. Dalia Attia & Reinhard Bürgy & Guy Desaulniers & François Soumis, 2019. "A decomposition-based heuristic for large employee scheduling problems with inter-department transfers," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 325-357, December.
    13. Hernández-Leandro, Noberto A. & Boyer, Vincent & Salazar-Aguilar, M. Angélica & Rousseau, Louis-Martin, 2019. "A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 272(3), pages 859-867.
    14. 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.
    15. María I. Restrepo & Bernard Gendron & Louis-Martin Rousseau, 2016. "Branch-and-Price for Personalized Multiactivity Tour Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 334-350, May.
    16. 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.
    17. Kraul, Sebastian & Fügener, Andreas & Brunner, Jens O. & Blobner, Manfred, 2019. "A robust framework for task-related resident scheduling," European Journal of Operational Research, Elsevier, vol. 276(2), pages 656-675.
    18. Stolletz, Raik & Brunner, Jens O., 2012. "Fair optimization of fortnightly physician schedules with flexible shifts," European Journal of Operational Research, Elsevier, vol. 219(3), pages 622-629.
    19. Oyku Ahipasaoglu & Nesim Erkip & Oya Ekin Karasan, 2019. "The venue management problem: setting staffing levels, shifts and shift schedules at concession stands," Journal of Scheduling, Springer, vol. 22(1), pages 69-83, February.
    20. Emir Hüseyin Özder & Evrencan Özcan & Tamer Eren, 2019. "Staff Task-Based Shift Scheduling Solution with an ANP and Goal Programming Method in a Natural Gas Combined Cycle Power Plant," Mathematics, MDPI, vol. 7(2), pages 1-26, 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:252:y:2016:i:3:p:1019-1030. 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.