Modélisation et définition du problème

Soit un ensemble de $n$ tâches noté $\mathcal{T}= \lbrace T_{1},\ldots,T_{n} \rbrace$, un ensemble $\mathcal{B} = \lbrace b_{1}, \ldots, b_{ \vert \mathcal{B} \vert} \rbrace$ de buffers fonctionnant de façon analogue à des fifos. Chaque buffer $b_{k}$ est défini par un couple de tâches $(T_{i}, T_{j})$ où $T_{i}$ (resp. $T_{j}$) est la tâche en écriture (resp. en lecture) sur $b_{k}$. L'ensemble des buffers de $T_{i}$ vers $T_{j}$ est représenté par $\mathcal{B}_{ij}$.

Chaque tâche $T_{i}$ se décompose en $n_{i}$ opérations séquentielles notées $\mathcal{O}_{i} = \lbrace o_{i}^{1},\ldots, o_{i}^{n_{i}} \rbrace$, on définit de même : $\mathcal{O} = \bigcup_{i=1}^{n}\mathcal{O}_{i}$. A chaque opération $o_{i}^{p}$ est associé un buffer noté $b(o_{i}^{p})$. Si $o_{i}^{p}$ est une opération d'écriture sur $b(o_{i}^{p})$, alors $b(o_{i}^{p})\in\bigcup_{j\in\lbrace 1, \ldots, n\rbrace}\mathcal{B}_{ij}$, dans le cas où $o_{i}^{p}$ lit des données dans $b(o_{i}^{p})$, alors $b(o_{i}^{p})\in\bigcup_{j\in\lbrace 1, \ldots, n\rbrace}\mathcal{B}_{ji}$.

On appellera le poids du buffer $b$ la surface $w_{b}$ à laquelle la donnée élémentaire stockée par $b$ est proportionnelle, c'est-à-dire la surface que prend (resp. libère) chaque écriture (resp. lecture) dans $b$. La capacité d'un buffer $b$ est le nombre maximal de données pouvant y être stockées simultanément, on note $\Delta$ l'application de $\mathcal{B}$ dans $\mbox{I\hspace{-.15em}N}$ qui à chaque buffer associe une dimension à lui attribuer. Les variables de décision du problème sont formées par l'ensemble { $\Delta(b) \mid b\in\mathcal{B}$}.

Si les buffers sont de dimensions insuffisantes, des tentatives d'écriture y seront impossibles; Des échecs de la sorte en cascade (ou plutôt en boucle) peuvent entraîner le blocage complet du système. Comme chaque buffer occupe une surface proportionnelle à $w_{b}\Delta(b)$, il devient nécessaire de trouver une application $\Delta$ permettant de minimiser la surface occupée par les buffers.

La fonction objectif est donc $\mathcal{C}_{\Sigma} = \sum_{b\in\mathcal{B}}w_{b}\Delta(b)$. Le but étant de minimiser $\mathcal{C}_{\Sigma}$ tout en assurant qu'aucun inter-blocage ne peut survenir.