For certain scheduling problems with pre-emptive processing, a dynamic programming formulation reduces the problem to a sequence of deterministic optimal control problems. Simple necessary and sufficient optimality conditions for these deterministic problems are obtainable from the standard results of optimal control theory, and sometimes lead to analytic solutions. Where this does not happen, then as with many dynamic programming formulations, computational solution is possible in principle, but infeasible in practice. After a survey of this approach to scheduling problems, this paper discusses a simplification of the method which leads to computationally tractable problems, which can be expected to yield good, though sub-optimal, scheduling strategies. This new approach is based on the notion of sequential open-loop control, sometimes used in control engineering to solve stochastic control problems by deterministic means, and is not base don dynamic programming.
back to list of papers