Programmation linéaire en nombres entiers pour l'ordonnancement cyclique sous contraintes de ressources

Un probleme d'ordonnancement cyclique consiste a ordonner dans le temps l'execution repetitive d'un ensemble d'operations liees par des contraintes de precedence, en utilisant un nombre limite de ressources. Ces problemes ont des applications immediates dans les systemes de production ou en informatique parallele. Particulierement, ils permettent de modeliser l'ensemble des contraintes de precedence et de ressource a prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une operation represente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel designe une methode efficace pour l'optimisation de boucles qui permet la realisation en parallele des operations des differentes iterations de la boucle. Dans cette these, nous nous interessons principalement au probleme d'ordonnancement periodique qui est un cas particulier de l'ordonnancement cyclique et qui est egalement la base du pipeline logiciel. Le terme ordonnancement modulo designe un ordonnancement periodique tel que l'allocation de ressources pour une operation donnee n'est pas modifiee d'une iteration sur l'autre. Pour resoudre le probleme, nous nous interessons aux formulations de programmation lineaire en nombres entiers, et notamment a la resolution du probleme par des techniques de separation, evaluation, generation de colonnes, relaxation lagrangienne et des methodes hybrides. En particulier, nous proposons des nouvelles formulations basees sur des variables binaires representant l'execution d'ensembles d'instructions en parallele. Enfin, les methodes developpees ont ete validees sur des jeux d'instances industrielles pour des processeurs de type VLIW. Un probleme d'ordonnancement cyclique consiste a ordonner dans le temps l'execution repetitive d'un ensemble d'operations liees par des contraintes de precedence, en utilisant un nombre limite de ressources. Ces problemes ont des applications immediates dans les systemes de production ou en informatique parallele. Particulierement, ils permettent de modeliser l'ensemble des contraintes de precedence et de ressource a prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une operation represente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel designe une methode efficace pour l'optimisation de boucles qui permet la realisation en parallele des operations des differentes iterations de la boucle. Dans cette these, nous nous interessons principalement au probleme d'ordonnancement periodique qui est un cas particulier de l'ordonnancement cyclique et qui est egalement la base du pipeline logiciel. Le terme ordonnancement modulo designe un ordonnancement periodique tel que l'allocation de ressources pour une operation donnee n'est pas modifiee d'une iteration sur l'autre. Pour resoudre le probleme, nous nous interessons aux formulations de programmation lineaire en nombres entiers, et notamment a la resolution du probleme par des techniques de separation, evaluation, generation de colonnes, relaxation lagrangienne et des methodes hybrides. En particulier, nous proposons des nouvelles formulations basees sur des variables binaires representant l'execution d'ensembles d'instructions en parallele. Enfin, les methodes developpees ont ete validees sur des jeux d'instances industrielles pour des processeurs de type VLIW.