Abstract FR:

Le probleme de placement de taches dans un systeme distribue sans contraintes de capacite sur les processeurs et avec couts de communication uniformes est etudie en detail, et deux nouveaux algorithmes approches avec garanties de performance sont proposes pour sa resolution. Le premier est fonde sur la notion de coupe isolante dans un graphe de stone, alors que le deuxieme utilise la programmation lineaire continue. Pour le probleme plus general avec contraintes de capacite, il est demontre pour plusieurs variantes qu'aucun algorithme s'executant en temps polynomial ne peut presenter de garanties de performance sans que p=np. Deuxiemement, une nouvelle methode generale de construction d'algorithmes epsilon-approches pour les problemes de maximisation quadratiques en 0-1 soumis a des contraintes lineaires est exposee. Elle est fondee sur l'utilisation de la programmation lineaire continue, et est appliquee avec succes a plusieurs problemes classiques de l'optimisation combinatoire (maximisation d'une posiforme quadratique sans contraintes, un probleme de placement ne comportant que des gains, k-max-cut, k-cluster pour les graphes bipartis, et la bipartition d'un graphe). Enfin, deux nouvelles heuristiques pour la resolution des programmes quadratiques continus soumis a des contraintes lineaires sont proposees. Leur principe commun est une reduction de la fonction quadratique initiale en fonctions lineaires par fixation alternee de groupes de variables. En utilisant la relaxation continue du programme quadratique en 0-1 associe au probleme de placement de taches dans un systeme distribue, deux algorithmes performants ont ete obtenus. Les tests comparatifs effectues avec le recuit simule montrent que nos heuristiques sont beaucoup plus rapides et fournissent des resultats d'aussi bonne qualite