Single Machine Scheduling with Precedence Constraints of Dimension 2
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.
- Single Machine Scheduling with Series-Parallel Precedence Constraints
- scientific article; zbMATH DE number 5605136
- Approximating Precedence-Constrained Single Machine Scheduling by Coloring
- Scheduling with Precedence Constraints of Low Fractional Dimension
- Scheduling partially ordered jobs faster than \(2^n\)
- Single machine precedence constrained scheduling is a Vertex cover problem
- A compact labelling scheme for series-parallel graphs
- An algorithm to generate the ideals of a partial order
- On the computational complexity of the order polynomial
- Transitive closure for restricted classes of partial orders
- On estimating the number of order ideals in partial orders, with some applications
- The use of dynamic programming in genetic algorithms for permutation problems
- Understanding the generalized median stable matchings
- Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- Algorithmic combinatorics based on slicing posets
- Scheduling partially ordered jobs faster than \(2^{n }\)
- The minimum dummy task problem
- Single Machine Scheduling with Series-Parallel Precedence Constraints
- scientific article; zbMATH DE number 1305426 (Why is no real title available?)
- On the complexity of dynamic programming for sequencing problems with precedence constraints
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)