TY - GEN
T1 - Nurse rostering using constraint programming and meta-level reasoning
AU - Wong, Gary Yat Chung
AU - Chun, Hon Wai
PY - 2003
Y1 - 2003
N2 - 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 1050. 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. © Springer-Verlag Berlin Heidelberg 2003
AB - 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 1050. 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. © Springer-Verlag Berlin Heidelberg 2003
UR - http://www.scopus.com/inward/record.url?scp=7044285800&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-7044285800&origin=recordpage
U2 - 10.1007/3-540-45034-3_72
DO - 10.1007/3-540-45034-3_72
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783540404552
T3 - Lecture Notes in Computer Science
SP - 712
EP - 721
BT - Developments in Applied Artificial Intelligence
A2 - Chung, Paul W. H.
A2 - Hinde, Chris
A2 - Ali, Moonis
PB - Springer
CY - Berlin, Heidelberg
T2 - 16th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE 2003)
Y2 - 23 June 2003 through 26 June 2003
ER -