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
Abstract
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
(www.aaai.org). All rights reserved.
Full paper in Postscript