Harald Meyer auf'm Hofe: Nurse Rostering as Constraint Satisfaction with Fuzzy Constraints and Inferred Control Strategies

Abstract: This article reports on the commercial ORBIS Dienstplan system that has been developed in a collaboration of the GWI-SIEDA GmbH and the German Research Center for Artificial Intelligence (DFKI). This system solves constraint optimization problems representing nurse rostering tasks involving 250 to 1200 variables within a few minutes to a sufficient degree. Although the system is very successful on the German market, it still has some significant limitations. This system is extended in two ways: Fuzzy constraints are integrated in order to represent certain optimization tasks more accurately. Additionally, a generic method is proposed to infer search control knowledge from an abstraction of the original constraint representation. After sketching the problem representation and search algorithms, which are used by the currently sold nurse rostering system, this paper describes both extensions.