´Ecole des Mines de Nantes – BP 20722

In this paper, we introduce a new solving algorithm for Constraint Satisfaction Problems (CSP). It performs an overall local search helped with a domain filtering tech-nique to prune the search space. Conflicts detected dur-ing filtering are used to guide the search. First experi-ments with a tabu version of the algorithm have shown good results on hard instances of open shop scheduling problems. It competes well with the best highly special-ized algorithms