Stéfan J. Darmoni (1), Alain Fajner (2), Nathalie Mahé (1), Arnaud Leforestier (3), Marc Vondracek (2), Olivier Stelian (2), Michel Baldenweck (1)
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
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. This paper presents a constraint-based, the artificial intelligence approach by describing a prototype implementation developed with the Charme language and the first results of its use in the Rouen University Hospital. Horoplan implements a non-cyclical constraint-based scheduling, using some heuristics. Four levels of constraints were defined to give a maximum of flexibility: 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). Some constraints must be always verified and can not be overruled and some constraints can be overruled with a certain cost. Rescheduling is possible at any time specially in case of a non scheduled absence.
Nursing staff, hospital; personnel staff and scheduling; personnel staff and scheduling information systems; nursing service; artificial intelligence; constraint programming; software; decision support system, management; job satisfaction.
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.
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).
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 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 :
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.
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
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.
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.
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.
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.
Warner (1976) proposed the following criteria to evaluate scheduling methodologies in hospitals:
More recently, Visser, Hasman and Van der Linden (1994) established
a questionnaire to measure acceptance and attittude towards a protocol
We will merge Warner's criteria and Visser's questionnaire to evaluate Horoplan (see Table 1). Table 1. Evaluation of Horoplan
_________________________________________________________ Question Frequency of Scores Mean score _________________________________________________________ 1 2 3 4 5 _________________________________________________________ Minimum coverage requirements 4 6 2 62 26 4.0 Balanced coverage 3 18 41 31 7 3.2 Quality (work stretch) 0 0 12 53 35 4.2 Quality (days-off & week-ends) 2 20 33 39 6 3.3 Quality (equalisation of rotation) 4 39 31 24 2 2.8 Flexibility* 0 0 1 3 2 4.2 Cost-effective* 0 0 0 3 3 4.5 Previous experience with computers* 0 2 2 2 0 3 Easy to use* 0 0 1 4 1 4 Clear and conveniant presentation* 0 0 0 3 3 4.5 Faster than previous sources* 0 0 0 1 5 4.8 Less conversation with colleagues* 0 3 1 2 0 2.8 Performance increases* 0 0 0 2 4 4.7 Would use in daily practise* 0 0 0 4 2 4.3 _________________________________________________________
Scores: 1=strongly disagree 2=disagree 3=in between 4=agree 5=strongly agree * Answer for each of the six head nurses of our project group
A hundred schedules were generated by Horoplan. These schedules were evaluated by the six head nurses of our project group. The results of the evaluation of Horoplan are displayed in Table 1. In 88 cases, Horoplan has given a full solution which covers the minimum requirements and the wishes of the nurses. In the other cases, Horoplan did not find a global solution in the 5 minutes limit that we fixed to generate a solution: in all these 12 cases, at least 4 weeks were scheduled. However, we need to optimise the balance workload beyond nurses. In the worst case, one million backtracks occured during the generation process of the schedule. Compared with 10420, this number of backtracks is negligible: Charme prunes the search tree quickly. When the minimum requirements are fulfilled, Horoplan schedules "neutral" shifts to let the head nurse to decide which shift to input. So, Horoplan is a flexible, interactive tool. Many constraints are defined as parameters to optimise the flexibility.
Building a complete nurse schedule with Horoplan including staffing, wishes and manual modifications requires about half an hour. Therefore, this prototype saves an average of three hours and a half per schedule each month.
Horoplan implements a non-cyclical constraint-based scheduling, using some heuristics. In spite of the direct link between this study and the Rouen University Hospital scheduling protocol and since constraints can be very easily written, added or modified, a core set of constraints can be adaptated to the particular need of a large part of French hospitals.
Users have complete flexibility in defining constraints that define their scheduling practices. Horoplan is designed to schedule all types of hospital personnel. We emphasised nurse scheduling because there is a large number of nurse needed to provide direct and high quality of care (Giglio, 1991). Future versions of Horoplan will calculate the staffing. If Horoplan is in use in all the 100 care units of the Rouen University Hospital, and if we extrapolate the 3.5 hours of labor savings in one care unit, the whole hospital would save 4200 hours of labour of head nurse per year, therefore saving yearly 70000 $. If 25% of the French hospitals used this software within the next five years, the French health system would save yearly 105,000 hours of labor, representing 1,575,000 $.
The authors thank Benoit Thirion for his librarian assistance and Myriam Quéré for her secretary assistance.