Dynamic Programming Solution of Sequencing Problems with Precedence Constraints

Abstract

Consider a set of tasks that are partially ordered by precedence constraints. A subset of tasks is called feasible if, for every task in the subset, all predecessors are also in the subset. The major results are (1) a method for enumerating all feasible subsets and (2) a method for assigning to each feasible subset an easily computed label that can be used as a physical address for storing information about the subset. These two results permit a very compact computer implementation of a dynamic programming algorithm for solving one-machine sequencing problems with precedence constraints. This algorithm appears to be much more efficient than previous ones for certain one-machine sequencing problems.