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.
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.
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.
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.
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.
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.
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.
Demassey, S., Pesant, G., & Rousseau, L. M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315–333.
Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation. New York: Springer.
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.
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.
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction to automata theory, languages and computability. Boston: Addison-Welsey.
Lequy, Q., Bouchard, M., Desaulniers, G., Soumis, F., & Tachefine, B. (2010a). Assigning multiple activities to work shifts. Journal of Scheduling, 15(2), 239–251.
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.
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.
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.
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.
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-013-0338-9