Consistency Propagation for Stretch Constraints
Lars Hellsten · 2004
I hereby declare that I am the sole author of this thesis. I authorize the University of Waterloo to lend this thesis to other institutions or individuals for the purpose of scholarly research. I further authorize the University of Waterloo to reproduce this thesis by photocopying or by other means, in total or in part, at the request of other institutions or individuals for the purpose of scholarly research. ii 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