IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v57y2011i1p151-163.html
   My bibliography  Save this article

Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling

Author

Listed:
  • Marie-Claude Côté

    (CIRRELT and Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada)

  • Bernard Gendron

    (CIRRELT and Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada)

  • Louis-Martin Rousseau

    (CIRRELT and Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada)

Abstract

This paper presents a new implicit formulation for shift scheduling problems, using context-free grammars to model the rules for the composition of shifts. From the grammar, we generate an integer programming (IP) model having a linear programming relaxation equivalent to that of the classical set covering model. When solved by a state-of-the-art IP solver on problem instances with a small number of shifts, our model, the set covering formulation, and a typical implicit model from the literature yield comparable solution times. On instances with a large number of shifts, our formulation shows superior performance and can model a wider variety of constraints. In particular, multiactivity cases, which cannot be modeled by existing implicit formulations, can easily be handled with grammars. We present comparative experimental results on a large set of instances involving one work activity, as well as on problems dealing with up to 10 work activities. This paper was accepted by Dimitris Bertsimas, optimization.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormnsc:v:57:y:2011:i:1:p:151-163
    DOI: 10.1287/mnsc.1100.1264
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.1100.1264
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.1100.1264?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
    ---><---

    References listed on IDEAS

    as
    1. Leslie C. Edie, 1954. "Traffic Delays at Toll Booths," Operations Research, INFORMS, vol. 2(2), pages 107-138, May.
    2. Monia Rekik & Jean-François Cordeau & François Soumis, 2004. "Using Benders Decomposition to Implicitly Model Tour Scheduling," Annals of Operations Research, Springer, vol. 128(1), pages 111-133, April.
    3. Turgut Aykin, 1996. "Optimal Shift Scheduling with Multiple Break Windows," Management Science, INFORMS, vol. 42(4), pages 591-602, April.
    4. M. Segal, 1974. "The Operator-Scheduling Problem: A Network-Flow Approach," Operations Research, INFORMS, vol. 22(4), pages 808-823, August.
    5. 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.
    6. Willie B. Henderson & William L. Berry, 1976. "Heuristic Methods for Telephone Operator Shift Scheduling: An Experimental Analysis," Management Science, INFORMS, vol. 22(12), pages 1372-1380, August.
    7. Gary M. Thompson, 1995. "Improved Implicit Optimal Modeling of the Labor Shift Scheduling Problem," Management Science, INFORMS, vol. 41(4), pages 595-607, 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. 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.
    2. Volland, Jonas & Fügener, Andreas & Brunner, Jens O., 2017. "A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals," European Journal of Operational Research, Elsevier, vol. 260(1), pages 316-334.
    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. Michael Römer, 2024. "Block-based state-expanded network models for multi-activity shift scheduling," Journal of Scheduling, Springer, vol. 27(4), pages 341-361, August.
    5. 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.
    6. 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.
    7. Jens O. Brunner & Jonathan F. Bard & Jan M. Köhler, 2013. "Bounded flexibility in days‐on and days‐off scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(8), pages 678-701, December.
    8. 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.
    9. Hassani, Rachid & Desaulniers, Guy & Elhallaoui, Issmail, 2021. "Real-time bi-objective personnel re-scheduling in the retail industry," European Journal of Operational Research, Elsevier, vol. 293(1), pages 93-108.
    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. 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.
    12. 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.
    13. Restrepo, María I. & Rousseau, Louis-Martin & Vallée, Jonathan, 2020. "Home healthcare integrated staffing and scheduling," Omega, Elsevier, vol. 95(C).
    14. Alex Bonutti & Sara Ceschia & Fabio De Cesco & Nysret Musliu & Andrea Schaerf, 2017. "Modeling and solving a real-life multi-skill shift design problem," Annals of Operations Research, Springer, vol. 252(2), pages 365-382, May.
    15. 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.
    16. 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.
    17. 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.

    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. Aykin, Turgut, 2000. "A comparative evaluation of modeling approaches to the labor shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 125(2), pages 381-397, September.
    2. 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.
    3. Anuj Mehrotra & Kenneth E. Murphy & Michael A. Trick, 2000. "Optimal shift scheduling: A branch‐and‐price approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 185-200, April.
    4. 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.
    5. Noah Gans & Ger Koole & Avishai Mandelbaum, 2003. "Telephone Call Centers: Tutorial, Review, and Research Prospects," Manufacturing & Service Operations Management, INFORMS, vol. 5(2), pages 79-141, September.
    6. 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.
    7. Gary M. Thompson, 1997. "Labor staffing and scheduling models for controlling service levels," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(8), pages 719-740, December.
    8. 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.
    9. Dietz, Dennis C., 2011. "Practical scheduling for call center operations," Omega, Elsevier, vol. 39(5), pages 550-557, October.
    10. Jens O. Brunner & Jonathan F. Bard & Jan M. Köhler, 2013. "Bounded flexibility in days‐on and days‐off scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(8), pages 678-701, December.
    11. 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.
    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. Lusby, Richard Martin & Range, Troels Martin & Larsen, Jesper, 2016. "A Benders decomposition-based matheuristic for the Cardinality Constrained Shift Design Problem," European Journal of Operational Research, Elsevier, vol. 254(2), pages 385-397.
    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. 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.
    16. 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.
    17. Brusco, Michael J. & Johns, Tony R., 1996. "A sequential integer programming method for discontinuous labor tour scheduling," European Journal of Operational Research, Elsevier, vol. 95(3), pages 537-548, December.
    18. 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.
    19. Giovanni Felici & Claudio Gentile, 2004. "A Polyhedral Approach for the Staff Rostering Problem," Management Science, INFORMS, vol. 50(3), pages 381-393, March.
    20. Alex Bonutti & Sara Ceschia & Fabio De Cesco & Nysret Musliu & Andrea Schaerf, 2017. "Modeling and solving a real-life multi-skill shift design problem," Annals of Operations Research, Springer, vol. 252(2), pages 365-382, May.

    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:inm:ormnsc:v:57:y:2011:i:1:p:151-163. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.