Nurse Rostering Using Constraint Programming and Meta-level Reasoning

摘要

Constraint programming techniques have been widely used in many different types of applications. However for NP-hard problems, such as scheduling, resources allocation, etc, basic constraint programming techniques may not be enough solve efficiently. This paper describes a design and implementation of a simplified nurse rostering system using constraint programming and automatic implied constraint generation by meta-level reasoning. The nurse rostering system requires generating a weekly timetable by assigning work shifts to nurse. Although the problem set is simplified, the search is difficult because it involves more than hundred constraints with a search space of about 3.74 x 10~(50). Using only traditional constraint programming techniques, even in addition with popular heuristics, no timetable can be generated in reasonable time. To improve the search, we propose to use automatic implied constraint generation by meta-level reasoning. Several solvable and non-solvable problem instances were tested. With our approach, these instances can be solved or identified as non-solvable within one second.