Constraint-based rostering using meta-level reasoning and probability-based ordering

摘要

Constraint programming (CP) techniques have been widely used in many different types of applications. However for difficult NP-hard problems, such as rostering, scheduling and resource allocation, standard CP techniques alone might not be enough to find solutions efficiently. This paper introduces a technique, called "meta-level reasoning and probability-based ordering" (MRPO), that has performed very well on a nurse rostering problem. MRPO consists of two procedures - meta-level reasoning (MR) and probability-based ordering (PO). MR is a resolution procedure that is executed before search starts. It automatically generates redundant or implied constraints from posted constraints. These new constraints help in further reducing the search space prior to search as well as determining whether the problem is solvable or not. PO, on the other hand, is a type of value heuristic that is based on probability. Experiments show that our MRPO approach outperforms other common CP techniques and heuristics as well as other scheduling techniques, such as genetic algorithm (GA) or hybrid GA+CP algorithms. We have tested our algorithm on problems with relatively large search space - roughly 3.74×10{sup}50. Traditional CP techniques will not be able to generate any solution after 12h. MRPO, on the other hand, returns a solution within only half a second.