AAAI Publications, Twentieth International Conference on Automated Planning and Scheduling

Font Size: 
Partially Informed Depth-First Search for the Job Shop Problem
Carlos Mencía, María R. Sierra, Ramiro Varela

Last modified: 2010-04-20


We propose a partially informed depth-first search algorithm to cope with the Job Shop Scheduling Problem with makespan minimization. The algorithm is built from the well-known P. Brucker's branch and bound algorithm. We improved the heuristic estimation of Brucker's algorithm by means of constraint propagation rules and so devised a more informed heuristic which is proved to be monotonic. We conducted an experimental study across medium and large instances. The results show that the proposed algorithm reaches optimal solutions for medium instances taking less time than branch and bound and that for large instances it reaches much better lower and upper bounds when both algorithms are given the same amount of time.


heuristic search; depth-first; branch and bound; scheduling; job shop; constraint propagation; heuristics; artificial intelligence

Full Text: PDF