Nowadays, many real problems can be modeled as constraint satisfaction problems (CSPs) and be solved using constraint programming techniques. These problems belong to different areas of knowledge such as: Artificial Intelligence, Operations Research, Information Systems, databases, etc. CSPs are NP-complete, so it is necessary to use tools that simplify the problem in order to find a solution in an efficient way. The most common techniques to handle a CSP are consistency techniques and search techniques. Consistency techniques, or filtering techniques, are designed to reduce the search space by filtering the variable domains. The arc-consistency techniques are mostly used since they carry out significant pruning of domains; by efficiently removing values that will not take part of a solution.

Therefore, proposing efficient algorithms to achieve arc-consistency has always been considered as a central question in the scientific community.

However, many works on arc-consistency make assumptions that are not present in many real life problems. For instance, the same pair of variables may be involved in two or more constraints, which is called non-normalized problem. Therefore, these problems would require a normalization process in order to use such algorithms, which can be prohibitive in large domains. In these cases, the 2-consistency is able to prune more search space than arc-consistency, so that search algorithms can be more efficient. However, little works have focused their attention in the development of 2-consistency algorithms.

In this thesis, we present new algorithms for arc-consistency and 2-consistency as preprocessing algorithms to solve constraint satisfaction problems. These algorithms have a better performance than the state of the art techniques in some efficiency criteria established by the scientific community, such as: number of constraints checks, amount of propagation, CPU time, or amount of pruning. Furthermore, we introduce a hybrid normalization algorithm, which calculates the cost of the normalization process required to apply the techniques that have been published in the literature.

Regarding search techniques, we present two algorithms: a general purpose heuristic search algorithm and a complete domain dependent search algorithm. Both algorithms take benefit from the results given by the developed 2-consistency techniques.

Additionally, since many real problems can be modeled naturally by using non-binary constraints, in this thesis we propose a modeling language that combines CSPs with non-binary constraints and POCL planning for planning and scheduling problems. The proposed modeling language enables to encode complex constraints, to represent the continuous use of resources and to benefit from the consistency techniques developed in this thesis.

All the presented techniques have been empirically evaluated on different random instances and benchmarks. They have also been applied to solve the railway scheduling problem.