Many problems from artificial intelligence can be described as constraint
satisfaction problems over finite domains (CSP(FD)), that is, a solution
is an assignment of a value from a finite domain to each problem variable
such that a set of constraints is satisfied. Arc-consistency algorithms
remove inconsistent values from the set of values that can be assigned
to a variable (its domain), thus reducing the search space. We have developed
two parallelisation models of arc-consistency to be run on MIMD multiprocessors.
Two different policies, static and dynamic, to schedule the execution of
constraints have been tested. In the static scheduling policy, the set
of constraints is divided into N partitions, which are executed in parallel
on N processors. We discuss an important factor affecting performance,
the criterion to establish the partition in order to balance the run-time
workload. In the dynamic scheduling policy, any processor can execute any
constraint, improving the workload balance. However, a coordination mechanism
is required to ensure a sound order in the execution of constraints. Both
parallelisation models have been implemented on a CRAY T3E multiprocessor
with up to thirty four processors. Empirical results on speedup and behaviour
of both models are reported and discussed.