Analyzing iterative incremental scheduling

The iterative incremental scheduling algorithm constructs a minimum relative schedule, or detects the presence of inconsistent timing constraints, with at most i + 1 iterations. This is a very desirable property, since the number of maximum timing constraints i is in general small. The proof follows the outline in [LW83]. Note that in the sequel the full anchor set A(v ) for a valex Vi is used in the computation of the start time and offsets. By Theorem 6.2.4 and Theorem 6.2.6, the result is applicable when the relevant anchor set R vi) or the irredundant anchor set IR(vi) are used instead. 

We consider the effect of iterative application of the iterative incremental scheduling algorithm. For any integer r, r 0, let f = ra(t ,) a G G V denote the offsets after the r call to the IncrementalOffset procedure. Initially, all offsets r (vt) are set to 0. We state the following lemma. 

Proof We will prove by induction. After the first call to procedure IncrementalOffset, the offsets = ri(v,) a G A(v,),Vu,- G V are equal to the longest paths in G/ from the anchors to their successors. In addition, all offsets 0- (1 , ) are greater than or equal to 0. Since G/ is a subgraph of the constraint graph G, the assertion holds for r = 1. 

IncrementalOffset accepts these readjusted offsets as input, and finds the offsets 1 + = r + (v,) a G G V such that, for every anchor 

This means that La is the least number such that, for any vertex r G V(a), any of the longest weighted paths from a-to-u has no more than L a backward edges. Furthermore, define L as 

---

We analyze in this section properties of the algorithms presented in Section 6.3. We prove first the makeWellposed algorithm can minimally serialize an ill-posed constraint graph in attempt to make it well-posed, if a well-posed solution exists. We then prove the iterative incremental scheduling algorithm can construct a minimum relative schedule, if one exists, in polynomial time. 

---