Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Planning and Scheduling. 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.
@inproceedings{ijcai1997p181,
title = {Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems},
author = {Schaerf, Andrea},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1254--1258},
year = {1997},
note = {Planning and Scheduling},
url = {https://ijcai.org/proceedings/1997/181},
}
TY - CPAPER TI - Combining Local Search and Look-Ahead for Scheduling and Constraint Satisfaction Problems AU - Schaerf, Andrea T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1254 EP - 1258 UR - https://ijcai.org/proceedings/1997/181 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
