Sequential open-loop scheduling strategies

R.R. Weber and P. Nash, In M.A.H. Dempster, J.K. Lenstra, and A.H.G. Rinnooy Kan, editors, Deterministic and Stochastic Scheduling pages 385-398. Reidel, 1982.


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