Les satellites de télécommunications multifaisceaux ont la particularité de proposer des couvertures à partir d'une pluralité de faisceaux étroits qui permettent de profiter de meilleurs gains antenne et de la possibilité de réutiliser la ressource fréquentielle qui est chère et donc limitée. Le placement des différents faisceaux sur la zone à couvrir est un problème complexe qui doit être résolu sous différentes contraintes technologiques liées à l'architecture des antennes, tout en optimisant plusieurs critères liés au coût du satellite et à la mission télécom à assurer. La discrétisation de l'espace continu des possibles pour les centres de ces faisceaux positionne le problème dans le monde de l'optimisation combinatoire. Le lien avec le problème du k-centre métrique et une modélisation faisant appel à la théorie des graphes seront présentés. Cette dernière permet d'interpréter le problème comme étant celui de la recherche d'un sous-graphe 4-colorable optimal au sens d'une certaine fonction objectif. L'heuristique de résolution proposée construit la solution faisceau par faisceau selon une approche gloutonne multi-start randomisée. Pour chaque nouveau faisceau "difficile" en termes de coloration, une heuristique de réparation faisant appel à un recuit simulé est appliquée.