×

zbMATH — the first resource for mathematics

An indirect genetic algorithm for a nurse-scheduling problem. (English) Zbl 1048.90102
Summary: This paper describes a Genetic Algorithms (GAs) approach to a manpower-scheduling problem arising at a major UK hospital. Although GAs have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical GAs paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.

MSC:
90B35 Deterministic scheduling theory in operations research
90B60 Marketing, advertising
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Michalewicz Z. A survey of constraint handling techniques in evolutionary computation methods. Proceedings of the Fourth Annual Conference on Evolutionary Programming, San Diego, California, 1995. p. 135-55.
[2] Hung, R., Hospital nurse-scheduling, Journal of nursing administration, 1, 21-23, (1995)
[3] Sitompul, D.; Randhawa, S., Nurse scheduling modelsa state-of-the-art review, Journal of the society of health systems, 2, 62-72, (1990)
[4] Bradley, D.; Martin, J., Continuous personnel scheduling algorithmsa literature review, Journal of the society for health systems, 2, 8-23, (1990)
[5] Easton, F.; Mansour, N., A distributed genetic algorithm for employee staffing and scheduling problems, (), 360-367
[6] Tanomaru J. Staff scheduling by a Genetic Algorithm with heuristic operators. Proceedings of the IEEE Conference on Evolutionary Computation, New York 1995. p. 456-61.
[7] Fuller E. Tackling scheduling problems using integer programming. Master Thesis, University of Wales, Swansea, United Kingdom, 1998.
[8] Dowsland, K.A., Nurse scheduling with tabu search and strategic oscillation, European journal of operational research, 106, 393-407, (1998) · Zbl 0991.90055
[9] Aickelin, U.; Dowsland, K.A., Exploiting problem structure in a genetic algorithms approach to a nurse rostering problem, Journal of scheduling, 31, 139-153, (2000) · Zbl 0965.90019
[10] Davis L. Adapting operator probabilities in Genetic Algorithms. In: Schaffer J, editor. Proceedings of the Third International Reference on Genetic Algorithms and their Applications, San Mateo: Morgan Kaufmann Publishers, 1989. p. 61-7.
[11] Palmer C, Kershenbaum A. Representing trees in Genetic Algorithms. Proceedings of the First IEEE International Conference on Evolutionary Computation, New York 1994. p. 379-84.
[12] Dowsland KA, Thompson JM. Nurse scheduling with knapsacks, networks and Tabu Search. Journal of the Operational Research Society 2000; 825-33. · Zbl 1055.90548
[13] Holland, J., Adaptation in natural and artificial systems, (1976), University of Michigan Press Ann Arbor, MI
[14] Fogel, D., Evolutionary computation: the fossil record, (1998), IEEE Press New York · Zbl 0908.68210
[15] De Jong, K., Genetic algorithms are NOT function optimisers, (), 5-17
[16] Deb K. Genetic algorithms for function optimisation. Genetic Algorithms and Soft Computing 1996:4-31.
[17] Bäck, T., Applications of evolutionary algorithms, (1993), Dortmund Germany
[18] Chaiyaratana, N.; Zalzala, A., Recent developments in evolutionary and genetic algorithms: theory and applications, (), 270-277
[19] Beasley, J.; Chu, P., A genetic algorithm for the set covering problem, European journal of operational research, 94, 392-404, (1996) · Zbl 0953.90565
[20] Goldberg, D., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[21] Fang, H.-.L.; Ross, P.; Corne, D., A promising genetic algorithm approach to job-shop scheduling, rescheduling and open shop scheduling problems, (), 375-382
[22] Podgorelec, V.; Kokol, P., Genetic algorithm based system for patient scheduling in highly constrained situations, Journal of medical systems, 21, 417-427, (1997)
[23] Corne, D.; Odgen, J., Evolutionary optimisation of methodist preaching timetables, (), 143-155
[24] Goldberg, D.; Lingle, R., Alleles, loci, and the travelling salesman problem, (), 154-159
[25] Syswerda, G., Schedule optimisation using genetic algorithms, (), 335-349
[26] Reeves, C., Hybrid genetic algorithms for bin-packing and related problems, Annals of OR, 63, 371-396, (1996) · Zbl 0851.90098
[27] Davis, L., Applying adaptive algorithms to epistatic domains, Proceedings of the ninth international joint reference on artificial intelligence, 1, 162-164, (1985)
[28] Herbert E. Genetic algorithms for bin packing problems. PhD Dissertation, University of Wales, Swansea, United Kingdom, 1998.
[29] Aickelin U. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, Special Issue on Local Search, 2002, in print. · Zbl 1139.90428
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.