A study of nurse scheduling in Japan

Scheduling nurses to staff shifts is a major problem in hospitals. 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, is incredibly difficult. It is often impossible to develop a schedule which satisfies all the requirements despite the time and resources spent in the effort. This paper summarizes all our published research on nurse scheduling to date. The difficulties realized by our two investigations in Japan are shown first, together with a resulting scheduling problem. The nurse scheduling model based on the results is then described. In this model, all constraints are divided into two essentially different types; that which maintains a certain level of skill for each shift ('shift constraints') and that which concerns the workload for each nurse ('nurse constraints'). By classifying the constraints in this manner, we can determine what is affected by a specific constraint when the constraint is not satisfied. We developed efficient algorithms while taking advantage of the structure of this model. Finally, it is shown that our algorithm can solve this problem for a 2-shift system efficiently.