Dynamic Programming Solution of Sequencing Problems with Precedence Constraints

TLDR

Tasks are partially ordered by precedence constraints, and a subset is feasible only if it contains all predecessors of its tasks. The study proposes methods to enumerate all feasible subsets and to assign each subset a computable label for efficient storage. The authors develop a dynamic programming approach that enumerates feasible subsets and assigns each a computable label serving as a physical address for data storage. The resulting algorithm enables a compact dynamic programming solution for one‑machine sequencing with precedence constraints and outperforms prior methods on selected problems.

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.