Optimal Factory Scheduling using Stochastic Dominance A*
  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.
