To appear in Proceedings 14th National Conference on Artificial Intelligence

Stochastic Procedures for Generating Feasible Schedules

Angelo Oddi and Stephen F. Smith

The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA


In this paper, we investigate the use of stochastic variable and value ordering heuristics for solving job shop scheduling problems with non-relaxable deadlines and complex metric constraints. Previous research in constraint satisfaction scheduling has developed highly effective, deterministic heuristics for this class of problems based on simple measures of temporal sequencing flexibility. However, they are not infallible, and the possibility of search failure raises the issue of how to most productively enlarge the search. Backtracking is one alternative, but such systematicity generally implies high computational cost. We instead design an iterative sampling procedure, based on the intuition that it is more productive to deviate from heuristic advice in cases where the heuristic is less informed, and likewise better to follow the heuristic in cases where it is more knowledgeable. We specify stochastic counterparts to previously developed search heuristics, which are parameterized to calibrate degree of randomness to level of discriminatory power. Experimental results on job shop scheduling CSPs of increasing size demonstrate comparative advantage over chronological backtracking. Comparison is also made to another, recently proposed iterative sampling technique called heuristic-biased stochastic sampling (HBSS). Whereas HBSS assumes a statically specified heuristic bias that is utilized at every application of the heuristic, our approach defines bias dynamically according to how well the heuristic discriminates alternatives.
The work described in this paper was sponsored in part by the Advanced Research Projects Agency and Rome Laboratory, Air Force Material Command, USAF, under grant number F30602-95-1-0018 and the CMU Robotics Institute. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Advanced Research Projects Agency and Rome Laboratory or the U.S. Government.

Angelo Oddi's work was also supported by Agenzia Spaziale Italiana (ASI), CNR Committee 12 on Information Technology (Project SARI), CNR Committee 04 on Biology and Medicine, and Ministero dell'Universita' e della Ricerca Scientifica e Tecnologica (MURST). He is currently supported by a scholarship from CNR Committee 12 on Information Technology.

Copyright 1997, American Association for Artificial Intelligence ( All rights reserved.
Full paper in Postscript