
## 3 Some Examples

To motivate the introduction of this global constraint, we give some examples of models where we have one or more sets of variables which take all-different values, as well as certain pairs of these variables which are ordered.

## 3.1 Exam Time-Tabling

Suppose we are time-tabling exams. A straight forward model has variables for exams, and values which are the possible times for these exams. In such a model, we may have temporal precedences (e.g. part 1 of the physics exam must be before part 2) as well as ALLDIFFERENT constraints on those sets of exams with students in common (e.g.

all physics, maths, and chemistry exams must occur at different times since there are students that need to sit all three exams).

## 3.2 Scheduling

Suppose we are scheduling a single machine with unit-time tasks, subject to precedence constraints and release and due times [14]. A straight forward model has variables for the tasks, and values which are the possible times that we execute each task. In such a model, we have an ALLDIFFPREC constraint on variables whose domains are the appropriate intervals. For example, consider scheduling instructions in a block (a straight-line sequence of code with a single entry and exit point) on one processor where all instructions take the same time to execute. Such a schedule is subject to a number of different types of precedence constraints. For instance, instruction A must execute before B if:
Read-after-write dependency: B reads a register written by A;
Write-after-write dependency: B writes a register also written by A; Write-after-read dependency: B writes a register that A reads.

Such dependencies give rise to precedence constraints between the instructions.

## 3.3 Breaking Value Symmetry

Many constraint models contain value symmetry. Puget has proposed a general method for breaking any number of value symmetries in polynomial time [15, 16]. This method introduces variables Zj to represent the index of the first occurrence of each value:

## Xi = J ⇒ Zj ≤ I, Zj = I ⇒ Xi = J

Value symmetry on the Xiis transformed into variable symmetry on the Zj . This variable symmetry is easy to break. We simply need to post precedence constraints on the Zj . Depending on the value symmetry, we need different precedence constraints.

Consider, for example, finding a graceful labelling of a graph. A graceful labelling is a labelling of the vertices of a graph with distinct integers 0 to e such that the e edges
(which are labelled with the absolute differences of the labels of the two connected vertices) are also distinct. Graceful labellings have applications in radio astronomy, communication networks, X-ray crystallography, coding theory and elsewhere. Here is the graceful labelling of the graph K3 × P2: