Skip to main content
Springer Nature Link
Log in

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Barnhart, C., Hane, C. A., & Vance, P. H. (2000). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48(2), 318–326.

    Article  Google Scholar 

  • Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.

    Article  Google Scholar 

  • Contreras, I., Díaz, J., & Fernández, E. (2011). Branch and price for large-scale capacitated hub location problems with single assignment. INFORMS Journal of Computing, 23, 41–55.

    Article  Google Scholar 

  • Côté, M. C., Gendron, B., Quimper, C. G., & Rousseau, L. M. (2011a). Formal languages for integer programming modeling of shift scheduling problems. Constraints, 16(1), 54–76.

    Google Scholar 

  • Côté, M. C., Gendron, B., & Rousseau, L. M. (2011b). Grammar-based integer programming models for multiactivity shift scheduling. Management Science, 57(1), 151–163.

    Google Scholar 

  • Côté, M. C., Gendron, B., & Rousseau, L. M. (2012). Grammar-based column generation for personalized multi-activity shift scheduling. INFORMS Journal of Computing. doi:10.1287/ijoc.1120.0514.

  • Crainic, T. G., Frangioni, A., Gendron, B., & Guertin, F. (2009). OOBB: An object-oriented library for parallel branch-and-bound. In: CORS/INFORMS international conference, Toronto, Canada.

  • Dantzig, G. B. (1954). A comment on Edie’s “Traffic delays at toll booths”. Journal of the Operations Research Society of America, 2(3), 339–341.

    Article  Google Scholar 

  • Demassey, S., Pesant, G., & Rousseau, L. M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315–333.

    Article  Google Scholar 

  • Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation. New York: Springer.

    Book  Google Scholar 

  • Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004a). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1), 21–144.

    Article  Google Scholar 

  • Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004b). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.

    Article  Google Scholar 

  • Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction to automata theory, languages and computability. Boston: Addison-Welsey.

    Google Scholar 

  • Lequy, Q., Bouchard, M., Desaulniers, G., Soumis, F., & Tachefine, B. (2010a). Assigning multiple activities to work shifts. Journal of Scheduling, 15(2), 239–251.

    Article  Google Scholar 

  • Lequy, Q., Desaulniers, G., Solomon, M. M. (2010b) Assigning team tasks and multiple activities to fixed work shifts. Cahiers du GERAD (G-2010-71). Montreal: HEC Montreal.

  • Lequy, Q., Desaulniers, G., Solomon, M. M. (2010c) A two-stage heuristic for multi-activity and task assignment to work shifts. Cahiers du GERAD (G-2010-28). Montreal: HEC Montreal.

  • Quimper, C. G., & Rousseau, L. M. (2009). A large neighbourhood search approach to the multi-activity shift scheduling problem. Journal of Heuristics, 16(3), 373–392.

    Article  Google Scholar 

  • Quimper, C. G., & Walsh, T. (2007). Decomposing global grammar constraints. In: Principles and practice of constraint programming-CP 2007. Lecture notes in computer science (Vol. 4741, pp. 590–604). New York: Springer.

  • Tang, L., Wang, G., & Liu, J. (2007). A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry. Computers & Operations Research, 34(10), 3001–3015.

    Article  Google Scholar 

  • Tang, L., Wang, G., Liu, J., & Liu, J. (2011). A combination of lagrangian relaxation and column generation for order batching in steelmaking and continuous-casting production. Naval Research Logistics, 58(4), 370–388.

    Article  Google Scholar 

  • van den Akker, J. M., Hoogeveen, J. A., & van de Velde, S. L. (1999). Parallel machine scheduling by column generation. Operations Research, 47(6), 862–872.

    Article  Google Scholar 

Download references

Author information

Author notes

  1. Vincent Boyer

    Present address: Graduate Program in Systems Engineering, Universidad Autónoma de Nuevo León (UANL), 66451 , San Nicolás de los Garza, Nuevo Leon, Mexico

Authors and Affiliations

  1. Centre interuniversitaire de recherche sur les réseaux d’Entreprise, la logistique et le transport, Université de Montréal, C.P. 6128, succursale Centre-ville, Montreal, QC, H3C 3J7, Canada

    Vincent Boyer, Bernard Gendron & Louis-Martin Rousseau

Authors
  1. Vincent Boyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernard Gendron
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Louis-Martin Rousseau
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vincent Boyer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boyer, V., Gendron, B. & Rousseau, LM. A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem. J Sched 17, 185–197 (2014). https://doi.org/10.1007/s10951-013-0338-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-013-0338-9

Keywords

Search

Navigation