Dans ce mémoire, je présente une synthèse de mes travaux de recherche ainsi que le choix des thèmes étudiés. J'ai choisi de présenter trois thèmes. Les résultats obtenus pour chaque thème dépendent à la fois de la difficulté des problématiques étudiées, du temps qui leur est imparti et des circonstances et des opportunités d'encadrement des étudiants. Ces thèmes sont essentiellement sur les problèmes d'ordonnancement et principalement sont axées sur les ateliers de type flowshop avec prise en compte de contraintes supplémentaires, proche de la réalité industrielle, à savoir, (i) prise en compte de contraintes de groupement des tâches, connues sous le terme anglais, batch scheduling, (ii) prise en compte de contraintes temporelles sur la succession d'exécution des tâches, connues sous le nom de time-lags, (iii) prise en compte de la détérioration des tâches. Notre contribution à ces trois thèmes concerne d'une part l'étude de la complexité de la structure combinatoire de ces problèmes, et d'autre part la mise en œuvre de méthodes d'optimisation efficaces pour la résolution. Ce mémoire se termine par une conclusion générale, ainsi que les perspectives et les orientations de recherche que nous souhaitons engagé dans un avenir proche ainsi que quelques réflexions sur de nouvelles voies de recherche.

Le problème du sac-à-dos à contraintes disjonctives (DCKP) est une variante du sac-à-dos normal. C'est un problème dans lequel certains objets peuvent être incompatibles avec d'autres. Le DCKP apparait, souvent, comme sous problème d'autres problèmes d'optimisation combinatoire plus complexes.

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.

Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d'ordonnancement du projet multi-compétences (MSPSP). L'objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d'un projet, composé d'un ensemble d'activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu'il y a encore un certain nombre d'instances pour lesquelles l'optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique.

Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l’équilibrage des services. Ces problèmes trouvent plusieurs applications dans le monde réel.L’objectif de nos recherches est l’élaboration de nouvelles méthodes de résolution pour les problèmes considérés en examinant leur performance avec une étude comparative par rapport aux différentes approches de la littérature. Deux variantes sont traitées. Le premier cas étudie le Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). Nous proposons de nouveaux prétraitements et bornes inférieures pour déterminer le nombre de véhicules nécessaires en s’inspirant de travaux menés en ordonnancement (raisonnement énergétique) et d’autres problèmes combinatoires comme la clique maximum et les problèmes de bin-packing. Nous présentons également un algorithme d’optimisation par essaim particulaire qui traite de la minimisation du nombre de véhicules puis de celle du temps de trajet total. Le deuxième cas étudie le Problème de Tournées de Véhicules avec des Fenêtres de Temps et des Visites Synchronisées (VRPTWSyn). Nous proposons plusieurs méthodes basées sur des approches heuristiques et des formulations linéaires avec l’incorporation d’inégalités valides pour tenir compte de la contrainte de synchronisation. / This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some realworld situations particularly those with different temporal constraints including time windows, visit synchronization and service balance.The aim of this research is to develop new algorithms for the considered problems,investigate their performance and compare them with the literature approaches.Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the VehicleRouting Problem with Time Windows and Synchronized Visits (VRPTWsyn).Both exact methods and heuristics are proposed and compared to the literature approaches.

Bien que la gestion des ressources humaines soit une problématique bien étudiée, elle reste d’actualité encore aujourd’hui, notamment en raison de la grande diversité des contextes applicatifs. De plus, les outils d’aide à la décision adressant ces problèmes peuvent encore être améliorés. Dans cette thèse, nous nous intéressons au contexte particulier où les activités des employés correspondent à des tâches fixées dans le temps, requérant des compétences précises et ne pouvant être préemptées. Nous étudions tout d’abord un problème issu de l’industrie pharmaceutique où il s’agit non seulement de trouver une affectation équitable des tâches, mais également de construire les horaires de travail du personnel de manière à respecter les contraintes légales et organisationnelles. Pour résoudre ce problème, nous proposons et comparons deux méthodes exactes, l’une fondée sur un modèle PLNE, l’autre sur un modèle PPC, ainsi que deux méta-heuristiques, l’une reposant sur une décomposition du problème, l’autre reposant sur une recherche par voisinages larges. Nous discutons ensuite de l’intégration de la meilleure de ces méthodes au sein d’un outil d’aide à la décision. Nous nous intéressons ensuite à un problème d’affectation de tâches fixées visant à minimiser le nombre d’employés requis. Pour résoudre ce problème, nous proposons une approche PPC tirant parti de la structure du problème. Nous montrons que cette approche permet d’obtenir rapidement de bonnes bornes, permettant ainsi de prouver l’optimalité sur les instances de la littérature dans un temps raisonnable. / Although workforce scheduling has been studied for decades, it remains highly relevant. In particular, applications and contexts are numerous, and they are always changing. Moreover, decision-support tools dedicated to workforce scheduling could still be improved. In this thesis, we focus on the particular context where workers are assigned to fixed tasks which cannot be preempted and require specific skills. First, we study a problem arising in a company specialized in drug evaluation where fixed tasks have to be assigned in a fair way to qualified employees so that the resulting individual shifts and plannings respect legal and organizational constraints. To handle this problem, we design and compare two exact methods, one based on a MIP model, the other on a CP approach, but also two meta-heuristics, one based on a decomposition strategy, and the other on a large neighborhood search. The best method is integrated within a decision support system. Second, we study a fixed tasks assignment problem, where the objective is to minimize the number of resources required to perform all the tasks. To tackle this problem, we suggest a constraint based approach which takes advantage of the structure of the problem. This approach enables to compute good bounds quickly, and thus, it proves optimality over state-of-the-art instances within a reasonable time limit.

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d’ordonnancement du projet multi-compétences (MSPSP). L’objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d’un projet, composé d’un ensemble d’activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu’il y a encore un certain nombre d’instances pour lesquelles l’optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique. / In this Phd Thesis we introduce several procedures to solve the Multi-Skill Project Scheduling Problem (MSPSP). The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. Precedence relations and resource constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Furthermore, we give a particula rimportance to exact methods for solving the Multi-Skill Project Scheduling Problem (MSPSP), since there are still several instances for which optimality is still to be proven. Nevertheless, with the purpose of solving big sized instances we also developed and implemented a heuristic approach.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

La thèse se situe dans le domaine de l'optimisation combinatoire, en particulier celui de la<br />modélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantes<br />NP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème de<br />la distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dos<br />généralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).<br />Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmes<br />approchés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partie<br />traite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.<br />L'approche exacte que nous proposons est de type séparation et évaluation s'appuyant<br />principalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de la<br />stratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.<br />La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP et<br />MMKP. Concernant le problème de la distribution équitable, nous proposons dans un premier<br />temps, une première version de l'algorithme exploitant certaines caractéristiques de la<br />recherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapidité<br />de la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problème<br />de sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche locale<br />itérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithme<br />est une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.<br /><br />Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.<br /><br />Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆues<br />principalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend de<br />la taille et la densité des instances traitées.