Le travail présenté dans cette thèse traite des problèmes d'affectation de fréquences (FAP) qui se produisent dans les systèmes de communication par satellite utilisant la technologie SDMA. Ces systèmes se composent d'un satellite et d'une zone de service de taille fixe dans laquelle sont répartis des utilisateurs. L'objectif est alors de servir un maximum d'utilisateur en fréquence dans cette zone de service. Cependant, l'affectation ne doit pas violer les contraintes d'interférence qui apparaissent lorsque deux utilisateurs utilisent une même fréquence ou lorsqu'ils se partagent une même plage de fréquence. Deux types d'interférences sont considérés dans cette étude : les interférences binaire et cumulative. Pour chacune d'elles, les problèmes d'affectation de fréquence de type mono-porteuse (une fréquence par utilisateur) et multi-porteuses (plusieurs fréquences par utilisateur) sont traités. Le problème de l'affectation bidimensionnelle est aussi abordé et nous proposons des modèles de Programmation Linéaire en Nombre Entiers (PLNE) pour le résoudre. Au niveau des méthodes de résolution, nous utilisons des algorithmes gloutons, des modèles de PLNE pour le problème de type mono-porteuse. En outre, un algorithme de déplacement continu de faisceau est conçu pour améliorer les solutions en résolvant un problème d'optimisation continu non linéaire. Concernant le problème de type multi-porteuses, nous le ramenons à un problème d'ordonnancement et celui-ci est résolu à l'aide de la PLNE et la Programmation Par Contraintes (PPC). Il est par ailleurs montré que les résultats issus de la PPC sont meilleurs que ceux de la PLNE. De plus, en transformant les interférences cumulatives en interférences binaires, la méthode d'ordonnancement avec les contraintes induites par les cliques donne de bien meilleurs résultats. Nous considérons également un problème industriel dans lequel de nombreuses contraintes apparaissent ce qui rend le problème très complexe et insoluble avec des méthodes exactes. Face à ce constat, deux algorithmes gloutons sont réalisés et leurs résultats sont comparés.

Le problème de planification de réseaux WLAN consiste d'une part à positionner et à paramétrer des antennes dans un bâtiment et d'autre part à leur affecter une fréquence afin d'offrir aux clients un accès sans fil au réseau local. Le réseau ainsi construit doit répondre à des critères de couverture et de qualité de service, tout en minimisant le coût financier.<br /><br />Notre modélisation est basée sur le calcul du débit réel offert en chaque point de demande de service du réseau. Nous montrons que ce critère de débit réel permet une modélisation complète de la qualité de service car il unifie les critères habituels de couverture, de gestion des interférences et de capacité.<br /><br />Notre optimisation traite simultanément le problème de placement des points d'accès et le problème d'affectation de fréquences par un algorithme à Voisinages Variables Aléatoires VVA : à chaque itération de cette recherche locale le type de voisinage est tiré au hasard. Cet algorithme est très modulaire et permet facilement de combiner les deux sous problèmes (placement et affection).<br /><br />Ces travaux ont donné lieu à des collaborations et partenariats industriels : logiciel de planification globale des WLAN avec Orange Labs et solutions de planification séquentielle avec la start-up Trinaps.<br /><br />Enfin nous approfondissons la modélisation du problème en explicitant les liens entre le calcul du débit réel et les SINR. Dans une première étape, nous montrons que les contraintes de seuil sur les SINR induisent un problème de T-coloration de graphe (condition nécessaire). Pour obtenir une équivalence rendant compte des interférences multiples, une généralisation du problème de T-coloration pour les hypergraphes est introduite. Dans une seconde étape, nous définissons un algorithme déduisant les seuils de SINR à partir des contraintes sur les débits réels. Cette nouvelle modélisation est la base de nos développements futurs.