Introduction to Scheduling

Section 6.3 presents polynomial-time algorithms to check for well-posedness, make the constraints well-posed with minimal serialization, remove redundant anchors, and find the minimum relative schedule. Section 6.4 analyzes the properties of the algorithms. In particular, we show that the algorithms are guaranteed to yield a minimally serialized, well-posed, minimum schedule, if one exists. Finally, Section 6.5 summarizes the relative scheduling approach. 

For a constraint graph G(V,a weight Uij is associated with each edge (uj, Vj) that is equal to the execution delay of the qjeration t ,-, denoted by (v ). Let us assume first that the weights are known this assumption will be removed in the next section. The scheduling problem may be defined as follows  

Definition 6.1.1 A schedule of a constraint graph G V, E) is an integer labeling cr V from the set of vertices V to non-negative integers Z , such that civj) r(vi) -I- Wij if there is an edge from Vi to Vj with weight Wij. A minimum schedule is a schedule such that ( 7(v,) — r(vo)) is minimum for all Vi V. 

The integer label associated with a vertex v,- represents the time (or equivalently the cycle) with respect to the beginning of the schedule ( r(wo)) in which the operation modeled by may begin execution, i.e. r(v,) is the start 

---