Improving heuristic search algorithms by means of pruning by dominance. Application to scheduling problems

Article type: Other

Authors: Sierra, María R.

Affiliations: Computing Technologies Group, Department of Computing, University of Oviedo, Campus of Viesques, 33271 Gijón, Spain. E-mail: sierramaria@uniovi.es

Abstract: In this dissertation, we face the Job Shop Scheduling problem by means of state space heuristic search. Our goal was devising new algorithms to reach either optimal schedules for moderate size instances or sub-optimal schedules for larger ones. We considered two different objective functions, designed new heuristics estimations and studied the formal properties of them. The main contribution is the formulation of an efficient pruning method based on dominance relations among states of the search space. This method reduces drastically the effective search space and can be adapted in principle to any regular objective function. The experimental study shows that the proposed method is quite competitive with other state-of-the-art methods in reaching both optimal and sub-optimal schedules.

Keywords: Job shop scheduling, heuristic search, pruning by dominance, best first search

DOI: 10.3233/AIC-130562

Journal: AI Communications, vol. 26, no. 3, pp. 323-324, 2013