Horoplan: computer-assisted nurse scheduling using constraint-based programming

Stéfan J. Darmoni (1), Alain Fajner (2), Nathalie Mahé (1), Arnaud Leforestier (3), Marc Vondracek (2), Olivier Stelian (2), Michel Baldenweck (1)

(1) Information System, Computing and Telecommunications Department , Rouen University Hospital, 1 rue de Germont, 76031 Rouen Cedex, France,
(2) Bull DSII Cediag, Tour Bull, 92039 Paris La Défense Cedex 74, France,
(3) GIST, 119-121 Grande Rue, 92318 Sèvres Cedex, France

Correspondence and reprints to S.J. Darmoni, Id.. Tel (33) 35.88.49.00 Fax (33) 35.71.02.21, E-mail: Stefan.Darmoni@chu-rouen.fr

1. Background

Nurse scheduling is a difficult and time consuming task. The schedule has to determine the day to day shift assignments of each nurse for a specified period of time in a way that satisfies the given requirements as much as possible, taking into account the wishes of nurses as closely as possible. Manpower scheduling presents a considerable problem in most health organizations. The patient demand tends to fluctuate widely. The objectives of nurse scheduling are multiple: use of minimum staffing to avoid wasted manpower, provide adequate patient care, ensure continuity in service and satisfy organisational policies (Sitompul and Randhawa, 1990). In Rouen University Hospital, it takes approximately 4 hours for a head nurse to build the nurse schedule each month, and half an hour each day for rescheduling in case of a non scheduled absence. An another French study has shown that computerization of nurse scheduling cane save 8 hours of labour (Cosneau, 1993). The same figures are also found in an American study (Warner, Keller, and Martel 1991).

The goal of HOROPLAN (French acronym which stands for time scheduling) is to generate nurse scheduling and more generally health care professional scheduling, using a new approach, constraint based programming.

History of scheduling

The appropriate scheduling is a key to effectiveness and efficiency (Giglio, 1991) because nursing salaries make up the largest single element in hospital costs (Sitompul and Randhawa, 1990). Effective scheduling of nursing personnel is important in controlling health-care costs; it directly affects the quality of patient care (Sitompul and Randhawa, 1990). Resource scheduling is especially critical for health care institutions because they are arguably the most complex type of productive enterprise (Giglio, 1991). Scheduling formations are among the most difficult to solve of mathematical problems (Giglio, 1991).

There are basically two types of scheduling, cyclical and non-cyclical scheduling, and two types solution techniques, optimising and heuristic (Sitompul and Randhawa, 1990). In cyclical scheduling, each nurse work pattern is repeated in a cycle of N weeks. Non-cyclical scheduling generates a new scheduling period with available resources and policies that attempt to satisfy a given set of constraints. Optimisation is an objective function to optimise subject of a set of constraints. A heuristic procedure finds a good solution without guaranteeing to be the best one. These techniques avoid the excessive cost of using an optimizing approach (Sitompul and Randhawa, 1990).

Modelling of nurse scheduling is not a new idea. Until the 60s, scheduling tools consisted only of graphical devices (Giglio, 1991); in 1966, Howell (1966) proposed a cyclical nurse scheduling, followed by Ahuja and Sheppard. (1975), and Smith (1976). The applicability of cyclical scheduling is very limited (Okada et al., 1991) and lacks of flexibility (Sitompul and Randhawa, 1990). Sitomplu and Randhawa (1990), Bradley and Martin (1991), and Jelinek and Kavois (1992) reviewed extensively the literature on scheduling health care professional. Mathematical programming (Warner, 1976 and Miller, Pierskalla, and Rath, 1976) generally based on the optimisation concepts of linear programming (Ozkarahan, 1989; Ozkarahan, 1991; and Harmeier, 1991) are powerful but are not flexible. Goal programming (Arthur and Ravindran, 1981 and Musa and Saxena, 1984) is a more flexible method to compute nurse scheduling. In the early 70s, scheduling systems began to be based on heuristic models (Smith, Wiggins, and Bird, 1979 and Isken and Hancock, 1991)

Some authors already used artificial intelligence techniques, such as knowledge based systems (Lukman et al., 1991 and Chen and Yeung, 1993) and declarative programming using Prolog (Okada et al., 1991; Okada and Okada, 1988; and Okada, 1992). Since there are many possible solutions to build nurse scheduling and since the definition of the optimal solution is difficult if not ambiguous in that kind of problem, we do think that heuristic methods are more appropriate and more flexible than are mathematical methods. Expert systems are not really built to solve that kind of problems which are much more combinatory than imprecise (Opplobedu, Marcovich, and Tourbier, 1989). Neural networks may also provide the technology required to develop nurse scheduling (Jelinek and Kavois, 1992). Some are already commercial products (Scipione et al., 1992).

Facing the combinatorial class of mathematical problems (NP-complete problems), constraint-based programming (CBP) offered a new approach, reducing the search space because it defines a set of values for the variables which respect all the constraints. We believe that CBP technology is the most relevant and cost-effective answer to solve nurse scheduling problem: the "constraint and generate" paradigm replaces the costly "generate and test". None the less, the advantages of CBP should be proved versus any other techniques in a nurse trial. The CBP technology is currently applied to the specific Japanese nurse scheduling (Astier et al., 1993).

2. Methods

This computer-assisted nurse scheduling was designed by a project group consisting of six head nurses and two computer scientists of the Rouen University Hospital and three computer scientists and a business engineer of Bull DSII Cediag. Use and maintainability was foreseen from the start. Analysis of the nurse scheduling process was done before choosing computer programs and hardware. Technical choices were made according to this analysis, financial considerations and portability (Van Bemmel, 1993). We choice to develop Horoplan using Charme, a constraint-based programming language (Van Hentenryck, 1989) in the MS-DOS environment. Hardware is a Zenith microcomputer with a 80486DX microprocessor, 10 Megabytes of RAM for development and for runtime. Hard disk occupation is less than 2 Megabytes. In addition to the planning module built in Charme, a complete interface was developed with Borland C++ v3.1 and Ms-Windows v3.1. This allowed end-users to define mostly with the mouse all the data needed for scheduling, activate the planner and visualize the results.

Charme

Charme is a constraint-based programming (CBP) shell of the BULL Company (Opplobedu, Marcovich, and Tourbier, 1989). This language came from the European Computer Industry Research Centre (Munich) and especially dedicated to industry with its syntax, its architecture and its portability. The three main parts of a Charme program with regards to constraint solving are: (a) data structure definition, (b) stating the constraint and (c) the value enumeration part. In stating the constraint phase, developers describe the problem. After this part, the labelling phase chooses variables and values to determine a real solution. Strategies must be well worked out because the standard generation does not offer sufficient guarantees of time reply and specificity of application domain.

CBP has several key points :

  1. It first considers a finite set of n variables {X1, X2, ..., Xn} (called "decisions variables") having domains D1, D2, ..., Dn respectively where each Di represents the set of all possible values for the Xi variable.
  2. It allows to define relations between variables which must be verified: these relations are called constraints. There are two types of constraints: hard constraints which must be always verified and can not be over ruled; in that case, for the nurse scheduling problem, the head nurse has to intervene; floppy constraints which can be over ruled with a certain cost.
  3. Solving a constraint satisfaction problem means finding a single or many feasible solutions that satisfy the constraints, and if necessary, optimize a given cost function. This solving step implements problem specific strategies based on domain dependent heuristics, that choose a variable to instanciate and then a value for this variable (among its domain) until all variables are instantiated.
  4. The main idea of the CBP is to use constraints to prune the search tree in a "a priori" way, propagating information and thus reducing domains of variables. The first-fail principle is used to detect a fail as soon as possible, avoiding the inefficient comportment of conventional backtracking algorithm.

The Charme technology, based on C language, offers the same syntax and possibilities (arrays, trees, control instructions...). Charme runs in two environments : MS-DOS and UNIX. So it allows to use extern graphical displays like Windows or X-Window.

Description of HOROPLAN

The project group analysed the steps in building the nurse schedule by the head nurse. Horoplan is a step by step procedure for accommodating the work pattern and individual preferences of nurses given a certain service level.
Horoplan generates a six-week nurse schedule.
step 1 is the allocation of nurses from the department pool (which is the number of nurses who work regularly in the department) in a care unit. The allocation defines the number of nurses from a department pool who will work in a care unit during one schedule. This allocation is performed by the head nurse. In Horoplan, the head nurse inputs the allocation.
step 2 is the process of determining how many personnel must be employed by the organisation to provide a predetermined level of service (Bradley and Martin, 1991). In the aggregate, staffing is measured in full-time equivalents to ensure that an adequate number of personnel are available to maintain services, even though the number available for scheduling is reduced by annual leave, compensatory time and training (Bradley and Martin, 1991). That is why, in France, the number available for scheduling is roughly half of the total of nurses in a care unit. In Rouen, there are four possible shifts: morning (6.30 a.m. to 2.30 p.m.), afternoon (1.00 p.m. to 9.00 p.m.), day (9.00 a.m. to 5.00 p.m.) and night (8.45 p.m. to 6.45 a.m.). Three main different working contracts are possible : (a) full-time, (b) fifty per cent time, (c) eighty per cent time. Each day, the head nurse must forecast the number of nurses required for each shift. In Horoplan, the head nurse inputs the staffing. The Figure 1 displays an example of how the head nurse imputs the staffing .
step 3 is to place the scheduled absences ; e.g, training and paid holidays (twenty eight days for a nurse in France).
step 4 is to list the wishes of the nurses. For each month, a nurse can specify five wishes. The first one is the main wish and the others are secondary. When possible, the head nurse would try to satisfy the main one. For a nurse, a wish consists of a day and a shift (working shift or day-off). The Figure 2 shows an example of wishes of a nurse inputted by the head nurse.
step 5 is to fill the night shift. This night scheduling is variable according to the department.
step 6 is to position the week-ends and days-off. Each nurse must be given four days-off (RH) within two weeks and two of them must be consecutive. For each holiday at work, a nurse should obtain a compensatory day-off called RC. Part-time nurses are given a number of part-time days-off (RTP) each week.
step 7 is to check undesirable patterns: By French law, some patterns such as 'P.m. / A.m.' and 'Day-off / Work / Day-off' are prohibited. In the reality, head nurses sometimes desobey this rule. No more than two occurrences of such patterns is an acceptable rule for each schedule.
step 8 is to integrate the experience of the nurses. Nurses have different levels of experience and the schedule must take this into account. For example, a novice must be supervised by an experienced nurse. Some shifts are prohibited for novices.
step 9 is to check the global consistency of the schedule. The Figure 3 shows an example of a schedule generated by Horoplan.

As much as possible, shifts should be balanced equally among nurses over a period of two months. To obtain this equity, the head nurse must keep precise records thoughout the year.
The timetable (see Figure 3) is never frozen. All absences or permutations are automatically reported. All month long, the timetable represents the real situation of the staff. Rescheduling is possible at any time specially in case of an unpredictable absenteeism.

Data structures

For modeling a schedule, some variables and sets of values (representing decision variables), must be defined. A timetable is represented by a matrix giving the shift for each day and each nurse. If there are ten nurses, the search space which is the cartesian product of all the variable domains is about 10420 combinations. Also, requirements are represented as an array.

The constraints

Four levels of constraints were defined to give a maximum of flexibility to Horoplan: French level (e.g. number of worked hours in a year), hospital level (e.g. specific day-off), department level (e.g. specific shift) and care unit level (e.g. specific pattern for week-ends). First, we consider the hard constraints that must be respected in all coherent solutions of the problem. The first one is to satisfy daily requirements for each shift. In this part, we use the predefined constraint distribution to assign a number of occurrences for each shift :After this distribution, we have to consider undesirable patterns, such as the A.m.-P.m. pattern. Using Charme demons, we can control the maximum of occurrences. Another constraint is the work-time duration, we consider that nurses do not work more than six days at a stretch. We satisfy this rule by requiring of a day-off in each period of seven days.

The labelling part

Finding a solution means defining a set of values which respect all the constraints. This implies scanning the search space until a solution of the variables compatible with the constraints is found. Charme relies on three mechanisms to efficiently scan the search space: constraint propagation, backtrack and generation heuristics. When a constraint is defined, Charme deduces data concerning all the possible values of this variable (its domain). This data is immediately subjected to other constraints already applied to same variable. This processing can result in the permanent deletion of the values of the domain of the variable. When the domain of one variable is modified, this information is propagated on the other variables affected by the constraint. The domain of the variables represents all possible values occurring in a solution. Constraint propagation reduces systematically and drastically the domains of the variables and dramatically speeds up the search. A solution is obtained when all variables are known. Constraint propagation is suspended when no further data can be deduced for all the possible values of the variables. When a domain becomes empty, the partial configuration obtained cannot be part of solution and a backtrack occurs. In that case, Charme cancels the consequences of its last choice and resumes the search for a solution. Constraint propagation by itself is not sufficient to determine all the variables once the constraints have been set. Most of the time, a generation mechanism is needed which defines the sequence in which variables will be given a value. A standard generation strategy selects the variables with the smallest domain (Astier et al., 1993).
In the labelling part, in addition to variables and values selection, we set up strategies to determine a balanced schedule. That is why we defined objective criteria: Most of which are cumulative counters for the variables; e.g., number of unsatisfied wishes, number of worked Sunday mornings, number of worked week day afternoons. These counters are calculated by Horoplan for each period of time. According to the date, we defined estimated and realised counters. The Figure 4 displays an example of counters for a scheduled month.
As close as possible, nurses wishes must be satisfied. This requirement implies that nurses are sorted previously on realised wishes. For week-end work, the planning must be equitable over a period of two months. So, to assign nurses on a Sunday, we choose one on a personnel list sorted on number of Sunday's worked period. After assuring all nurses on this Sunday (work or rest), we try to affect the Saturday. The chosen rule is : Try to assign the same shift on Saterday and Sunday. To prevent infeasible schedules, we consider a list of shifts and we try successively to assign one on this list. The components are: (a) same shift (A.m. or P.m.), (b) day-off (RH), (c) P.m. or A.m., (d) others possibilities (e.g. compensatory day-off).
After week-ends assignements, we consider the other days. Overall planning is a very complex structure. It must take into account continuity and equity on assigned shifts. To introduce this strategy, we consider the following rules :(a) if a nurse works on day J (Monday to Friday), try to assign the same shift on day J+1. (b) if a nurse is unassigned on day J, construct a list of possible assignements for day J+1. The first component is a rest-shift and the others are work-shifts sorted on a criteria of insufficient allocation. The shuffling is biased according to each staffer's account balance: the staffer who owes the most is the most likely to be scheduled.

Criteria to evaluate nurse scheduling

Warner (1976) proposed the following criteria to evaluate scheduling methodologies in hospitals: