Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Optimal Factory Scheduling using Stochastic Dominance A*
Peter Wurman, Michael Wellman
Abstract:
We examine a standard factory scheduling problem with stochastic processing and setup times, minimizing the expectation of the weighted number of tardy jobs. Because the costs of operators in the schedule are stochastic and sequence dependent, standard dynamic programming algorithms such as A* may fail to find the optimal schedule. The SDA* (Stochastic Dominance A*) algorithm remedies this difficulty by relaxing the pruning condition. We present an improved state-space search formulation for these problems and discuss the conditions under which stochastic scheduling problems can be solved optimally using SDA*. In empirical testing on randomly generated problems, we found that in 70%, the expected cost of the optimal stochastic solution is lower than that of the solution derived using a deterministic approximation, with comparable search effort.
Keywords: Scheduling, search under uncertainty, stochastic dominance, A*.
Pages: 554-563
PS Link: ftp://ftp.eecs.umich.edu/people/wellman/uai96wurman.ps.Z
PDF Link: /papers/96/p554-wurman.pdf
BibTex:
@INPROCEEDINGS{Wurman96,
AUTHOR = "Peter Wurman and Michael Wellman",
TITLE = "Optimal Factory Scheduling using Stochastic Dominance A*",
BOOKTITLE = "Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1996",
PAGES = "554--563"
}


hosted by DSL   •   site info   •   help