Abstract FR:

Cette thèse traite du problème de la minimisation d'une fonction pseudo-booléenne quadratique (f. P. B. Q. ) sous des contraintes linéaires et de son application au problème de placement de taches sur les systèmes distribues ainsi qu'au problème de partition de graphes. Nous proposons le calcul de plusieurs bornes inférieures. Dans le cas de contraintes linéaires de transport, nous proposons une réduction de la fonction objectif et le calcul d'une borne inférieure par implications logiques. Nous utilisons cette borne inférieure pour la résolution d'un problème de placement de taches avec contraintes de ressources. Nous résolvons des problèmes de l'ordre de 20 taches et 3 processeurs. Dans le cas de contraintes linéaires quelconques, nous calculons une borne inférieure par une décomposition optimale, sous certaines hypothèses, de la fonction objectif. Nous appliquons le calcul de cette borne au problème de placement de taches sans contraintes de ressources. Une étude expérimentale montre la bonne qualité de cette borne: nous obtenons des écarts relatifs, avec la valeur exacte du problème, inférieurs a 2% pour des problèmes comportant 60 taches et 15 processeurs. Nous proposons aussi le calcul d'une borne inférieure pour un problème de partition de graphes. Cette borne est obtenue par un algorithme de coupes polyédriques. Une étude expérimentale montre la bonne qualité de cette borne pour certaines classes de problèmes. Dans le cadre de la minimisation d'une f. P. B. Q. Sous une contrainte linéaire, nous proposons le calcul d'une borne inférieure par un programme linéaire continu. Nous prouvons que cette borne est la meilleure valeur que l'on puisse obtenir sous certaines hypothèses. Ce résultat se situe dans le prolongement des travaux de Hammer, Hansen et Simeone, dans le cas sans contraintes, sur le toit dual. Nous terminons par une étude théorique comparative de ces différentes bornes