Single machine scheduling with precedence constraints of dimension 2

Abstract

<p>Consider the set of tasks that are partiallv ordered by precedence constraints. The tasks are to be sequenced so that a given objective function will assume its optimal value over the set of feasible solutions. A subset of tasks is called feasible, if for every task in the subset, all of its predecessors are also in the subset. We present an efficient dynamic proqramminq solution to the problem, when the constraining Partial order has a dimension < 2. This is done by defining a "compact" labelinq scheme and a very efficient enumerative procedure for all the feasible subsets. In this process a new characterization is qiven for 2-dimensional partial orders.</p>