Partially Informed Depth-First Search for the Job Shop Problem

Authors

  • Carlos Mencía University of Oviedo
  • María Sierra University of Oviedo
  • Ramiro Varela University of Oviedo

DOI:

https://doi.org/10.1609/icaps.v20i1.13407

Keywords:

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

Abstract

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.

Downloads

Published

2021-05-25

How to Cite

Mencía, C., Sierra, M., & Varela, R. (2021). Partially Informed Depth-First Search for the Job Shop Problem. Proceedings of the International Conference on Automated Planning and Scheduling, 20(1), 113-120. https://doi.org/10.1609/icaps.v20i1.13407