Pruning search space by dominance rules in best first search for the job shop scheduling problem

Abstract

In this paper, we propose a pruning method, based on dominance relations among states, for reducing the search space in best-¯rst search. We apply this method to an A* algorithm that explores the space of active schedules for the Job Shop Scheduling Problem with makespan minimization. We conducted an experimental study over conventional benchmarks. The results show that the proposed method is able to re- duce both the space and the time in searching for optimal schedules and that it outperforms other approach taken from the literature