Abstract
Personnel rosters are typically constructed for a medium-term period under the assumption of a deterministic operating environment. However, organisations usually operate in a stochastic environment and are confronted with unexpected events in the short term. These unexpected events affect the workability of the personnel roster and need to be resolved efficiently and effectively. To facilitate this short-term recovery, it is important to consider robustness by adopting proactive scheduling strategies during the roster construction. In this paper, we discuss a proactive strategy that maximises the employee substitutability value in a personnel shift scheduling context. We propose a problem-specific population-based approach with local and evolutionary search heuristics to solve the resulting non-linear personnel shift scheduling problem and obtain a medium-term personnel shift roster with a maximised employee substitutability value. Detailed computational experiments are presented to validate the design of our heuristic procedure and the selection of the heuristic operators.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Burke, E., De Causmaecker, P., Vanden Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7, 441–499 (2004)
Ernst, A., Jiang, H., Krishnamoorthy, M., Owens, B., Sier, D.: An annotated bibliography of personnel scheduling and rostering. Ann. Oper. Res. 127, 21–144 (2004)
Ernst, A., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: a review of applications, methods and models. Eur. J. Oper. Res. 153, 3–27 (2004)
Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., De Boeck, L.: Personnel scheduling: a literature review. Eur. J. Oper. Res. 226, 367–385 (2013)
Abernathy, W., Baloff, N., Hershey, J.: A three-stage manpower planning and scheduling model - a service sector example. Oper. Res. 21, 693–711 (1973)
Dück, V., Ionescu, L., Kliewer, N., Suhl, L.: Increasing stability of crew and aircraft schedules. Transp. Res. Part C: Emerg. Technol. 20(1), 47–61 (2012)
Ionescu, L., Kliewer, N.: Increasing flexibility of airline crew schedules. Proc. - Soc. Behav. Sci. 20, 1019–1028 (2011)
Abdelghany, A., Ekollu, G., Narasimhan, R., Abdelghany, K.: A proactive crew recovery decision support tool for commercial airlines during irregular operations. Ann. Oper. Res. 127(1–4), 309–331 (2004)
Abdelghany, K., Abdelghany, A., Ekollu, G.: An integrated decision support tool for airlines schedule recovery during irregular operations. Eur. J. Oper. Res. 185(2), 825–848 (2008)
Eggenberg, N., Salani, M., Bierlaire, M.: Constraint-specific recovery network for solving airline recovery problems. Comput. Oper. Res. 37(6), 1014–1026 (2010)
Gao, C., Johnson, E., Smith, B.: Integrated airline fleet and crew robust planning. Transp. Sci. 43(1), 2–16 (2009)
Shebalov, J., Klabjan, D.: Robust airline crew pairing: move-up crews. Transp. Sci. 40, 300–312 (2006)
De Bruecker, P., Van den Bergh, J., Beliën, J., Demeulemeester, E.: Workforce planning incorporating skills: state of the art. Eur. J. Oper. Res. 243(1), 1–16 (2015)
Gurobi Optimization Inc.: Gurobi optimizer reference manual (2015). http://www.gurobi.com/documentation/
Bellanti, F., Carello, G., Della Croce, F.: A greedy-based neighborhood search approach to a nurse rostering problem. Eur. J. Oper. Res. 153, 28–40 (2004)
Burke, E., Curtois, T., Post, G., Qu, R., Veltman, B.: A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. Eur. J. Oper. Res. 188, 330–341 (2008)
Burke, E.K., Li, J., Qu, R.: A pareto-based search methodology for multi-objective nurse scheduling. Ann. Oper. Res. 196(1), 91–109 (2012)
Maenhout, B., Vanhoucke, M.: An evolutionary approach for the nurse rerostering problem. Comput. Oper. Res. 38, 1400–1411 (2011)
Beddoe, G., Petrovic, S.: Enhancing case-based reasoning for personnel rostering with selected tabu search concepts. J. Oper. Res. Soc. 58(12), 1586–1598 (2007)
Bilgin, B., De Causmaecker, P., Rossie, B., Vanden Berghe, G.: Local search neighbourhoods for dealing with a novel nurse rostering model. Ann. Oper. Res. 194(1), 33–57 (2012)
Burke, E.K., Li, J., Qu, R.: A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems. Eur. J. Oper. Res. 203(2), 484–493 (2010)
Maenhout, B., Vanhoucke, M.: An electromagnetic meta-heuristic for the nurse scheduling problem. J. Heuristics 13, 359–385 (2007)
Dowsland, K.: Nurse scheduling with tabu search and strategic oscillation. Eur. J. Oper. Res. 106, 393–407 (1998)
Maenhout, B., Vanhoucke, M.: Comparison and hybridization of crossover operators for the nurse scheduling problem. Ann. Oper. Res. 159, 333–353 (2008)
Vanhoucke, M., Maenhout, B.: On the characterization and generation of nurse scheduling problem instances. Eur. J. Oper. Res. 196, 457–467 (2009)
Acknowledgments
We acknowledge the support for the doctoral research project fundings by the Bijzonder Onderzoekfonds (BOF, Ghent University) under contract number 01N00712 and the National Bank of Belgium.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Ingels, J., Maenhout, B. (2017). A Memetic Algorithm to Maximise the Employee Substitutability in Personnel Shift Scheduling. In: Hu, B., López-Ibáñez, M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science(), vol 10197. Springer, Cham. https://doi.org/10.1007/978-3-319-55453-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-55453-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55452-5
Online ISBN: 978-3-319-55453-2
eBook Packages: Computer ScienceComputer Science (R0)