Nurse Rostering with Genetic Algorithms

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.

A truncation in the Aryl Hydrocarbon Receptor of the CRL:WI(Han) rat does not affect the developmental toxicity of TCDD

The Aryl Hydrocarbon Receptor (AhR) is required for the toxicity of TCDD, and so the AhR of CRL:WI and CRL:WI(Han) rats was characterised. Western blot showed AhR proteins of ~110 and ~97 kDa in individual rats from both strains. The AhR cDNA from a CRL:WI(Han) rat with the ~110kDa protein revealed a sequence that was identical to that of the CRL:WI and SD rat. However, cloning of the AhR from a rat with the ~97kDa protein revealed a point mutation, and five variants encoding two C-terminally truncated variants of the AhR protein, arising from a point mutation in the intron/exon junction and consequent differential splicing. These C-terminally truncated variants were expressed and shown to give rise to a protein of ~97kDa; the recombinant AhR bound TCDD with an affinity that was not statistically different from the full-length protein. A single-nucleotide polymorphism (SNP) assay was developed, and showed that both alleles were represented in a Hardy-Weinberg equilibrium in samples of CRL:WI and CRL:WI(Han) populations; both alleles are abundant. Rats from two studies of TCDD developmental toxicity were genotyped, and the association with toxicity investigated using statistical analysis. There was no plausible evidence that the AhR allele had a significant effect on the toxic endpoints examined. These data show that the two AhR alleles are common in two strains of Wistar rat, and that the AhR alleles had no effect on TCDD-induced developmental toxicity in two independent studies.