Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

Le domaine de l'embarqué connaît depuis quelques années un essor important avec le développement d'applications de plus en plus exigeantes en calcul auxquels les architectures traditionnelles à base de processeurs (mono/multi cœur) ne peuvent pas toujours répondre en termes de performances. Si les architectures multiprocesseurs ou multi cœurs sont aujourd'hui généralisées, il est souvent nécessaire de leur adjoindre des circuits de traitement dédiés, reposant notamment sur des circuits reconfigurables, permettant de répondre à des besoins spécifiques et à des contraintes fortes particulièrement lorsqu'un traitement temps-réel est requis. Ce travail présente l'étude des problèmes d'ordonnancement dans les architectures hétérogènes reconfigurables basées sur des processeurs généraux (CPUs) et des circuits programmables (FPGAs). L'objectif principal est d'exécuter une application présentée sous la forme d'un graphe de précédence sur une architecture hétérogène CPU/FPGA, afin de minimiser le critère de temps d'exécution total ou makespan (Cmax). Dans cette thèse, nous avons considéré deux cas d'étude : un cas d'ordonnancement qui tient compte des délais d'intercommunication entre les unités de calcul CPU et FPGA, pouvant exécuter une seule tâche à la fois, et un autre cas prenant en compte le parallélisme dans le FPGA, qui peut exécuter plusieurs tâches en parallèle tout en respectant la contrainte surfacique. Dans un premier temps, pour le premier cas d'étude, nous proposons deux nouvelles approches d'optimisation, GAA (Genetic Algorithm Approach) et MGAA (Modified Genetic Algorithm Approach), basées sur des algorithmes génétiques. Nous proposons également de tester un algorithme par séparation et évaluation (méthode Branch & Bound). Les approches GAA et MGAA proposées offrent un très bon compromis entre la qualité des solutions obtenues (critère d'optimisation de makespan) et le temps de calcul nécessaire à leur obtention pour résoudre des problèmes à grande échelle, en comparant à la méthode par séparation et évaluation (Branch & Bound) proposée et l'autre méthode exacte proposée dans la littérature. Dans un second temps, pour le second cas d'étude, nous avons proposé et implémenté une méthode basée sur les algorithmes génétiques pour résoudre le problème du partitionnement temporel dans un circuit FPGA en utilisant la reconfiguration dynamique. Cette méthode fournit de bonnes solutions avec des temps de calcul raisonnables. Nous avons ensuite amélioré notre précédente approche MGAA afin d'obtenir une nouvelle approche intitulée MGA (Multithreaded Genetic Algorithm), permettent d'apporter des solutions au problème de partitionnement. De plus, nous avons également proposé un algorithme basé sur le recuit simulé, appelé MSA (Multithreaded Simulated Annealing). Ces deux approches proposées, basées sur les méthodes métaheuristiques, permettent de fournir des solutions approchées dans un intervalle de temps très raisonnable aux problèmes d'ordonnancement et de partitionnement sur système de calcul hétérogène / The domain of the embedded systems becomes more and more attractive in recent years with the development of increasing computationally demanding applications to which the traditional processor-based architectures (either single or multi-core) cannot always respond in terms of performance. While multiprocessor or multicore architectures have now become generalized, it is often necessary to add to them dedicated processing circuits, based in particular on reconfigurable circuits, to meet specific needs and strong constraints, especially when real-time processing is required. This work presents the study of scheduling problems into the reconfigurable heterogeneous architectures based on general processors (CPUs) and programmable circuits (FPGAs). The main objective is to run an application presented in the form of a Data Flow Graph (DFG) on a heterogeneous CPU/FPGA architecture in order to minimize the total running time or makespan criterion (Cmax). In this thesis, we have considered two case studies: a scheduling case taking into account the intercommunication delays and where the FPGA device can perform a single task at a time, and another case taking into account parallelism in the FPGA, which can perform several tasks in parallel while respecting the constraint surface. First, in the first case, we propose two new optimization approaches GAA (Genetic Algorithm Approach) and MGAA (Modified Genetic Algorithm Approach) based on genetic algorithms. We also propose to compare these algorithms to a Branch & Bound method. The proposed approaches (GAA and MGAA) offer a very good compromise between the quality of the solutions obtained (optimization makespan criterion) and the computational time required to perform large-scale problems, unlike to the proposed Branch & Bound and the other exact methods found in the literature. Second, we first implemented an updated method based on genetic algorithms to solve the temporal partitioning problem in an FPGA circuit using dynamic reconfiguration. This method provides good solutions in a reasonable running time. Then, we improved our previous MGAA approach to obtain a new approach called MGA (Multithreaded Genetic Algorithm), which allows us to provide solutions to the partitioning problem. In addition, we have also proposed an algorithm based on simulated annealing, called MSA (Multithreaded Simulated Annealing). These two proposed approaches which are based on metaheuristic methods provide approximate solutions within a reasonable time period to the scheduling and partitioning problems on a heterogeneous computing system

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

Les problèmes d'optimisation spatialisés font intervenir des entités (clients, demandes, trafic) réparties sur une étendue (la donnée) et des dispositifs physiques (antennes, véhicules) qui doivent leur être associés de manière optimale. Il en résulte de nombreux problèmes d'optimisation combinatoire difficile à résoudre (NP-hard). Pour résoudre ce type de problème, nous proposons des algorithmes à structure intermédiaire, des recherches locales et des approches de résolution collective selon des métaphores de systèmes naturels et biologiques. Le but est par exemple de prendre en compte dès le départ la potentialité d'application à des problèmes dynamiques, de fournir un canevas à la mise en œuvre distribuée possible des algorithmes, et de résoudre des problèmes de grandes tailles.

Le cloud computing a émergé au cours de la dernière décennie pour être largement adopté aujourd'hui dans plusieurs domaines de l'informatique. Il consiste à proposer des ressources axées, ou non, sur le marché sous forme de services qui peuvent être consommés de manière souple et transparente. Dans cette thèse, nous traitons le problème d'ordonnancement, un des enjeux majeurs du cloud. Selon la configuration de cloud ciblée, nous avons identifié trois niveaux d'ordonnancement : niveau service, niveau tâche et niveau machine virtuelle. Nous revisitons la modélisation du problème, la conception et l'implémentation des métaheuristiques multiobjectives pour chaque niveau d'ordonnancement du cloud. Les ordonnanceurs à base de métaheuristiques que nous proposons portent sur différents critères notamment la consommation d'énergie, les émissions de gaz à effet de serre, le profit et la qualité du service (coût et temps de réponse). Nous prouvons leur capacité d'adaptation aux contraintes du cloud en les intégrant au sein du gestionnaire de cloud OpenNebula. De plus, nos ordonnanceurs ont été largement expérimentés utilisant des configurations réalistes de cloud sur Grid'5000, en tant qu'infrastructure en tant que service (IAAS), et des scénarios concrets basés sur les instances et les tarifications d'Amazon EC2. Les résultats présentés montrent que les méthodes que nous proposons surpassent les approches l'ordonnancement existantes sur tous les critères cités précédemment.

Dans cette thèse, nous considérons le problème du séquencement sur une ligne de montage multi-modèles de véhicules industriels. Pour équilibrer au mieux la charge dynamique des opérateurs, la minimisation de la somme des retards à l’issue de chaque véhicule est proposée.Deux approches peuvent être utilisées pour optimiser le lissage de charge dans un problème de séquencement : l’utilisation directe des temps opératoires ou le respect de règles. La plupart des travaux appliqués à l’industrie automobile utilisent l’approche de respect de règles. Une originalité de ce travail est d’utiliser l’approche de la prise en compte directe des temps opératoires.L’étude de la littérature de ce problème a dévoilé deux lacunes dans les travaux précédents : l’essentiel des travaux modélisent un seul type d’opérateurs d’une part, et proposent des heuristiques ou des métaheuristiques pour résoudre ces problèmes, d’autre part. L’originalité de ce travail est de tester des méthodes exactes pour des instances industrielles et de modéliser le fonctionnement de trois différents types d’opérateurs spécifiques au cas industriel.Deux méthodes exactes sont développées : la programmation linéaire mixte et la programmation dynamique. Une étude expérimentale des facteurs de complexité sur des instances académiques des deux modèles est développée. Les modèles sont aussi testés sur des instances du cas d’étude.Par ailleurs, le problème est traité par deux méthodes approchées : une heuristique basée sur la programmation dynamique d’une part, et des métaheuristiques (algorithme génétique, recuit simulé et un couplage des deux) d’autre part. Les deux approches sont testées sur des instances académiques et des instances du cas d’étude.Ce travail a permis d’apporter une solution intéressante d’un point de vue industriel puisqu’il prend en compte les caractéristiques de la ligne de montage (opérateurs spécifiques) et améliore significativement la qualité du séquencement en un temps de calcul raisonnable. / In this thesis, the problem of sequencing mixed model assembly lines (MMAL) is considered. Our goal is to determine the sequence of products to minimize the work overload. This problem is known as the mixed model assembly line sequencing problem with work overload minimization (MMSP-W). This work is based on an industrial case study of a truck assembly line.Two approaches can be used to minimize the work overload: the use of task operation times or the respect of sequencing rules. Most of the earlier works applied in car industry use the latter approach. The originality of this work is to employ the task operation times for the generation of the product sequence in a MMAL.The literature review has highlighted two main gaps in previous works: most of the papers consider a single type of operators, and propose heuristics or metaheuristics to solve the problem. The originality of this work is to test exact methods for industrial case instances and to model three different types of operators.Two exact methods are developed: the mixed integer linear programming and dynamic programming. The models are tested on industrial case study instances. An experimental study is developed for both approaches in order to understand the complexity factors.Moreover, the problem is treated by two approximate methods: a heuristic based on dynamic programming and metaheuristics (genetic algorithm, simulated annealing and a hybrid method based on both genetic algorithm and simulated annealing). All approaches are tested on academic instances and on real data from the industrial case study.

Cette thèse aborde le problème de tournées de véhicules (VRP) intégrant des contraintes temporelles : fenêtres de temps (TW), synchronisation (S) et précédence (P), appliqué au secteur de soins à domicile, donnant le VRPTW-SP. Il s’agit d’établir un plan de visite journalier des soignants, aux domiciles des patients ayant besoin d’un ou plusieurs services. Tout d’abord, nous avons abordé ce problème sous angle mono-objectif. Ensuite, le cas bi-objectif est considéré. Pour la version mono-objectif, un Programme Linéaire à Variables Mixtes Entières (PLME), deux heuristiques constructives, deux procédures de recherches locales et trois métaheuristiques à base de voisinages sont proposés : une procédure de recherche constructive adaptative randomisée (GRASP), une recherche locale itérée (ILS) et une approche hybride (GRASP × ILS). Concernant le cas bi-objectif, différentes versions de métaheuristiques évolutionnaires multi-objectifs sont proposées, intégrant différentes recherches locales : l’algorithme génétique avec tri par non-dominance version 2 (NSGAII), une version généralisée de ce dernier avec démarrages multiples (MS-NSGAII) et une recherche locale itérée avec tri par non-dominance (NSILS). Ces algorithmes ont été testés et validés sur des instances adaptées de la littérature. Enfin, nous avons étendu le VRPTW-SP sur un horizon de planification, donnant le VRPTW-SP multi-période. Pour résoudre cette extension, un PLME ainsi qu’une matheuristique sont proposés / This work addresses the vehicle routing problem (VRP) including timing constraints: time windows (TW), synchronization (S) and precedence (P), applied in Home Health Care sector; giving the VRPTW-SP. This problem consists in establishing a daily caregivers planning to patients' homes asking for one or several services. We have started by considering the problem as a single objective case. Then, a bi-objective version of the problem is introduced. For solving the single-objective problem, a Mixed Integer Linear Program (MILP), two constructive heuristics, local search procedures and three local search based metaheuristics are proposed : a Greedy Randomized Adaptive Search procedure (GRASP), an Iterated Local Search (ILS) and a hybrid approach (GRASP × ILS). Regarding the bi-objective VRPTW-SP, different versions of multi-objective evolutionary algorithm, including various local research strategies are proposed: the Non-dominated Sorting Genetic Algorithm version 2 (NSGAII), a generalized version of this latter with multiple restarts (MS-NSGAII) and an Iterated Local Search combined with the Non-dominated Sorting concept (NSILS). All these algorithms have been tested and validated on appropriate instances adapted from the literature. Finally, we extended the VRPTW-SP on a multi-period planning horizon and then proposed a MILP and a matheuristic approach

Les travaux de thèse présentés s’intéressent à l’optimisation des activités d’un bloc opératoire. Ces activités concernent les interventions chirurgicales à planifier et les interventions de maintenance préventive sur les équipements dans les salles d’opération. Une solution est la synchronisation de ces activités lors de la construction du planning opératoire au niveau opératoire. Nous dissocions deux stratégies de programmation opératoire : programmation ouverte et programmation avec allocation préalable des plages horaires aux chirurgiens. Pour chacune des stratégies, nous considérons deux cas : le cas où l’heure de début d’une intervention de maintenance dans la salle est fixée, ladite intervention précédant l’affection des interventions chirurgicales dans les salles. Le second cas étant celui où l’heure de début de maintenance varie dans un intervalle entre une heure de début minimum et une heure de début maximum, avec l’intervention de maintenance placée a posteriori.Nous faisons plusieurs propositions de méthodes (exactes et approchées), y compris une méthode hybride, qui repose sur le couplage entre une métaheuristique et une heuristique. Les résultats obtenus sur des instances générées en concertation avec le monde hospitalier sont intéressants. / The presented dissertation is about the optimization of hospital systems, more precisely the optimization of the activities of an operation theatre. These activities showcase the surgical procedures to be planned and the preventive maintenance interventions on the equipment in the operating rooms. One solution is the synchronization of these activities during the construction of the operational planning at the operational level.We dissociate two operating programming strategies: Open Scheduling or Open programming and Block Scheduling or Programming with prior allocation of times to surgeons. For each strategy two cases are considered: the first case is where the time of beginning of a maintenance intervention in the room is fixed - this intervention preceding the affection of the surgical interventions in the rooms. The second case is where the maintenance start time varies in the interval between a minimum start time and a maximum start time, with the maintenance intervention placed beforehand. We make several proposition’s methods (exact and approximate), including a hybrid method, which is based on the coupling between a metaheuristic and a heuristic. The results obtained on bodies generated in consultation with the hospital’s world are interesting.

Les travaux de thèse présentés s’intéressent à l’optimisation des systèmes hospitaliers. Une solution existante est la mutualisation de ressources au sein d’un même territoire. Cela peut passer par différentes formes de coopération dont la Communauté Hospitalière de Territoire. Différents problèmes sont définis en fonction du niveau de décision : stratégique, tactique ou opérationnel ; et du niveau de modélisation : macroscopique, mesoscopique et microscopique. Des problèmes de dimensionnement, de planification et d’ordonnancement peuvent être considérés. Nous définissons notamment le problème de planification d’activités avec affectation de ressources. Plusieurs cas sont dissociés : soit les ressources humaines sont à capacité infinie, soit elles sont à capacité limitée et leur affectation sur site est une donnée, soit elles sont à capacité limitée et leur affectation sur site est une variable. Ces problèmes sont spécifiés et formalisés mathématiquement. Tous ces problèmes sont comparés à un problème de bin packing : le problème du bin packing de base pour le problème où les ressources humaines sont à capacité infinie, le problème du bin packing avec interdépendances dans les deux autres cas. Le problème du bin packing avec incompatibilités est ainsi défini. De nombreuses méthodes de résolution ont déjà été proposées pour le problème du bin packing. Nous faisons plusieurs propositions dont un couplage hiérarchique entre une heuristique et une métaheuristique. Des métaheuristiques basées individu et une métaheuristique basée population, l’optimisation par essaim particulaire, sont utilisées. Cette proposition nécessite un nouveau codage inspiré des problèmes de permutation d’ordonnancement. Cette méthode donne de très bons résultats sur les instances du problème du bin packing. Elle est simple à appliquer : elle couple des méthodes déjà connues. Grâce au couplage proposé, les nouvelles contraintes à considérer nécessitent d’être intégrées uniquement au niveau de l’heuristique. Le fonctionnement de la métaheuristique reste le même. Ainsi, notre méthode est facilement adaptable au problème de planification d’activités avec affectation de ressources. Pour les instances de grande taille, le solveur utilisé comme référence ne donne qu’un intervalle de solutions. Les résultats de notre méthode sont une fois encore très prometteurs : les solutions obtenues sont meilleures que la borne supérieure retournée par le solveur. Il est envisageable d’adapter notre méthode sur d’autres problèmes plus complexes par intégration dans l’heuristique des nouvelles contraintes à considérer. Il serait notamment intéressant de tester ces méthodes sur de réelles instances hospitalières afin d’évaluer leur portée. / The presented work is about optimization of the hospital system. An existing solution is the pooling of resources within the same territory. This may involve different forms of cooperation between several hospitals. Various problems are defined at the decision level : strategic, tactical or operational ; and at the modeling level : macroscopic, mesoscopic and microscopic. Problems of sizing, planning and scheduling may be considered. We define the problem of activities planning with resource allocation. Several cases are dissociated : either human resources are under infinite capacity, or they are under limited capacity and their assignment on a place is given, or they are under limited capacity and their assignment is a variable. These problems are specified and mathematically formalized. All thes problems are compared to a bin packing problem : the classical problem of bin packing is used for the problem where human resources are under infinite capacity, the bin packing problem with interdependencies is used in the two other cases. The bin packing problem with incompatibilities is defined. Many resolution methods have been proposed for the bin packing problem. We make several propositions including a hierarchical coupling between heuristic and metaheuristic. Single based metaheuristics and a population based metaheuristic, the particle swarm optimization, are used. This proposition requires a new encoding inspired by permutation problems. This method gives very good results to solve instances of the bin packing problem. It is easy to apply : it combines already known methods. With the proposed coupling, the new constraints to be considered need to be integrated only on the heuristic level. The running of the metaheuristic is the same. Thus, our method is easily adaptable to the problem of activities planning with resource allocation. For big instances, the solver used as a reference returns only an interval of solutions. The results of our method are once again very promising : the obtained solutions are better than the upper limit returned by the solver. It is possible to adapt our method on more complex issues through integration into the heuristic of the new constraints to consider. It would be particularly interesting to test these methods on real hospital authorities to assess their significance.

La prise de décision est une partie intégrante de notre vie quotidienne où le décideur est confronté à des problèmes composés de plusieurs objectifs habituellement contradictoires. Dans ce travail, nous traitons des problèmes d'optimisation multiobjectif dans des espaces de recherche continus ou discrets. Nous avons développé plusieurs nouveaux algorithmes basés sur les métaheuristiques hybrides évolutionnaires, en particulier sur l'algorithme MOEA/D. Nous avons proposé l'algorithme HEMH qui utilise l'algorithme DM-GRASP pour construire une population initiale de solutions de bonne qualité dispersées le long de l'ensemble des solutions Pareto optimales. Les résultats expérimentaux montrent la supériorité de toutes les variantes hybrides proposées sur les algorithmes originaux MOEA/D et SPEA2. Malgré ces bons résultats, notre approche possède quelques limitations, levées dans une version améliorée de HEMH : HEMH2 et deux autres variantes HEMHde et HEMHpr. Le Adaptive Binary DE inclus dans les HEMH2 et HEMHde a de meilleures capacités d'exploration qui pallient aux capacités de recherche locale contenues dans la HEMH, HEMH2 et HEMHde. Motivés par ces résultats, nous avons proposé un nouvel algorithme baptisé HESSA pour explorer un espace continu de recherche où le processus de recherche est réalisé par différentes stratégies de recherche. Les résultats expérimentaux montrent la supériorité de HESSA à la fois sur MOEA/D et dMOPSO. Tous les algorithmes proposés ont été vérifiés, testé et comparés à certaines méthodes MOEAs. Les résultats expérimentaux montrent que toutes les propositions sont très compétitives et peuvent être considérés comme une alternative fiable / Many real-world decision making problems consist of several conflicting objectives, the solutions of which is called the Pareto-optimal set. Hybrid metaheuristics proved their efficiency in solving these problems. They tend to enhance search capabilities by incorporating different metaheuristics. Thus, we are concerned with developing new hybrid schemes by incorporating different strategies with exploiting the pros and avoiding the drawback of the original ones. First, HEMH is proposed in which the search process includes two phases DMGRASP obtains an initial set of efficient solutions in the 1st phase. Then, greedy randomized path-relinking with local search or reproduction operators explore the non-visited regions. The efficient solutions explored over the search are collected. Second, a comparative study is developed to study the hybridization of different metaheuristics with MOEA/D. The 1st proposal combines adaptive discrete differential Evolution with MOEA/D. The 2nd combines greedy path-relinking with MOEA/D. The 3rd and the 4th proposals combine both of them in MOEA/D. Third, an improved version of HEMH is presented. HEMH2 uses inverse greedy to build its initial population. Then, differential evolution and path-relink improves these solutions by investigating the non-visited regions in the search space. Also, Pareto adaptive epsilon concept controls the archiving process. Motivated by the obtained results, HESSA is proposed to solve continuous problems. It adopts a pool of search strategies, each of which has a specified success ratio. A new offspring is generated using a randomly selected one. Then, the success ratios are adapted according to the success of the generated offspring. The efficient solutions are collected to act as global guides. The proposed algorithms are verified against the state of the art MOEAs using a set of instances from literature. Results indicate that all proposals are competitive and represent viable alternatives