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.