Classification of Various Neighborhood Operations for the Nurse Scheduling Problem

Manual scheduling of nurses with consideration of numerous constraints is time consuming, and an automatic scheduler for planning a satisfactory schedule is required. Since the nurse scheduling problem (NSP) is a problem of finding a feasible solution, the solution space must include infeasible solutions to solve it using a local search algorithm. However, the solution space consisting of all the solutions is so large that the local search algorithm requires much CPU time for search. In the NSP, some constraints have higher priority. Therefore, we can define the solution space to be the set of solutions satisfying some of the important constraints, which are called the elementary constraints. On the other hand, the connectivity of the solution space is important for the performance of the local search algorithm. However, the connectivity is not obvious when the solution space consists only of solutions satisfying the elementary constraints and is composed of small neighborhoods. This paper gives theoretical support for using 4-opt-type neighborhood operations by discussing the connectivity of its solution space and the size of the neighborhood. Another interesting point in our model is that a special case of the NSP corresponds to the bipartite transportation problem, and our result also applies to it.