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

A two-stage stochastic programming approach for multi-activity tour scheduling

Author

Listed:
  • Restrepo, María I.
  • Gendron, Bernard
  • Rousseau, Louis-Martin

Abstract

This paper addresses a discontinuous multi-activity tour scheduling problem under demand uncertainty and when employees have identical skills. The problem is formulated as a two-stage stochastic programming model, where first-stage decisions correspond to the assignment of employees to weekly tours, while second-stage decisions are related to the allocation of work activities and breaks to daily shifts. A multi-cut L-shaped method is presented as a solution approach. Computational results on real-based and randomly generated instances show that the use of the stochastic model helps to reduce understaffing and overstaffing costs, when compared with the expected-value problem solutions.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:262:y:2017:i:2:p:620-635
    DOI: 10.1016/j.ejor.2017.04.055
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717304022
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.04.055?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. Hesham Alfares, 2004. "Survey, Categorization, and Comparison of Recent Tour Scheduling Literature," Annals of Operations Research, Springer, vol. 127(1), pages 145-175, March.
    2. Turgut Aykin, 1996. "Optimal Shift Scheduling with Multiple Break Windows," Management Science, INFORMS, vol. 42(4), pages 591-602, April.
    3. Jonathan Bard & David Morton & Yong Wang, 2007. "Workforce planning at USPS mail processing and distribution centers using stochastic optimization," Annals of Operations Research, Springer, vol. 155(1), pages 51-78, November.
    4. Parisio, Alessandra & Neil Jones, Colin, 2015. "A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand," Omega, Elsevier, vol. 53(C), pages 97-103.
    5. 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.
    6. 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.
    7. 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.
    8. Detienne, Boris & Pridy, Laurent & Pinson, ric & Rivreau, David, 2009. "Cut generation for an employee timetabling problem," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1178-1184, September.
    9. Larry P. Ritzman & LeRoy J. Krajewski & Michael J. Showalter, 1976. "The Disaggregation of Aggregate Manpower Plans," Management Science, INFORMS, vol. 22(11), pages 1204-1214, July.
    10. Prattana Punnakitikashem & Jay Rosenberber & Deborah Buckley-Behan, 2013. "A stochastic programming approach for integrated nurse staffing and assignment," IISE Transactions, Taylor & Francis Journals, vol. 45(10), pages 1059-1076.
    11. 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.
    12. Easton, Fred F. & Mansour, Nashat, 1999. "A distributed genetic algorithm for deterministic and stochastic labor scheduling problems," European Journal of Operational Research, Elsevier, vol. 118(3), pages 505-523, November.
    13. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    14. Marie-Claude Côté & Bernard Gendron & Louis-Martin Rousseau, 2011. "Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling," Management Science, INFORMS, vol. 57(1), pages 151-163, January.
    15. Song, Haiqing & Huang, Huei-Chuen, 2008. "A successive convex approximation method for multistage workforce capacity planning problem with turnover," European Journal of Operational Research, Elsevier, vol. 188(1), pages 29-48, July.
    16. 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.
    17. Robbins, Thomas R. & Harrison, Terry P., 2010. "A stochastic programming model for scheduling call centers with global Service Level Agreements," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1608-1619, December.
    18. G M Campbell, 2011. "A two-stage stochastic program for scheduling and allocating cross-trained workers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 1038-1047, June.
    19. Kibaek Kim & Sanjay Mehrotra, 2015. "A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management," Operations Research, INFORMS, vol. 63(6), pages 1431-1451, December.
    20. Dale McDaniel & Mike Devine, 1977. "A Modified Benders' Partitioning Algorithm for Mixed Integer Programming," Management Science, INFORMS, vol. 24(3), pages 312-319, November.
    21. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    22. X Zhu & H D Sherali, 2009. "Two-stage workforce planning under demand fluctuations and uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 94-103, January.
    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. Shoufeng Ma & Hongming Li & Ning Zhu & Chenyi Fu, 2021. "Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty," Journal of Scheduling, Springer, vol. 24(2), pages 137-174, April.
    2. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2021. "Crowdsourced delivery: A review of platforms and academic literature," Omega, Elsevier, vol. 98(C).
    3. Mitra, Sovan & Lim, Sungmook & Karathanasopoulos, Andreas, 2019. "Regression based scenario generation: Applications for performance management," Operations Research Perspectives, Elsevier, vol. 6(C).
    4. Bürgy, Reinhard & Michon-Lacaze, Hélène & Desaulniers, Guy, 2019. "Employee scheduling with short demand perturbations and extensible shifts," Omega, Elsevier, vol. 89(C), pages 177-192.
    5. Douglas S. Altner & Erica K. Mason & Les D. Servi, 2019. "Two-stage stochastic days-off scheduling of multi-skilled analysts with training options," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 111-129, July.
    6. Restrepo, María I. & Rousseau, Louis-Martin & Vallée, Jonathan, 2020. "Home healthcare integrated staffing and scheduling," Omega, Elsevier, vol. 95(C).
    7. Zhou, Shaorui & Zhang, Hui & Shi, Ning & Xu, Zhou & Wang, Fan, 2020. "A new convergent hybrid learning algorithm for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 283(1), pages 33-46.

    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. Douglas S. Altner & Anthony C. Rojas & Leslie D. Servi, 2018. "A two-stage stochastic program for multi-shift, multi-analyst, workforce optimization with multiple on-call options," Journal of Scheduling, Springer, vol. 21(5), pages 517-531, October.
    3. Tohidi, Mohammad & Kazemi Zanjani, Masoumeh & Contreras, Ivan, 2021. "A physician planning framework for polyclinics under uncertainty," Omega, Elsevier, vol. 101(C).
    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. 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.
    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. Bürgy, Reinhard & Michon-Lacaze, Hélène & Desaulniers, Guy, 2019. "Employee scheduling with short demand perturbations and extensible shifts," Omega, Elsevier, vol. 89(C), pages 177-192.
    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. Douglas S. Altner & Erica K. Mason & Les D. Servi, 2019. "Two-stage stochastic days-off scheduling of multi-skilled analysts with training options," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 111-129, July.
    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. 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.
    13. Restrepo, María I. & Rousseau, Louis-Martin & Vallée, Jonathan, 2020. "Home healthcare integrated staffing and scheduling," Omega, Elsevier, vol. 95(C).
    14. Ağralı, Semra & Taşkın, Z. Caner & Ünal, A. Tamer, 2017. "Employee scheduling in service industries with flexible employee availability and demand," Omega, Elsevier, vol. 66(PA), pages 159-169.
    15. Kibaek Kim & Sanjay Mehrotra, 2015. "A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management," Operations Research, INFORMS, vol. 63(6), pages 1431-1451, December.
    16. Vlado Popović & Milorad Kilibarda & Milan Andrejić & Borut Jereb & Dejan Dragan, 2021. "A New Sustainable Warehouse Management Approach for Workforce and Activities Scheduling," Sustainability, MDPI, vol. 13(4), pages 1-19, February.
    17. Lusby, Richard Martin & Range, Troels Martin & Larsen, Jesper, 2015. "A Benders decomposition-based Matheuristic for the Cardinality Constrained Shift Design Problem," Discussion Papers on Economics 9/2015, University of Southern Denmark, Department of Economics.
    18. 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.
    19. 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.
    20. 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.

    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:262:y:2017:i:2:p:620-635. 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.