Abstract
In this paper, we present a hybrid genetic algorithm for the well-known nurse scheduling problem (NSP). The NSP involves the construction of roster schedules for nursing staff in order to maximize the quality of the roster schedule subject to various hard constraints. In the literature, several genetic algorithms have been proposed to solve the NSP under various assumptions. The contribution of this paper is twofold. First, we extensively compare the various crossover operators and test them on a standard dataset in a solitary approach. Second, we propose several options to hybridize the various crossover operators.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aickelin, U., & Dowsland, K. A. (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. Journal of Scheduling, 3, 139–153.
Aickelin, U., & Dowsland, K. A. (2004). An indirect Genetic Algorithm for a nurse-scheduling problem. Computers and Operations Research, 31, 761–778.
Bremermann, H. J. (1962). Optimization through evolution and recombination. In M. C. Yovits, G. T. Jacobi, & G. D. Goldstine (Eds.), Self-organizing systems (pp. 93–106). Washington: Spartan.
Burke, E. K., Cowling, P., De Causmacker, P., & Vanden Berghe, G. (2001). A memetic approach to the nurse rostering problem. Applied Intelligence, 3, 199–214.
Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7, 441–499.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems—a bibliographic survey. European Journal of Operational Research, 151, 447–460.
Davis, L. (1985). Applying adaptive algorithms to epistatic domains. Proceedings of the Ninth International Joint Conference on Artificial Intelligence, 1, 162–164.
Dias, T. M., Ferber, D. F., de Souza, C. C., & Moura, A. V. (2003). Constructing nurse schedules at large hospitals. International Transactions in Operational Research, 10, 245–265.
Ernst, A. T., Jiang, H., Krishamoorty, M., Owens, B., & Sier, D. (2004a). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153, 3–27.
Ernst, A. T., Jiang, H., Krishamoorty, M., Owens, B., & Sier, D. (2004b). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127, 21–144.
Felici, G., & Gentile, C. (2004). A polyhedral approach for the staff rostering problem. Management Science, 50, 381–393.
Fraser, A. S. (1957). Simulation of genetic systems by automatic digital computers. Australian Journal of Biological Sciences, 10, 484–491.
Glover, F., & McMillan, C. (1986). The general employee scheduling problem: an integration of MS and AI. Computers and Operations Research, 13, 563–573.
Goldberg, D. E., & Lingle, R. (1985). Alleles, loci, and the travelling salesman problem. In J. Grefenstette (Ed.), Proceedings of the first international conference on genetic algorithms and their applications (pp. 154–159). Hillsdale: Erlbaum.
Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130, 449–467.
Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. Republished by MIT Press (1992).
Inoue, T., & Furuhashi, T. (2003). A proposal of combined method of evolutionary algorithm and heuristics for nurse scheduling support system. IEEE Transactions on Industrial Electronics, 50, 833–841.
Jan, A., Yamamoto, M., & Ohuchi, A. (2000). Evolutionary algorithms for nurse scheduling problem. In Proceedings of the 2000 congress on evolutionary computation (pp. 196–203).
Kapsalis, A., Rayward-Smith, V. J., & Smith, G. D. (1993). Solving the graphical Steiner tree problem using genetic algorithms. Journal of the Operational Research Society, 44, 397–406.
Maenhout, B., & Vanhoucke, M. (2006). New computational results for the nurse scheduling problem: a scatter search algorithm. In Lecture notes in computer science (Vol. 3906, pp. 158–170). Berlin: Springer.
Maenhout, B., & Vanhoucke, M. (2007). An electromagnetism meta-heuristic for the nurse scheduling problem. Journal of Heuristics, 13, 359–385.
Michalewicz, Z. (1995). A survey of constraint handling techniques in evolutionary computation methods. In Proceedings of the fourth annual conference on evolutionary programming (pp. 135–155). San Diego, California.
Osogami, T., & Imai, H. (2000). Classification of various neighbourhood operations for the nurse scheduling problem. In Lecture notes in computer science (Vol. 1969, pp. 72–83). Berlin: Springer.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers and Operations Research, 22, 5–13.
Reeves, C. R. (1996). Hybrid genetic algorithms for bin-packing and related problems. Annals of Operations Research, 63, 371–396.
Syswerda, G. (1996). Schedule optimisation using genetic algorithms. In L. Davis (Ed.), Handbook of genetic algorithms (pp. 335–349). London: Thomson.
Thompson, G. M. (1995). Improved implicit optimal modelling of the labour shift scheduling problem. Management Science, 43, 595–607.
Vanhoucke, M., & Maenhout, B. (2005). Characterisation and generation of nurse scheduling problem instances (Working Paper 05/339). Ghent University.
Vanhoucke, M., & Maenhout, B. (2007). NSPLib—A nurse scheduling problem library: a tool to evaluate (meta-)heuristic procedures. In S. Brailsford & P. Harper (Eds.) Proceedings for the 31st annual meeting of the working group on operations research applied to health services (pp. 151–165). Oxford: Peter Lang.
Warner, H. W. (1976). Scheduling nursing personnel according to nursing preference: a mathematical approach. Operations Research, 24, 842–856.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Maenhout, B., Vanhoucke, M. Comparison and hybridization of crossover operators for the nurse scheduling problem. Ann Oper Res 159, 333–353 (2008). https://doi.org/10.1007/s10479-007-0268-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0268-z