Over-Constrained Scheduling using Dynamic Programming

In this paper, we demonstrate the use of stochastic dynamic programming to solve over-constrained scheduling problems. In particular, we propose a decision method for efficiently calculating, prior to start of execution, the optimal decision for every possible situation encountered in sequential, predictable, over-constrained scheduling domains. We present our results using an example problem from Product Quality Planning.