The AllDifferent Constraint with Precedences
  We propose AllDiffPrecedence, a new global constraint that combines together
an AllDifferent constraint with precedence constraints that strictly order
given pairs of variables. We identify a number of applications for this global
constraint including instruction scheduling and symmetry breaking. We give an
efficient propagation algorithm that enforces bounds consistency on this global
constraint. We show how to implement this propagator using a decomposition that
extends the bounds consistency enforcing decomposition proposed for the
AllDifferent constraint. Finally, we prove that enforcing domain consistency on
this global constraint is NP-hard in general.
