Buffer plein/Buffer vide

Figure 3.4: Inter-blocage plein/vide

Figure 3.5: Déblocage plein/vide

Comme l'un des deux arcs est issu d'une contrainte de buffer plein $b_{1}$ (figure 3.4), il est possible de le déplacer en modifiant $\Delta(b_{1})$. $\Delta(b_{1})$ a été fixé dans cet exemple à 1, mais nous utiliserons directement l'expression $\Delta(b_{1})$ pour désigner la capacité actuelle de $b_{1}$, et $\Delta^{*}(b_{1})$ pour désigner la nouvelle capacité de $b_{1}$, c'est-à-dire celle qui brisera le circuit.

On voit (figure 3.5) que $N(o_{1}^{p}) = N(o_{2}^{t}) + \Delta(b_{1})$, on cherche le plus petit $r > q$ tel que $b(o_{1}^{p}) = b(o_{1}^{r})$, et on fixe :

$$\Delta^{*}(b_{1}) = \Delta(b_{1}) + N(o_{1}^{r}) - N(o_{1}^{p})$$

On obtiendra ainsi un arc $(o_{2}^{t}, o_{1}^{r})$, on remarque au passage que la relation

$$N(o_{1}^{p}) = N(o_{2}^{t}) + \Delta(b_{1})$$

$$\iff 0 = N(o_{2}^{t}) + \Delta(b_{1}) - N(o_{1}^{p})$$

$$\iff N(o_{1}^{r}) = N(o_{2}^{t}) + \Delta(b_{1}) + N(o_{1}^{r}) - N(o_{1}^{p})$$

$$\iff N(o_{1}^{r}) = N(o_{2}^{t}) + \Delta^{*}(b_{1})$$

est vérifiée.

Notons toutefois que la notation $\Delta (b)$ est ambiguë, il convient de faire la distinction entre les capacités dont on se sert pour tracer le graphe, et les variables de décision. Nous utiliserons dorénavant des variables $x$ ou $y$ pour définir l'ensemble $\mathcal{E}_{3}$ des contraintes dépendantes des buffers. Nous garderons la notation $\Delta$ pour désigner les valeurs des variables de décision.