Le problème de la recherche d'un élément dans un ensemble donne est un des problèmes fondamentaux en informatique non numérique, lie, par exemple, aux bases de données, a la compilation, a l'optimisation combinatoire, etc... Dans cette thèse nous abordons le problème de la recherche dans des ensembles ordonnes et quelques problèmes qui lui sont lies. Une matrice est dite triée si elle possédé une relation d'ordre total sur chaque ligne et chaque colonne. Un cas particulier est l'ensemble des matrices définies par x+y, la somme cartésienne de deux vecteurs tries. Après un tour d'horizon des problèmes de la sélection, de la recherche et du tri sur des ensembles de la forme x=y, nous démontrons des bornes inférieures et introduisons des bornes supérieures pour les problèmes de la recherche et de la sélection. Nous proposons, en outre, plusieurs algorithmes parallèles pour la recherche dans x+y. Ensuite nous montrons comment appliquer ces résultats a la resolution en parallèle du problème de décision du sac-a-dos, ou, étant donnes plusieurs objets et un sac de capacité définie a remplir, on veut décider s'il existe une combinaison des objets qui remplit exactement le sac. Des algorithmes avec une accélération optimale sont introduits pour divers modèles de machines parallèles a mémoire partagée et distribuée. Pour ce problème les approches existantes se ramènent soit a la recherche dans x+y, soit a la traversée d'un espace combinatoire a l'aide de la technique du Branch & Bound. Cette dernière technique est aussi discutée dans ce travail, ou nous présentons un algorithme de Branch & Bound en vue de la resolution de problèmes d'optimisation combinatoire sur la connexion machine. Enfin, toujours dans le domaine de l'optimisation combinatoire, nous étudions le comportement de l'algorithme de recuit simule. Nous prouvons que, malgré la confiance qu'il inspire et sa grande utilisation pour des application

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne. / .Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.