Title: Pruning search spaces by dominance rules: a case study in the job shop scheduling

Authors: Maria R. Sierra, Ramiro Varela

Addresses: Department of Computing, University of Oviedo, Campus of Viesques, 33271 Gijon, Spain. ' Department of Computing, Artificial Intelligence Center, University of Oviedo, Campus of Viesques, 33271 Gijon, Spain

Abstract: In this paper, we propose a pruning method based on dominance relations among states for reducing the search space in best-first search. We apply this method to an A* algorithm that explores the space of active schedules for the job shop scheduling problem with makespan minimisation. We conducted an experimental study over conventional benchmarks. The results show that the proposed method is able to reduce both the space and the time in searching for optimal schedules and that it outperforms other approach taken from the literature.

Keywords: job shop scheduling; heuristic search; best first search; pruning by dominance; search spaces; makespan minimisation; optimisation; dominance rules.

DOI: 10.1504/IJRIS.2010.029814

International Journal of Reasoning-based Intelligent Systems, 2010 Vol.2 No.1, pp.51 - 59

Published online: 02 Dec 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article