  In recent years genetic algorithms have emerged as a useful tool for the
heuristic solution of complex discrete optimisation problems. In particular
there has been considerable interest in their use in tackling problems arising
in the areas of scheduling and timetabling. However, the classical genetic
algorithm paradigm is not well equipped to handle constraints and successful
implementations usually require some sort of modification to enable the search
to exploit problem specific knowledge in order to overcome this shortcoming.
This paper is concerned with the development of a family of genetic algorithms
for the solution of a nurse rostering problem at a major UK hospital. The
hospital is made up of wards of up to 30 nurses. Each ward has its own group of
nurses whose shifts have to be scheduled on a weekly basis. In addition to
fulfilling the minimum demand for staff over three daily shifts, nurses' wishes
and qualifications have to be taken into account. The schedules must also be
seen to be fair, in that unpopular shifts have to be spread evenly amongst all
nurses, and other restrictions, such as team nursing and special conditions for
senior staff, have to be satisfied. The basis of the family of genetic
algorithms is a classical genetic algorithm consisting of n-point crossover,
single-bit mutation and a rank-based selection. The solution space consists of
all schedules in which each nurse works the required number of shifts, but the
remaining constraints, both hard and soft, are relaxed and penalised in the
fitness function. The talk will start with a detailed description of the
problem and the initial implementation and will go on to highlight the
shortcomings of such an approach, in terms of the key element of balancing
feasibility, i.e. covering the demand and work regulations, and quality, as
measured by the nurses' preferences. A series of experiments involving
parameter adaptation, niching, intelligent weights, delta coding, local hill
climbing, migration and special selection rules will then be outlined and it
will be shown how a series of these enhancements were able to eradicate these
difficulties. Results based on several months' real data will be used to
measure the impact of each modification, and to show that the final algorithm
is able to compete with a tabu search approach currently employed at the
hospital. The talk will conclude with some observations as to the overall
quality of this approach to this and similar problems.
