---
title: "Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems"
authors:
  - "Andrea Schaerf"
doi: ""
url: "https://ijcai.org/proceedings/1997/181"
pdf: "https://ijcai.org/proceedings/1997/0181.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "1254-1258"
track: "Planning and Scheduling"
keywords:
---

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

Andrea Schaerf

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1254-1258.

## Abstract

We propose a solution technique for scheduling and constraint satisfaction problems th at combines backtracking-free constructive methods and local search techniques. Our technique incrementally constructs the solution, performing 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 solution, a look-ahead factor, and (for optimization problems) a lower bound of the objective function. In order to improve search effectiveness, we make use of an adaptive relaxation of constraints and an interleaving of different lookahead factors . The new technique has been successfully experimented on two real-life problems: university course scheduling and sport tournament scheduling.