Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems

Abstract

We propose a solution technique for schedul-ing and constraint satisfaction problems that combines backtracking-free constructive meth-ods and local search techniques. Our technique incrementally constructs the solution, perform-ing a local search on partial solutions each time the construction reaches a dead-end. Local search on the space of partial solutions is guided by a cost function based on three components: the distance to feasibility of the partial solu-tion, a look-ahead factor, and (for optimization problems) a lower bound of the objective func-tion. In order to improve search eectiveness, we make use of an adaptive relaxation of con-straints and an interleaving of dierent look-ahead factors. The new technique has been successfully experimented on two real-life prob-lems: university course scheduling and sport tournament scheduling. 1