Efficient propagators for global constraints
Claude-Guy Quimper · UWSpace (University of Waterloo) · 2006
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. Claude-Guy Quimper ii We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The global cardinality constraint (GCC) ensures that a value v is assigned to at least lv vari-ables and to at most uv variables among a set of given variables where lv and uv are non-negative integers such that lv ≤ uv. The Inter-Distance constraint ensures that all variables, among a set of variables x1,..., xn, are pairwise distant from p, i.e. |xi − xj | ≥ p for all i � = j. The All-Different constraint, the GCC, and the Inter-Distance constraint are largely used in scheduling problems. For instance, in scheduling problems where tasks with unit processing time compete for a single