This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms 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. Keywords: Genetic Algorithms, Heuristics, Manpower Scheduling. In recent years, Genetic Algorithms (GAs) have become increasingly popular for solving complex optimisation problems such as those found in the areas of scheduling or timetabling. Unfortunately, there is no pre-defined way of including constraints into GAs. This is probably one of their biggest drawbacks, as it does not make them readily amenable to most real world optimisation problems. Some methods for dealing with constraints do exist, notably penalty and repair functions. However, as noted by Michalewicz [1], their application and success is problem specific. Here we use an alternative approach: the genetic operators act on an unconstrained solution space whose elements are converted into solutions by a schedule builder that acts as the decoder for the GA. Our work differs from previous studies using a similar strategy in two ways. First, constraints are used actively to guide the heuristic reducing the reliance on penalty functions. However, the nature of our problem means that it is not possible for the schedule-builder to guarantee feasible solutions and much of our investigation involves finding the best way of balancing the conflicting issues of feasibility and solution cost. Second, we investigate the effectiveness of various different permutation crossover operators for implementations of this type, and consequently introduce a hybrid crossover that combines the desirable features of the best two. The work described in this paper has two objectives. The first is to develop a fast, flexible solution approach to a nurse rostering problem and second, to add to the body of knowledge on solving constrained problems using GAs. Although there are many published algorithms for nurse scheduling, some characteristics of our particular problem, as outlined in the next section, make these approaches unsuitable for us. An extensive summary of these methods can be found in Hung Without these features, around one third of instances required several hours of run-time to find good feasible solutions. Due to the high costs of such software, this is not a practical solution for many hospitals. Dowsland [8] 3 solves the problem using a Tabu Search approach. Her results are impressive in solving instances arising at a particular hospital, but are less good on data with different characteristics. The approach adopted here was motivated by previous research into a GA solution to the problem. Aickelin and Dowsland [9] show that a straightforward GA implementation is not able to tackle the problem. The addition of problem specific information, in the form of co-evolving sub-populations and a modified fitness function coupled with an intelligent hill-climber, yields reasonable solutions in a very short time. However, solution quality is not consistent and the nature of the modifications means that the approach may not be robust to small changes in problem specification. Thus, there is still room for improvement. Here we use a different strategy for a GA approach, in which the individuals in the population do not represent direct encodings of solutions. Instead, solutions are obtained via separate decoder heuristics that build solutions from permutations of the list of available nurses using the constraints as guides. These permutations are manipulated by the GA. The advantage of this strategy is that the GA can remain canonical, i.e. it solves an unconstrained problem and does not require a hill-climber or other problem-specific knowledge. Note that penalty functions might still be required if the decoder fails to find a feasible solution. This also makes the algorithm more flexible than the integrated approaches outlined above, as the GA component can remain unchanged if the problem changes, e.g. if there are new constraints or objectives. The idea of an indirect GA is not new, and similar approaches have been used for other problems, for example by Davis [10] and Palmer and Kershenbaum [11] . However, there is one major difference between our work and theirs: The nurse scheduling problem is not a simple permutation problem like job shop scheduling but has additional constraints and hence our decoders cannot guarantee to always produce feasible solutions. Thus, there is still some work to be done by a penalty function. Our computational experiments are designed to examine this aspect of the implementation, as well as investigating the influence of the choice of heuristic decoder and the crossover operator on solution speed and quality. The result is an algorithm that is still simple but robust enough to cope with this infeasibility. This is achieved by striking a balance between the stochastic elements of the GA and the deterministic nature of the proposed decoder. Our key tools for this are the setting of parameter values, deciding on genetic strategies and finding a suitable decoder function. The rostering problem tackled in this paper can be described as follows. The task is to create weekly schedules for wards of up to 30 nurses by assigning one of a number of possible shift patterns to each nurse. These schedules have to satisfy working contracts and meet the demand for a given number of nurses of different grades on each shift, while being seen to be fair by the staff concerned. The latter objective is achieved by meeting as many of the nurses' requests as possible and considering historical information to ensure that unsatisfied requests and unpopular shifts are evenly distributed. The problem is complicated by the fact that higher qualified nurses can substitute less qualified nurses but not vice versa. Thus scheduling the different grades independently is not possible. Furthermore, the problem has a special day-night structure as most of the nurses are contracted to work either days or nights in one week but not both. However due to working contracts, the number of days worked is not usually the same as the number of nights. Therefore, it becomes important to schedule the 'right' nurses onto days and nights respectively. It is the latter two characteristics that make this problem challenging for any local search algorithm as finding and maintaining feasible solutions is extremely difficult. Furthermore, due to this special structure previous nurse scheduling algorithms suggested in the literature cannot be used. Further details of the nurse-scheduling problem can be found in Aickelin and Dowsland [9]. As described in Dowsland and Thompson [12] the problem can be decomposed into three independent stages. The first stage ensures that there are enough nurses to provide adequate cover. The second stage assigns the nurses to the correct number of day or night shifts. A final phase allocates those working on particular day to the early or late shift on that day. Phases 1 and 3 are easily solved using classical optimisation models. Thus, this paper deals with the highly constrained second step. The numbers of days or nights to be worked by each nurse defines the set of feasible weekly work patterns for that nurse. These will be referred to as shift patterns or shift pattern vectors in the following. For each nurse i and each shift pattern j all the information concerning the desirability of the pattern for this nurse is captured in a single numeric preference cost p ij. This was done in close consultation with the hospital and is a weighted sum of the following factors: Basic shift-pattern cost, general day / night preferences, specific requests, continuity problems, number of successive working day, rotating nights / weekends and other working history information.
For example, special encoding schemes have been developed to exploit problem-specific knowledge when tackling a highly constrained real-world problem such as nurse rostering REF .
An Indirect Genetic Algorithm for a Nurse Scheduling Problem
Computers&Operations Research, 31(5), pp 761-778, 2004
Computer Science