Single Machine Scheduling with Precedence Constraints of Dimension 2 (Q3329201)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3860869
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Single Machine Scheduling with Precedence Constraints of Dimension 2 |
scientific article; zbMATH DE number 3860869 |
Statements
Single Machine Scheduling with Precedence Constraints of Dimension 2 (English)
0 references
1984
0 references
precedence constraints
0 references
acyclic directed graph
0 references
feasible sequence
0 references
partial order dimension
0 references
0.875373363494873
0 references
0.818822979927063
0 references
0.8167842626571655
0 references
0.8006224036216736
0 references
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.
0 references