An efficient approach to nurse scheduling – implementation for a 2-shift case

This paper deals with the scheduling of nurses to staff shifts at a hospital. The basic difficulty is the necessity of maintaining a certain level of service and skill in the makeup of every shift, while balancing the workload among the nurses involved. As a result it is usually impossible to develop a schedule which satisfies all the requirements, in spite of the time and resources spent in the effort. In this paper we present an efficient approach to this scheduling problem whose constraints are of block-angular structure: it consists of blocks of constraints which can be dealt with independently without a set of coupling constraints. Each of these blocks corresponds to a set of requirements for a specific nurse, and the coupling constraints are associated with the requirements in developing the overall makeup of each shift. An objective function is first defined to measure the degree of violation caused by a schedule. We set out to optimize a problem defined by this objective function and the block of constraints for one nurse, given that the other nurses' schedules are fixed as specified in the current trial schedule. (For the first trial schedule, we used one which leaves all the nurses unassigned.) Using this trial schedule throughout, we optimize every nurse's schedule in turn by fixing those of the other nurses. Out of the resulting schedules, every one of which differs from the trial schedule only in assignments for one nurse, we choose the one with the minimal value for the objective function. This becomes the new trial solution for the next iteration, and we repeat this iterative process until a satisfactory and hopefully feasible schedule is obtained. We have implemented this approach and constructed an algorithm for a 2-shift case. As the night shifts present more stringent and tighter constraints, it first finds a schedule to satisfy them, and then seeks a schedule to satisfy the daytime constraints. This approach is particularly effective where there are many constraints.