In organizations such as hospitals, security companies, and call centers where staff members work in shifts, creating an appropriate roster or worker schedule is crucial for efficiency and worker satisfaction. However, creating a roster is a time-consuming and burdensome task because several conditions have to be satisfied to complete the task. The Nurse Scheduling Problem (NSP), in its simplest terms, can be explained as a scheduling problem where staff members are assigned certain shifts so that they can finish a given set of assignments most efficiently while satisfying a set of predetermined conditions. NSP is known to be a very difficult problem where there is no known algorithm guaranteed to efficiently finds a solution satisfying all the given conditions. In practice however, quickly finding a good solution satisfying as many conditions as possible is as effective as exhaustively searching for the best solution, if such a solution is even possible. We are researching algorithms that can find such a good solution efficiently to reduce the burden on roster creators.
For example, at a hospital, conditions that must be taken into account while creating a nurse roster include but are not limited to:
At Intelligent Systems Laboratory; we started by formally defining the problem and constructing evaluation functions to express how satisfying each condition affects the overall schedule quality and developed an algorithm which can quickly create a sufficiently practical solution.
There is a trade-off between speed and quality, in that even if a solution can be found quickly, but only satisfies a few conditions, a considerable amount of replanning and manual tweaks are necessary to create a satisfactory roster, which in turn reduces the value of an automated solution. One of the main research goals was, therefore, to create an algorithm which can quickly create a sufficiently practical solution.
As a result of our research, we developed a new algorithm which can create a schedule rivaling the quality of one created by a human expert. The "eKakushin Scheduler" is now available as a commercial product through SECOM Trust Systems Co., Ltd.
Furthermore, our new algorithm is highly flexible and can be used in many types of institutions with scheduling needs, not only hospitals. For example, SECOM emergency response personnel provide services 24/7, 365 days a year from over 1,000 offices throughout Japan. The personnel in each office work in shifts similar to a hospital, requiring each office to construct a roster. Our algorithm contributes to the efficient construction of their schedules.
The advantages of automating the process of roster generation include the time savings to create the roster and the possibility of adding more shift types. As shown in the figure below, automated schedule generation lead to a large reduction in time as compared to manual generation in all cases, with over a 90% reduction in some cases. This allows the person in charge of constructing rosters use their time more effectively, doing other tasks instead of creating a schedule. Since the resulting roster is subject to the defined constraints, the resulting roster will also evenly distribute the shifts without introducing any unintended degree of bias.
Furthermore, automating the process of building a roster allows the use of a larger number of shift types, which can lead to a reduction in personnel expenses. For example, in call centers, the number of incoming calls dictates the staffing requirements. As shown in the figures below, if there are only two types of shifts, there will be periods where an unnecessarily high number of operators are waiting for calls (shown in red in the left figure), representing a waste of human resources. However, by using different shifts as shown in the right figure, efficiency is increased leading to a reduction in human resources.
In this way, automated schedule generation have an effect other than the reduction of creation time for a roster. The nurse scheduling problem can be seen not just in the scheduling needs for hospitals, security companies and call centers, but in other markets such as convenience stores and hotels. In each market, a need exists for a system that can automate roster generation.