ナーススケジューリングにおける探索空間のネットワーク表現

Abstract

Nurse scheduling is adifficult combinatorial problem. Moreover, it is difficult to evaluate solutions because many of the constraints are subconsciously considered and not specified. Therefore, techniques that can easily grasp the size of the solutions space and the possibility of modifying a schedule are needed. In this work, we consider a subproblem of nurse scheduling to determine the optimal schedule for a nurse. We then represent all the feasible schedules of a subproblem as a network structure.In this structure, each node and each path represent a 7-day schedule and a feasible schedule, respectively. We develop a scheduling algorithm by using the network screated for each nurse and present two types of reduced networks that can help the scheduler create and modify a schedule