Single Machine Scheduling with Precedence Constraints of Dimension 2

Consider the set of tasks that are partially 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 a dynamic programming solution to the problem, when the constraining partial order has a dimension ≤2. This is done by definining a “compact” labeling scheme and an efficient enumerative procedure for all the feasible subsets. In this process a new characterization is given for 2-dimensional partial orders.