×

zbMATH — the first resource for mathematics

Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. (English) Zbl 0965.90019
Summary: There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm (GA) paradigm is not well equipped to handle the conflict between objectives and constraints that typically occur in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major U.K. hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating subpopulations. Problem-specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] (eds). Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 1153, Springer: Berlin, 1996.
[2] A distributed genetic algorithm for employee staffing and scheduling problems. In Proceedings ICGA, (ed.), vol. 5. Morgan Kaufmann: Los Aitos, CA, 1993; 360-367.
[3] Staff scheduling by a genetic algorithm with heuristic operators. Proceedings of the IEEE Conference on Evolutionary Computation, 1995; 456-461.
[6] Private communication, 1998. · Zbl 1015.91507
[7] Knapsack Problems. Wiley: Chichester, UK, 1990.
[11] Handling constraints in genetic algorithms. In ICGA, (ed.), vol. 4. Morgan Kaufmann: Los Aitos, CA, 1991; 151-157. [we make no use of this one].
[13] Some guidelines for genetic algorithms with penalty functions. In Proceedings ICGA, (ed.). vol. 3. Morgan Kaufmann: Los Aitos, CA, 1989; 191-197.
[14] Genetic optimisation using a penalty function. In Proceedings ICGA, (ed.). Morgan Kaufmann: Los Aitos, CA, 1993; 499-505.
[15] Genetic algorithms and combinatorial optimisation. In Applications of Modern Heuristic Methods. (ed.). Alfred Waller, 1995; 111-126.
[16] Adaption in Natural and Artificial Systems. University of Michigan Press: Ann Arbor, 1975.
[17] Epistasis variance: a viewpoint on GA-hardness. In Foundations of Genetic Algorithms, (ed.), vol. 1. Morgan Kaufmann: Los Aitos, CA, 1991; 23-35.
[18] Applying adaptive algorithms to epistatic domains. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, Mirchandi PB, Francis RL (eds), vol. 1. 1985; 162-164.
[19] A co-operative co-evolutionary approach to function optimization. In Parallel Problem Solving from Nature?PPSN III, (eds). Springer: Heidelberg, 1994; 249-257.
[21] Genetic algorithms are NOT function optimisers. In Foundations of Genetic Algorithms, (ed.). vol. 2. Morgan Kaufmann: Los Aitos, CA, 1993; 5-17.
[22] Reducing epistasis in combinatorial problems by expansive coding. Proceedings ICGA (ed.), vol. 5. Morgan Kaufmann: Los Aitos, CA, 1993; 400-406.
[23] Genetic Algorithms in Search, Optimisation and Machine Learning. Addison-Wesley: Reading, MA, 1989.
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.