(PDF)
Lars Hellsten.
Consistency Propagation for Stretch Constraints.
MMath thesis,
University of Waterloo, School of Computer Science,
2004.
Scheduling and rostering problems are among the most common applications of constraint programming. In this thesis, we explore several global constraints for rostering problems. We demonstrate algorithms for efficiently enforcing domain consistency for these constraints, and show empirically that achieving this strongest possible level of consistency is not only of theoretical interest, but also has substantial value in practical applications.
The focus of the thesis is a domain consistency algorithm for the stretch constraint based on dynamic programming. We also present an incremental version that sometimes performs better in practice, but requires more memory. We then show how this constraint, along with our algorithms, can be generalized to variants that subsume other rostering constraints from the literature. For certain other extensions of stretch that seem intuitively simple and useful, we prove that enforcing domain consistency is NP-hard.