Abstract FR:

La technique du recuit simule est une methode stochastique qui permet la resolution de problemes d'optimisation complexes. Malheureusement, cette methode demande souvent un temps de calcul important. La parallelisation de l'algorithme de recuit simule a permis de remedier a ce probleme. Cependant, les algorithmes paralleles proposes sont tres dependants du probleme a resoudre et des qu'une nouvelle application se presente le choix de l'algorithme parallele puis de son adaptation se pose. Pour pallier cet inconvenient, nous avons generalise divers algorithmes paralleles de recuit simule en vue de les rendre independants du probleme d'optimisation traite. Dans une premiere phase, nous avons defini un probleme test, qui a permis une etude comparative de divers algorithmes paralleles. Nous avons degage des proprietes generales concernant les temps de calcul et la qualite des solutions obtenues. Nous avons etabli des modeles de temps de calcul pour chaque algorithme implante. L'implantation des algorithmes a ete realisee sur un reseau de transputers.