Single Machine Scheduling with Precedence Constraints of Dimension 2

From MaRDI portal





The set V of n tasks has to be processed by one machine. The possible processing sequences are restricted by precedence constraints represented by a given acyclic directed graph \(G=(V,A)\). In any feasible sequence a task i may not be processed until the processing of all its predecessors has been finished. Each task \(i\in V\) has a given processing time c(i) and a (nondecreasing in t) cost function g(i,t)\(\geq 0\) where t is the termination time of processing i. The objective is to find a feasible sequence for which the total cost is minimal. When the partial order represented by the graph G has dimension \(\leq 2\), a dynamic programming algorithm requiring O(Kn) time and O(K) space is presented, where K is the number of feasible subsets of the graph G. A subset \(S\subseteq V\) is called feasible if for every \(i\in S\) all the predecessors of i are also in S. The dimension of a partial order P is the minimum of total orders such that their intersection (as binary relations) is P. The algorithm uses the Baker-Schrage labeling scheme and the compactness property of the labels. It is proved that the labeling scheme has the compactness property iff the partial order dimension is less or equal to two.











This page was built for publication: Single Machine Scheduling with Precedence Constraints of Dimension 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3329201)