Abstract
In this work, we propose a general integer programming model to address the staff scheduling problem, flexible enough to be easily adapted to a wide-range of real-world problems. The model is applied with slight changes to two case studies: a glass plant and a continuous care unit, and also to a collection of benchmark instances available in the literature. The emphasis of our approach is on a novel formulation of sequence constraints and also on workload balance, which is tackled through cyclic scheduling. Models are solved using the CPLEX solver. Computational results indicate that optimal solutions can be achieved within a reasonable amount of time.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abdennadher, S., & Schlenker, H. (1999). Nurse scheduling using constraint logic programming. In Proceedings of the 11th conference on innovative applications of artificial intelligence, pp. 838–843.
Aickelin, U., & White, P. (2004). Building better nurse scheduling algorithms. Annals of Operations Research, 128(1–4), 159–177.
Alfares, H. (2004). Survey, categorization, and comparison of recent tour scheduling literature. Annals of Operations Research, 127(1), 145–175.
Azaiez, M. (2005). A 0–1 goal programming model for nurse scheduling. Computers & Operations Research, 32(3), 491–507.
Baker, K. R. (1976). Workforce allocation in cyclical scheduling problems: A survey. Operational Research Quarterly, 27(1), 155–167.
Balakrishnan, N., & Wong, R. T. (1990). A network model for the rotating workforce scheduling problem. Networks, 20, 25–42.
Bard, J. F., Binici, C., & DeSilva, A. H. (2003). Staff scheduling at the United States Postal Service. Computers & Operations Research, 30(5), 745–771.
Bechtold, S., & Jacobs, L. (1990). Implicit modeling of flexible break assignments in optimal shift scheduling. Management Science, 36(11), 1339–1351.
Blöchliger, I. (2004). Modeling staff scheduling problems. A tutorial. European Journal of Operational Research, 158(3), 533–542.
Brusco, M., & Johns, T. (1996). A sequential integer programming method for discontinuous labor tour scheduling. European Journal of Operational Research, 95(3), 537–548.
Burke, E., Causmaecker, P.D., & Berghe, G.V. (1999). A hybrid tabu search algorithm for the nurse rostering problem. In Lecture Notes in Artificial Intelligence (Vol. 1585, pp. 187–194). Berlin: Springer.
Burke, E., Cowling, P., De Causmaecker, P., & Berghe, G. (2001). A memetic approach to the nurse rostering problem. Applied Intelligence, 15(3), 199–214.
Burke, E., De Causmaecker, P., Berghe, G. V., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7(6), 441–499.
Burke, E., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., & Woodward, J. R. (2010a). A classification of hyper-heuristic approaches. In M. Gendreau & J. Y. Potvin (Eds.), Handbook of metaheuristics. International Series in Operations Research & Management Science, (Vol. 146, pp. 449–468). Berlin: Springer.
Burke, E., Li, J., & Qu, R. (2010b). A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems. European Journal of Operational Research, 203(2), 484–493.
Carrasco, R. C. (2010). Long-term staff scheduling with regular temporal distribution. Computer methods and programs in biomedicine, 100(2), 191–9.
Burke, E., & Soubeiga, E. (2003). Scheduling nurses using a tabu-search hyperheuristic. In Proceedings of the 1st multidisciplinary international conference on scheduling: Theory and applications (MISTA 2003), Nottingham, UK, pp. 180–197.
Dantzig, G. B. (1954). Letter to the editor—a comment on edie’s “traffic delays at toll booths”. Operations Research, 2(3), 339–341.
De Causmaecker, P., & Vanden Berghe, G. (2010a). A categorisation of nurse rostering problems. Journal of Scheduling, 14(1), 3–16.
De Causmaecker, P., & Vanden Berghe, G. (2010b). Towards a reference model for timetabling and rostering. Annals of Operations Research, 177, 1–10.
Eitzen, G., Panton, D., & Mills, G. (2004). Multi-skilled workforce optimisation. Annals of Operations Research, 127(1–4), 359–372.
Enz, C. A. (2009). Key issues of concern in the lodging industry: What worries managers. Cornell Hospitality Report 4. The Center for Hospitality Research, School of Hotel Administration, Cornell University.
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–4), 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.
Gans, N., Koole, G., & Mandelbaum, A. (2003). Telephone call centers: Tutorial, review, and research prospects. Manufacturing and Service Operations Management, 5(2), 79–141.
Glass, C. A., & Knight, R. A. (2010). The nurse rostering problem: A critical appraisal of the problem structure. European Journal of Operational Research, 202(2), 379–389.
Laporte, G. (1999). The art and science of designing rotating schedules. The Journal of the Operational Research Society, 50(10), 1011–1017.
Laporte, G., & Pesant, G. (2004). A general multi-shift scheduling system. Journal of the Operational Research Society, 55(11), 1208–1217.
Loucks, J., & Jacobs, F. (1991). Tour scheduling and task assignment of a heterogeneous work force: A heuristic approach. Decision Sciences, 22(4), 719–738.
Misir, M., Verbeeck, K., De Causmaecker, P., & Berghe, G. (2010). Hyper-heuristics with a dynamic heuristic set for the home care scheduling problem. In IEEE Congress on Evolutionary Computation (IEEE CEC), 2010, pp. 1–8.
Mora, M., & Musliu, N. (2004). Genetic algorithm for rotating workforce scheduling problem. In Computational cybernetics, 2004. ICCC 2004. Second IEEE international conference on IEEE, pp. 121–126.
Morris, J. G., & Showalter, M. J. (1983). Simple approaches to shift, days-off and tour scheduling problems. Management Science, 29(8), 942–950.
Moz, M., & Pato, M. V. (2004). Solving the problem of rerostering nurse schedules with hard constraints: New multicommodity flow models. Annals of Operations Research, 1976, 179–197.
Musliu, N. (2006). Heuristic methods for automatic rotating workforce scheduling. International Journal of Computational Intelligence Research, 2(4), 309–326.
Ni, H., & Abeledo, H. (2007). A branch-and-price approach for large-scale employee tour scheduling problems. Annals of Operations Research, 155(1), 167–176.
Qu, R., & He, F. (2009). A hybrid constraint programming approach for nurse rostering problems. In T. Allen, R. Ellis, & M. Petridis (Eds.), Applications and innovations in intelligent systems XVI, 28th SGAI international conference on innovative techniques and applications of artificial intelligence, Cambridge (pp. 211–224). London: Springer.
Rekik, M., Cordeau, J. F., & Soumis, F. (2009). Implicit shift scheduling with multiple breaks and work stretch duration restrictions. Journal of Scheduling, 13(1), 49–75.
Rong, A. (2010). Monthly tour scheduling models with mixed skills considering weekend off requirements. Computers & Industrial Engineering, 59(2), 334–343.
Sellmann, M., Zervoudakis, K., Stamatopoulos, P., & Fahle, T. (2000). Integrating direct CP search and CP-based column generation for the airline crew assignment problem. Transportation Science, 24, 163–170.
Thompson, G. M., & Goodale, J. C. (2006). Variable employee productivity in workforce scheduling. European Journal of Operational Research, 170(2), 376–390.
Topaloglu, S., & Ozkarahan, I. (2004). An implicit goal programming model for the tour scheduling problem considering the employee work preferences. Annals of Operations Research, 128(1–4), 135–158.
Totterdell, P. (2005). Work schedules. In J. Barling, E. K. Kelloway, & M. R. Frone (Eds.), Handbook of work stress (p. 53). London: Sage Publishers.
Ulusam Seçkiner, S., & Gökçen, H. (2007). An integer programming model for hierarchical workforce scheduling problem. European Journal of Operational Research, 183(2), 694–699.
Valouxis, C., & Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial Intelligence in Medicine, 20(2), 155–175.
Warner, D. M. (1976). Scheduling nursing personnel according to nursing preference: A mathematical programming approach. Operations Research, 24(5), 842–856.
Acknowledgments
This work is partially funded by the ERDF—European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the FCT—Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within Project FCOMP-01-0124-FEDER-022701.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rocha, M., Oliveira, J.F. & Carravilla, M.A. Cyclic staff scheduling: optimization models for some real-life problems. J Sched 16, 231–242 (2013). https://doi.org/10.1007/s10951-012-0299-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-012-0299-4