Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks

Abstract

We discuss the dynamic programming approach to finding an optimal sequence of a set of tasks when the tasks are related by precedence restrictions. We describe how to use this approach in problems where no explicit precedence relations exist. Computer implementation considerations played an important role in its development. Computational results indicate that, when the curse of dimensionality can be dispelled, dynamic programming can be a useful procedure for large sequencing problems.