Dans la collaboration entre transporteurs, plusieurs transporteurs forment une alliance pour échanger leurs demandes de transport dans le but d'améliorer la rentabilité. Dans cette thèse, nous avons étudié la planification collaborative de transport entre transporteurs de charges partielles. Plus concrètement, nous avons étudié trois sous-problèmes soulevés dans cette planification collaborative: le problème de ramassage et de livraison avec fenêtres de temps, profits et demandes réservées, le problème de détermination de gagnants dans l'échange combinatoire, et le problème de génération d'enchère.Ces trois sous-problèmes sont les problèmes clés pour la planification collaborative de transport parmi des transporteurs, et ils sont peu étudiés dans la littérature. Nous avons établi les nouveaux modèles de programmation mathématique pour ces problèmes et développé des heuristiques efficaces pour trouver des solutions très proches de leurs optimums dans un temps de calcul raisonnable. Les heuristiques proposées sont plus performantes que les solveurs commerciaux (GUROBI, CPLEX) non seulement en termes de la qualité de solution, mais aussi en termes du temps de calcul. / In carrier collaboration, multiple carriers form an alliance to exchange their delivery requests for the purpose of improving profitability. In this thesis, we have studied the collaborative transportation planning (CTP) among less-than-truckload (LTL) carriers. More concretely, we have studied three sub-problems raised in this collaborative planning: the pickup and delivery problem with time windows, profits, and reserved requests (PDPTWPR), the winner determination problem (WDP) in carrier collaboration via combinatorial exchange (CE), and the bid generation problem (BGP).These sub-problems are the key issues for collaborative transportation planning among carriers, and they are rarely studied in the literature. We have established new mathematical programming models for these problems and developed efficient heuristics to find solutions close to their optimums in a reasonable computational time. The heuristics proposed are more efficient than commercial solvers (GUROBI, CPLEX) not only in terms of solution quality, but also in terms of computation time.

La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème. / The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Le crowdsourcing est une pratique permettant aux entreprises de faire appel à l’intelligence humaine à grande échelle afin d’apporter des solutions à des problématiques qu’elles souhaitent externaliser. Les problématiques externalisées sont de plus en plus complexes et ne peuvent être résolues individuellement. Nous proposons dans cette thèse une approche appelée SocialCrowd, contribuant à améliorer la qualité des résultats de crowdsourcing. Elle consiste à faire collaborer les participants afin d’unir leur capacité de résolution et apporter des solutions aux problèmes externalisés de plus en plus complexes. Les groupes collaboratifs sont mis en compétition, via des rétributions attrayantes, afin d’obtenir de meilleures résolutions. Par ailleurs, il est nécessaire de protéger les données privées des groupes en compétition. Nous utilisons les réseaux sociaux comme support de fuite de données. Nous proposons une approche basée sur l’algorithme Dijkstra pour estimer la probabilité de propagation de données privées d’un membre sur le réseau social. Ce calcul est complexe étant donné la taille des réseaux sociaux. Une parallélisation du calcul est proposée suivant le modèle MapReduce. Un algorithme de classification basé sur le calcul de propagation dans les réseaux sociaux est proposé permettant de regrouper les participants en groupes collaboratifs et compétitifs tout en minimisant les fuites de données d’un groupe vers l’autre. Comme ce problème de classification est d’une complexité combinatoire, nous avons proposé un algorithme de classification basé sur les algorithmes d’optimisation combinatoires tels que le recuit simulé et les algorithmes génétiques. Etant donnée le nombre important de solutions possible, une approche basée sur le modèle du Soft Constraint Satisfaction Problem (SCSP) est proposée pour classer les différentes solutions. / Crowdsourcing is the practice of allowing companies to use human intelligence scale to provide solutions to issues they want to outsource. Outsourced issues are increasingly complex and cannot be resolved individually. We propose in this thesis an approach called SocialCrowd, helping to improve the quality of the results of crowdsourcing. It compromise to collaborate participants to unite solving ability and provide solutions to outsourced problems more and more complex. Collaborative groups are put in competition through attractive remuneration, in order to obtain better resolution. Furthermore, it is necessary to protect the private information of competing groups. We use social media as a support for data leakage. We propose an approach based on Dijkstra algorithm to estimate the propagation probability of private data member in the social network. Given the size of social networks, this computation is complex. Parallelization of computing is proposed according to the MapReduce model. A classification algorithm based on the calculation of propagations in social networks is proposed for grouping participants in collaborative and competitive groups while minimizing data leaks from one group to another. As this classification problem is a combinatorial complexity, we proposed a classification algorithm based on combinatorial optimization algorithms such as simulated annealing and genetic algorithms. Given the large number of feasible solutions, an approach based on the model of Soft Constraint Satisfaction Problem (SCSP) is proposed to classify the different solutions.

Les travaux menés dans cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine de recherche à la croisée de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Notre objectif dans cette thèse est de concevoir des algorithmes efficaces pour la résolution de problèmes de décision dans des environnements complexes (multicritère, multi-agents, incertain). Nous nous intéressons d'une part à l'élicitation des préférences fondée sur des modèles décisionnels et d'autre part à l'exploitation de ces préférences pour la recherche des solutions optimales sur des espaces définis de manière explicite ou implicite (optimisation combinatoire). Pour la résolution de problèmes combinatoires, nous proposons et étudions une nouvelle approche, consistant à combiner l'élicitation incrémentale des préférences et l'exploration implicite des solutions potentielles. L'intuition sous-jacente est d'utiliser l'exploration des solutions potentielles pour identifier des questions informatives tout en exploitant les réponses obtenues pour mieux focaliser la recherche sur les solutions préférées. Cette approche nous a conduit à proposer des procédures de décision par élicitation incrémentale pour les problèmes de recherche dans un graphe d'états multi-objectifs, les problèmes de chemins optimaux et d'arbre couvrants dans les graphes multicritères, les problèmes de sac à dos multi-agents et les problèmes de décision séquentielle dans l'incertain. Nous établissons des résultats théoriques garantissant la correction des algorithmes proposés et présentons des tests numériques montrant leur efficacité pratique. / This thesis work falls within the area of algorithmic decision theory which is at the junction of decision theory, operations research and artificial intelligence. Our aim is to produce algorithms allowing the fast resolution of decision problems in complex environments (multiple criteria, multi-agents, uncertainty). This work focuses on decision-theoretic elicitation and uses preferences to efficiently determine the best solutions among a set of alternatives explicitly or implicitly defined (combinatorial optimization). For combinatorial optimization problems, we propose and study a new approach consisting in interleaving incremental preference elicitation and preference-based search. The idea is to use the exploration to identify informative preference queries while exploiting answers to better focus the search on the preferred solutions. This approach leads us to propose incremental elicitation procedures for multi-objective state-space search problems, multicriteria shortest path problems, multicriteria minimum spanning tree problems, multi-agents knapsack problems and sequential decision problems under uncertainty. We provide theoretical guarantees on the correctness of the proposed algorithms and we present numerical tests showing their practical efficiency.

Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]... / The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....

Les travaux de cette thèse s'inscrivent dans le contexte de la coordination des décisions de planification survenant dans une chaîne logistique à deux acteurs: un fournisseur et un producteur souhaitant chacun diminuer leur propre coût. Les décisions de planification prises de manière indépendante par chaque acteur peuvent amener à une mauvaise performance de la chaîne logistique en terme de coûts, d'où la nécessité d'une coordination. Nous étudions des mécanismes de partage de coûts entre des acteurs en définissant des stratégies de coordination entre les acteurs par la mise en place de contrats. Nous considérons le cas où le producteur (resp. fournisseur) peut imposer son plan de production optimal au fournisseur (resp. distributeur). Différentes hypothèses de partage de coûts, ainsi que la problématique d'asymétrie d'information sont prises en compte dans ces travaux. Nous effectuons également des analyses expérimentales mesurant la diminution du coût de la chaîne logistique obtenue quand les acteurs coopèrent. Ce contexte nous amène à étudier de nouveaux problèmes de lot-sizing pour lesquels nous proposons une analyse de complexité et des algorithmes de programmation dynamique pour les résoudre. Nous proposons également une étude théorique des problèmes de lot-sizing à deux niveaux avec une capacité de stockage limitée. / This thesis focus on the coordination of planning decisions in a two-level supply chain composed of one supplier and one retailer. Each actor wants to minimize his own cost. The planning decisions independently took by the actors can lead to a poor performance in terms of costs, hence the necessity of coordination. We study cost sharing mechanisms between the actors by designing contracts. In this work, we consider the case where the retailer (resp. supplier) can impose his optimal production plan to the supplier (resp. retailer). Different cost sharing hypothesis, as well as the asymmetric information problem are taking into account in this thesis. We also perform an experimental analysis in order to evaluate the decrease of the supply chain cost obtained when the actors cooperate. This context leads us to study new lot-sizing problems for which we propose a complexity analysis and dynamic programming algorithms in order to solve them. We also propose a theoritical study of two-level lot-sizing problems with inventory bounds.

Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire. / This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above.

Le Calcul Haute Performance, regroupant l’ensemble des acteurs responsables de l’amélioration des performances de calcul des applications scientifiques sur supercalculateurs, s’est donné pour objectif d’atteindre des performances exaflopiques. Cette course à la performance se caractérise aujourd’hui par la fabrication de machines hétérogènes dans lesquelles chaque composant est spécialisé. Parmi ces composants, les mémoires du système se spécialisent, et la tendance va vers une architecture composée de plusieurs mémoires aux caractéristiques complémentaires. La question se pose alors de l’utilisation de ces nouvelles machines dont la performance pratique dépend du placement des données de l’application sur les différentes mémoires. Dans cette thèse, nous avons développé une formulation du problème d’allocation de donnée sur une Architecture à Mémoires Hétérogènes. Dans cette formulation, nous avons fait apparaître le bénéfice que pourrait apporter une analyse temporelle du problème, parce que de nombreux travaux reposaient uniquement sur une approche spatiale. À partir de cette formulation, nous avons développé un outil de profilage hors ligne pour approximer les coefficients de la fonction objective afin de résoudre le problème d’allocation et d’optimiser l’allocation des données sur une architecture composée deux de mémoires principales aux caractéristiques complémentaires. Afin de réduire la quantité de modifications nécessaires pour prendre en compte la stratégie d’allocation recommandée par notre boîte à outils, nous avons développé un outil capable de rediriger automatiquement les allocations de données à partir d’un minimum d’instrumentation dans le code source. Les gains de performances obtenus sur des mini-applications représentatives des applications scientifiques codées par la communauté permet d’affirmer qu’une allocation intelligente des données est nécessaire pour bénéficier pleinement de ressources mémoires hétérogènes. Sur certaines tailles de problèmes, le gain entre un placement naïf est une allocation instruite peut atteindre un facteur ×3.75. / High Performance Computing, which brings together all the players responsible for improving the computing performance of scientific applications on supercomputers, aims to achieve exaflopic performance. This race for performance is today characterized by the manufacture of heterogeneous machines in which each component is specialized. Among these components, system memories specialize too, and the trend is towards an architecture composed of several memories with complementary characteristics. The question arises then of these new machines use whose practical performance depends on the application data placement on the different memories. Compromising code update against performance is challenging. In this thesis, we have developed a data allocation on Heterogeneous Memory Architecture problem formulation. In this formulation, we have shown the benefit of a temporal analysis of the problem, because many studies were based solely on a spatial approach this result highlight their weakness. From this formulation, we developed an offline profiling tool to approximate the coefficients of the objective function in order to solve the allocation problem and optimize the allocation of data on a composite architecture composed of two main memories with complementary characteristics. In order to reduce the amount of code changes needed to execute an application according to our toolbox recommended allocation strategy, we have developed a tool that can automatically redirect data allocations from a minimum source code instrumentation. The performance gains obtained on mini-applications representative of the scientific applications coded by the community make it possible to assert that intelligent data allocation is necessary to fully benefit from heterogeneous memory resources. On some problem sizes, the gain between a naive data placement strategy, and an educated data allocation one, can reach up to ×3.75 speedup.

Les problèmes d’optimisation combinatoire (Constraint Optimization Problems – COP) sont souvent difficiles à résoudre et le choix de la stratégie de recherche a une influence importante sur la performance du solveur. Pour de résoudre un problème d’optimisation combinatoire en explorant un arbre de recherche, il faut choisir une heuristique de choix de variable (qui définit l’ordre dans lequel les variables vont être instanciées), une heuristique de choix de valeur (qui spécifie l’ordre dans lequel les valeurs seront essayées), et une stratégie de retour-arrière (qui détermine vers quel noeud effectuer les retours-arrière lorsqu’une feuille de l’arbre est rencontrée). Pour les stratégies de retour-arrière, il y a celles dont les retours-arrière sont totalement déterministes (e.g. Depth-First Search – DFS) et d’autres qui s’appuient sur des mécanismes d’évaluation de noeuds plus dynamiques (e.g. Best-First Search). Certaines (e.g. Limited Discrepancy Search – LDS) peuvent être implémentées soit comme un algorithme itératif déterministe ou un évaluateur de noeud. Une stratégie est dite adaptative quand elle s’adapte dynamiquement à la structure du problème et identifie les zones de l’espace de recherche qui contiennent les “bonnes” solutions. Dans ce contexte, des stratégies de branchement adaptatives ont été proposées (e.g. Impact-Based Search – IBS) ainsi qu’une stratégie de retour-arrière adaptative (e.g. Adaptive Discrepancy Search – ADS), proposée pour les problèmes d’optimisation distribués. À notre connaissance, aucune stratégie adaptative qui utilise l’apprentissage par renforcement (Reinforcement Learning – RL) pour supporter son mécanisme d’apprentissage n’a été proposée dans la littérature. Nous pensons que les techniques de RL permettront un apprentissage plus efficace et qu’une stratégie de retour-arrière munie de ces techniques aura le potentiel de résoudre les problèmes d’optimisation combinatoire plus rapidement. Dans ce mémoire, nous proposons un algorithme (RLBS) qui “apprend” à faire des retours-arrière de manière efficace lors de l’exploration d’arbres non-binaires. Plus précisément, il s’agit une stratégie de retour-arrière qui se base sur l’apprentissage automatique pour améliorer la performance du solveur. En fait, nous utilisons l’apprentissage par renforcement pour identifier les zones de l’espace de recherche qui contiennent les bonnes solutions. Cette approche a été développée pour les problèmes d’optimisation combinatoire dont l’espace de recherche est encodé dans un arbre non-binaire. Comme les arbres sont non-binaires, on a l’occasion d’effectuer plusieurs retours-arrière vers chaque noeud durant l’exploration. Ceci permet d’apprendre quels noeuds mènent vers les meilleures récompenses en général (c’est-à-dire, vers les feuilles les plus intéressantes). Le branchement est effectué en utilisant une stratégie de choix de variable/valeur quelconque. Toutefois, quand un retour-arrière est nécessaire, la sélection du noeud cible s’appuie sur l’apprentissage par renforcement. RLBS est évalué sur cinq instances industrielles du problème de la planification des opérations du rabotage du bois et a été comparé à ADS et à LDS sur cette même application. RLBS dépasse LDS et ADS, en termes de temps de calcul nécessaire à la résolution, sur chacune de ces instances-là et trouve la solution optimale plus rapidement. Les expérimentations ont montré que RLBS est en moyenne 4 fois plus rapide que ADS, et 6 fois plus rapide que LDS. RLBS a aussi été évalué sur une instance jouet du même problème et a été comparé à IBS. RLBS surpasse largement IBS. Il est capable de trouver une solution optimale en explorant beaucoup moins de noeuds que le nombre nécessaire à IBS pour trouver une telle solution. / Combinatorial optimization problems are often very difficult to solve and the choice of a search strategy has a tremendous influence over the solver’s performance. To solve a problem using search, one needs to choose a variable selection strategy (defining the order in which variables will be instantiated), a value selection strategy (that specifies the sequence in which we will try the variable possible values) and a backtracking strategy (that determines to which node we should backtrack/backjump, when a leaf is reached or a dead-end is encountered). When it comes to backtracking strategies, there are some that are encoded into full deterministic algorithms (e.g. Depth-First Search – DFS), and others that rely on more dynamic node evaluator mechanisms (e.g. Best-First Search). Others (e.g. Limited Discrepancy Search – LDS) can be implemented as a deterministic iterative algorithm or as a node evaluator. A strategy is said to be adaptive when it dynamically adapts to the structure of the problem and identifies the areas of the search space that contain good solutions. Some have proposed adaptive branching strategies (e.g. Impact-based Search – IBS) or a backtracking strategy (e.g. Adaptive Discrepancy Search – ADS) proposed for distributed optimization problems. To our current knowledge, no adaptive backtracking strategy that relies on Reinforcement Learning (RL) has been proposed yet. We believe that RL techniques could allow a more efficient learning process and that, provided with these techniques, a backtracking strategy has a great potential of solving combinatorial optimization problems in a faster way. In this thesis, we introduce an algorithm (RLBS) that learns to efficiently backtrack when searching non-binary trees. We consider a machine learning approach which improves the performance of the solver. More specifically, we use reinforcement learning to identify the areas of the search space that contain good solutions. The approach was developed for optimization problems for which the search space is encoded as a non-binary tree. Since the trees are non-binary, we have the opportunity to backtrack multiple times to each node during the search. This allows learning which nodes generally lead to the best rewards (that is, to the most interesting leaves). Branching can be carried on using any variable/value selection strategy. However, when backtracking is needed, the selection of the target node involves reinforcement learning. RLBS is evaluated on five instances of the lumber planing problem using real idustrial data, and it is compared to LDS and ADS. It outperforms classic (non-adaptive) search strategies (DFS, LDS), an adaptive branching strategy (IBS), and an adaptive backtracking strategy (ADS) on every instance of this problem. Experiments have shown that RLBS is on average 4 times faster than ADS, and 6 times faster than LDS. RLBS is also evaluated on a toy instance of the lumber planing problem and compared to IBS. RLBS substantially outperforms IBS by solving the problem to optimality much faster.

Un problème d'ordonnancement de projet à ressources limitées (POPRL) consiste en l'ordonnancement d'un ensemble de tâches, nécessitant un ou plusieurs types de ressources, renouvelables ou non renouvelables, en quantités limitées. La résolution d'un POPRL a pour but la détermination des dates d'exécution des tâches en tenant compte des contraintes de préséance et de disponibilité des ressources et ayant comme objectif la minimisation de la durée totale du projet. Le POPRL est un problème d'optimisation combinatoire de complexité NP-dur (Blazewicz et al. 1983). Une revue de littérature du (POPRL) est présentée au chapitre 2. Plus de 125 articles scientifiques sont analysés. Les contributions relatives à ce problème portent sur les méthodes exactes de résolution, la détermination de bornes inférieures sur la durée du projet et les méthodes heuristiques (approchées) de résolution. L'aspect pratique de ce problème dans des contextes industriels divers a conduit à de nombreuses généralisations du problème classique. On constate que malgré les efforts déployés pour définir des POPRL plus généraux, les contraintes de transfert des ressources continuent à être ignorées, nous constatons aussi que l'optimisation du problème en considérant les coûts a été très peu traitée dans la littérature. Ce qui forcent les gestionnaires dans la plus part des cas à se baser uniquement sur leur expérience pour réaliser ou ajuster manuellement les ordonnancements produits par des heuristiques conçues pour résoudre des versions simplifiées du problème. Cette thèse tente de combler partiellement ces lacunes. Le chapitre 3 traite le problème d'ordonnancement de projet à ressources limitées POPRLTT avec des temps de transfert des ressources. Un temps de transfert est le temps nécessaire pour transférer une ressource du lieu d'execution d'une activité vers un autre. Ainsi, le temps de transfert d'une ressource dépend des lieux des activités à exécuter, ainsi que des caractéristiques des ressources à transférer. L'objectif dans un POPRLTT est la détermination des dates d'exécution des tâches en tenant compte des contraintes de préséance et de disponibilité des ressources et les temps de transfert des ressources. L'objectif est de minimiser la durée totale du projet. Nous proposons un nouvel algorithme génétique basé sur un opérateur de croisement de deux positions. L'étude expérimentale menée sur un grand nombre de problèmes test prouve que l'algorithme proposé est meilleur que les deux méthodes déjà existantes dans la littérature. Une généralisation du problème d'ordonnancement de projet à ressources limitées et des temps de transfert des ressources au contexte multi mode (POPRL=PMETT) est présentée au chapitre 4. Dans ce problème, nous supposons que la préemption est non autorisée, et les ressources utilisées sont renouvelables et non renouvelables, chaque activité a plusieurs modes d'exécution, et les relations de préséance sont de type dit début-fin sans décalage. L'objectif est de choisir un temps de début (ou de fin) et un mode d'exécution pour chaque tâche du projet, pour que la durée du projet soit minimisée tout en respectant les contraintes de préséance, de disponibilité de ressources et les temps de transfert. Au meilleur de notre connaissance, cette version du problème n'a jamais été abordée auparavant. Nous proposons une formulation mathématique de ce problème, ensuite nous présentons un algorithme génétique, que nous avons conçu pour résoudre les instances de grandes tailles. Pour tester les méthodes proposées nous développons des nouveaux ensembles de problèmes-tests pour le POPRL=PMETT, qui pourront être utilisés dans l'avenir pour mener des recherches dans ce domaine. Dans le chapitre 5, nous définissons une nouvelle généralisation du problème d'ordonnancement de projet à ressources limitées en considérant l'objectif de minimiser le coût total d'exécution du projet. Celui-ci est composé de deux éléments principaux: le coût direct des ressources à utiliser et les frais généraux qui ne dépendent pas de la quantité de ressources allouées, mais qui sont proportionnels à la durée du projet. Ce problème, que nous appelons Problème général d'allocation et de nivellement des ressources d'un projet (PGANRP) est très commun en pratique, mais très peu de recherche est consacrée à ce problème. Dans un PGANRP, nous devons simultanément déterminer les quantités des ressources à allouer au projet au cours de son exécution et réduire la variabilité de l'utilisation des ressources au minimum tout en essayant de terminer le projet à une date de fin acceptable. Les quantités des ressources à allouer au projet devraient permettre l'accomplissement du projet à cette date et devient une limite sur la disponibilité de ces ressources durant toute l'exécution du projet. Nous proposons, une formulation mathématique du problème et deux approches de recherche dans le voisinage pour les instances de grandes tailles. / The resource-constrained project scheduling problem (RCPSP) consists of scheduling a set of activities or tasks using one or more resource types available in limited quantity. In the standard version of this problem, pre-emption is not allowed, precedence relations are of the no-lag, finish-to-start type, and the used resources are renewable meaning that the same resources quantity are available each time period. Solving this NP-hard optimization problem requires the determination of tasks execution date such that the project duration is minimized without using more than the available resource quantities. In the first chapter of this thesis, the research problem and research objectives are presented while chapter 2 reviews the literature and contributions to the RCPSP and some of its extended versions. More than 125 published papers are reviewed. These contributions are divided into 4 groups of contributions. Those proposing optimal solution methods, those developing lower bounds on the project duration, those proposing heuristic and approximate solution methods, and those extending the standard version of the problem in order to make it closer to the real-life problem. This literature review revealed that very few contributions explicitly take into consideration the time required to transfer resources between execution sites of the project. Only three such contributions are published and none of these three publication deal with the case where tasks have more than one execution mode. This review also revealed that the large majority of the published research deals with the problem where the objective is to minimize the duration of the project. However, in almost all real-life situations, the objective is to minimise the total cost of the project. That is why this thesis is dedicated to solve these neglected extensions of the RCPSP. Chapter 3 deals with the resource-constrained project scheduling problem with transfer times (RCPSPTT). Thus the goal in this case is to determine execution dates that allows for resources to be transferred between execution sites while respecting the precedence relations between these tasks as well as resources availability. A new genetic algorithm (GA) is developed to solve the RCPSPTT. This algorithm uses a new and efficient crossover operator. The chapter also study the performance of the proposed genetic algorithm and shows that it produces better results than the two previously published solution heuristics. It is to notice that the proposed GA considers renewable resource types and assume that tasks have only one execution mode. Chapter 4 deals with the multi-mode resource-constrained project scheduling problem with transfer times (MRCPSPTT). Thus, it extends the problem studied in the previous chapter to the multi-mode case under the assumptions of no pre-emption while using renewable and non-renewable resources. This problem has never been the subject of any published research before. An integer linear mathematical formulation of the problem is given as well as new genetic algorithm is developed to solve it. An extensive empirical analysis is then presented and shows that the proposed GA is able to produce the optimal solution for 529 test instances with 10, 20 and 30 activities. Chapter 5 introduces the generalized resource allocation and leveling problem (GRALP). This problem can be stated as follows. Given a set of project tasks to execute, their possible execution modes and precedence relations, an upper bound on the amount of resources that can be made available to the project, a project due date, the cost of resource utilization and the overhead cost; determine the execution date and mode for each task and the amount of resources to allocate to the project. The objective is to minimize the total project execution cost while respecting precedence constraints, project due date and not using more than the amount of resources that we decided to allocate to the project. Again we notice that this problem has never been the subject of any published research work. Chapter 5 presents an integer linear formulation of the problem, a neighborhood search solution heuristic, a genetic algorithm to solve it and an empirical experiment to evaluate the proposed heuristics showing the superiority of the proposed GA. Finally, the conclusions of the thesis and some propositions for future research are given.