Improvement on the 2-shift nurse scheduling algorithm

This paper proposes an improvement of the algorithm by Ikegami and Niwa for 2-shift nurse scheduling. In their algorithm, we prepare beforehand a set of all the schedules for each nurse which specify which days she or he is feasibly assigned to the nighttime shift with an extra information that the nurse can or cannot work for the remaining days. Also we define the objective function to measure the degree of violations of the nighttime-related constraints which are caused by a solution. Then we set out to compare all the prepared solutions for each nurse in terms of the value of the objective function given that the other nurses' schedules are fixed as specified by the current trial solution. Finally we choose the best solution from these individual best ones. This solution in turn will be used as the next trial solution to define a new optimization problem to be solved and so on. This creates an iterative process once the first trial solution is given. For it we use a solution that assigns nobody to the nighttime shift on any day. Also we keep that specific schedule which produced the current trial solution out of the comparison process to avoid a creation of a loop. The iteration is continued until we have a schedule whose value is zero, i.e. a schedule which satisfies the nighttime constraints. Starting from this schedule, we go to the second phase of satisfying the daytime constraints through the same process after we prepare a set of schedules for each nurse which satisfy the daytime constraints as in the first phase. We again use as the initial solution a schedule which assigns nobody to the daytime shift on any day. This algorithm obtains a good solution, but is often slow as it basically checks all the alternative schedules for each nurse. The main contribution of this paper is to reduce the time taken in solving the subproblem by curtailing the number of alternative schedules to be looked at in each iteration. The observation of a sequence of the trial solutions in the first phase of the algorithm to satisfy the nighttime constraints shows the following. The two adjacent trial solutions have a small difference where the difference is defined to be the number of days when the night shift is assigned in one solution while not in the other: the difference is 0 to 3. This leads us to the modified algorithm, which focuses only on the schedules that have a little difference from the current solution to be examined and results in a remarkable improvement.