Improving heuristic estimations with constraint propagation in searching for optimal schedules

Abstract

We face the Job Shop Scheduling Problem by means of branch and bound and A ∗ search. Our main contribution is a new method, based on constraint propagation rules, that allows improving the heuristic estimations. We report results from an experimental study across conventional instances with different sizes showing that A ∗ takes profit from the improved estimations. Both algorithms can reach optimal solutions for medium size instances and, in this case, the branch and bound algorithm is better than A ∗ . However, for very large instances that remain unsolved in both cases, A ∗ returns much better lower bounds due to the improved estimation