Pruning by dominance in best-first search: a case study in job shop scheduling with makespan minimization

Autores: María Rita Sierra Sánchez , José Ramiro Varela Arias
Localización: XII Conferencia de la Asociación Española para la Inteligencia Artificial: (CAEPIA 2007). Actas / coord. por Daniel Borrajo Millán , Luis Castillo Vidal , Juan Manuel Corchado Rodríguez , Vol. 2, 2007, ISBN 978-84-611-8848-2, págs. 289-298
Idioma: inglés
Texto completo no disponible (Saber más ...)
Resumen
- Best-First search is a problem solving paradigm that allows designing exact of admissible algorithms. One of its main drawbacks is that it requires keeping a lot of visited states, so as it is very memory and time consuming. In order to alleviate this problem, a number of techniques are of common use, such us reducing the search space by means of constraint propagation or pruning states from tight lower and upper bounds calculated during the search. In this paper, we propose a complementary method, based on dominance relations among states, for reducing the search space and apply it to the Job Shop Scheduling Problem. We report results from an experimental study showing that the proposed method is able to reduce both the effective search space and the computation time.