Carnegie Mellon University
Stochastic Procedures for Generating Feasible Schedules

A. Oddi and Stephen Smith
Proceedings 14th National Conference on Artificial Intelligence, July, 1997.

  • Adobe portable document format (pdf) (152KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Text Reference
A. Oddi and Stephen Smith, "Stochastic Procedures for Generating Feasible Schedules," Proceedings 14th National Conference on Artificial Intelligence, July, 1997.

BibTeX Reference
   author = "A. Oddi and Stephen Smith",
   title = "Stochastic Procedures for Generating Feasible Schedules",
   booktitle = "Proceedings 14th National Conference on Artificial Intelligence",
   month = "July",
   year = "1997",