Proceedings:
Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling
Volume
Issue:
Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling
Track:
Full Technical Papers
Downloads:
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.
DOI:
10.1609/icaps.v20i1.13407
ICAPS
Vol. 20 (2010): Twentieth International Conference on Automated Planning and Scheduling