Pour certaines missions de télécommunications, il est nécéssaire de savoir couvrir totalement une zone subdivisée en sous-régions, chacunes ayant des demandes spécifiques. Une solution est de regrouper ces sous-régions dans différentes faisceaux. Ces faisceaux doivent ensuite être attribués à un type d'équipement antennaire particulier qui ne peut être embarqué à bord qu'en faible nombre : les réflecteurs. Cette atribution se fait sous contraintes : selon la taille des faisceaux qui dépend des sous-régions qu'ils couvrent, deux faisceaux proches ne peuvent être alloués au même réflecteur : il s'agit là de contraintes binaires de coloration de graphe. Nous nous retrouvons avec un problème de clustering (regroupement de sous-régions) et de coloration de graphe, qui est complexe pour deux raisons principales. Premièrement, on cherche à résoudre ce problème pour des centaines de sous-régions, ce qui implique une grande combinatoire. La deuxième raison est que les arêtes de notre graphe dépendent du regroupement de sous-régions en faisceaux choisi. On propose une approche matheuristique et une heuristique inspiré de la méhode ILS pour résoudre ce problème.