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. In Japan, a roster is created on a monthly basis and contains approximately 30 employees, resulting in complex, numerous and interdependent conditions, which makes scheduling a taxing and time-consuming task. Thus there is an increasing need for a system which can support this task.

We are researching algorithms to automate the creation of rosters, and to reduce the burden on roster creators. We have developed a novel approach which has given very promising results and has since been built into a commercial scheduling system. Furthermore, this scheduling system is used internally at SECOM, to build rosters for the security staff. In this article, we will introduce our algorithm and explain the advantages of building rosters automatically.

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 as a hard combinatorial problem that has complex constraints thus producing rosters satisfying a given NSP is very difficult for both humans and computers. In organizations such as hospitals where staff members work in staggered shifts, an experienced individual is usually assigned the task of producing rosters. Still a considerable amount of time and effort is required to produce a roster for each scheduling period.

At a hospital, for example, conditions that must be taken into account while creating a nurse roster include but are not limited to:

• Daily conditions: At least three nurses assigned to the night shift while avoiding shifts comprised of only inexperienced nurses
• Monthly conditions: Equalizing the number of night shifts assigned to each nurse
• Shift conditions: Avoid assigning a night shift after a day-off
• Individual requests: Vacations and/or sickness

NSP is known to be a very difficult problem where there is no known algorithm guaranteed to efficiently find 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.

At IS Laboratory, we started by formally defining the problem and constructing evaluation functions to express how satisfying each condition affects the overall schedule quality. Next, by using linear programming and meta-heuristic methods, we constructed a fast hybrid algorithm which can produce good results based on the evaluation functions. 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 to create an algorithm which can quickly create a sufficiently practical solution.

After an incremental improvement process, our hybrid algorithm is able to 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., and is currently used in many hospitals throughout Japan.

Furthermore, our new hybrid 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. Our algorithm is used in call centers as well.

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 Figure 2, 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 dictate the staffing requirements. As shown in Figure 3, 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 Figure 3), representing a waste of human resources. However, by using different shifts as shown in Figure 4, efficiency is increased leading to a reduction in human resources.

Manually constructing a roster for an increased number of shift patterns makes scheduling a more arduous task for the scheduler. On the other hand, automated roster generation can deal with many different shift types without increasing the burden for the human in charge.

In this way, automated roster generation contributes in ways other than through the efficiency of the person tasked with creating rosters.

At its core, 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. At IS Laboratory, we have been working on generalizing our approach to enable use in other markets and building a new system which can leverage this approach.

Papers

1. Seiya Hasegawa, "Solving Nurse Scheduling Problem by IP-Based Local Search", The Institute of Electronics, Information and Communication Engineers (IEICE), Vol. J89-D, No.10, pp.2251-2259, 2006

International conferences

1. Ulas Bardak, Seiya Hasegawa, Takayuki Saito, "PointFix: Learning from Fixing Individual Condition Violations", IEEE Symposium Series on Computational Intelligence 2009, IEEE CI-Sched 2009, Nashville, TN, USA, March 30 - April 2, 2009
2. Seiya Hasegawa, Yukio Kosugi, "Solving Nurse Scheduling Problem by Integer-Programming- Based Local Search", IEEE International Conference on Systems, Man and Cybernetics, Proceedings #939(pp.1474-1480), Taipei, Taiwan, Oct. 8-11, 2006

Symposiums & Workshops

1. Seiya Hasegawa, Yukio Kosugi, "Work table scheduling system using IP-based local search", IEICE technical report Office Information Systems, OIS2006-7, pp.37-42,2006