Search

The domain of energy management involves many combinatorial optimization problems known to be computationally hard. The emergence of quantum computers suggests new approaches for these problems. For near-future machines particularly promising are variational quantum heuristics such as QAOA that can leverage the computational power of the imperfect quantum hardware. We explore the potential of variational quantum algorithms for optimization problems issued from the field of "smart charging"}of electrical vehicles. We consider two problems inspired by real-world usecases. In the first problem, modeled as Max-K-Cut, we search to schedule a set of prioritized charges on several stations while minimizing the weighted completion time. In the second problem, modeled as Maximum Independent Set, we aim to maximize the number of satisfied charge demands on a single station while respecting the conflicts between demands. For both problems, we develop an experimental protocol specifying the encoding step and the parameter optimization routine. Our numerical experiments confirm the interest of quantum heuristics for these problems as well as the quality of our experimental protocol. In order to extend the applicability of quantum heuristics beyond QUBO we introduce a new hybrid approach that integrates quantum routines in the classical Branch & Price algorithm for large integer linear programs. We test this approach on a smart charging problem that is modeled as graph coloring problem. Our computational results affirm the potential of the hybrid approach while revealing the considerable dependence of the performance gain on the particular instance of the problem. Important components of variational algorithms can be represented as ZX-diagrams. We demonstrate how the rewriting rules of ZX-calculus can be used to derive the analytical formula for the mean energy of a general Ising model in a QAOA of depth 1 state. Furthermore, we contribute to the theoretical exploration of variational algorithms by extending the ZX-calculus with addition and differentiation of ZX-diagrams. Our inductive procedure for the addition is fully diagrammatic. For the differentiation we suggest two approaches. The first approach is inductive, it leverages our procedure for addition to explicitly represent the product rules. The second approach is resumed in two formulas derived from the factored form of parameterized diagrams.; Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.

Manufacturers must efficiently manage their production capacities and their performances to satisfy customer demands with quality goods. They also have been constantly challenged to optimize resource usage and production performance in a dynamic and volatile market context in a cost effective manner. To achieve this business objective, we consider lot-sizing problems under yield uncertainty via a robust, adaptive robust and distributionally robust optimization methodologies to determine the production setups and quantities that meet demands with quality goods, while minimizing the overall productionand inventory management costs. We propose different models and methodological strategies to compute optimal robust and less conservative production plans. We also provide a risk analysis to help decision-makers to tailor their decision plans to their strategic and operational goals. The experimental results show that robust-wise production plans have a better cost cutting strategy compared with other resolution approaches. The computational experiments show the robustness and effectiveness of the robust model through an average and worst case analysis. The experiments also demonstrate the performances and the value of the adaptive robust solutions and thelow sensitiveness to errors in predictions of the distributionally robust models.; Les fabricants doivent gérer leurs capacités de production et leur performance pour satisfaire la demande des clients avec des produits de qualité. De plus, ils sont constamment mis au défi d’optimiser l’utilisation de leurs ressources et leur performance de production dans un contexte de marché dynamique et volatil, et ce, de manière rentable. Pour atteindre cet objectif commercial, un défi tactique à relever parmi d’autres, les fabricants doivent minutieusement prendre des décisions de dimensionnement de lots de production afin de déterminer la configuration et les quantités de production répondant aux demandes avec des produits de qualité, tout en minimisant les coûts globaux de production et de gestion de stocks. Nous proposons différents modèles et stratégies méthodologiques pour calculer des plans de production optimaux robustes à conservation moindre. Nous fournissons également une analyse de risque pour aider les décideurs à adapter leurs plans décisionnels à leurs objectifs stratégiques et opérationnels. Les résultats expérimentaux montrent que les plans de production robustes ont une meilleure stratégie de réduction des coûts par rapport aux autres approches de résolution. Les expériences numériques montrent la robustesse et l’efficacité du modèle robuste à travers une analyse des cas moyens et les plus défavorables. Les expériences démontrent également les performances et la valeur des solutions adaptatives robustes et la faible sensibilité aux erreurs de prédiction des modèles distributionnellement robustes.

International audience; Pour un utilisateur qui n'est pas un développeur expert en recherche opérationnelle, un système d'optimisation est souvent perçu comme une boîte noire qui, étant donnée une instance d'un problème, fournit une solution qu'il convient de suivre. Dans ce contexte, l'utilisateur peut vouloir interroger le système quant à la pertinence d'une solution qu'il aurait retourné et obtenir des explications de sa part, que ce soit pour avoir davantage confiance en cette solution avant de la suivre ou simplement pour être critique vis-à-vis de celle-ci.Expliquer des solutions obtenues au moyen de systèmes d'optimisation n'est pas une tâche facile et soulève de nombreuses questions. Que peut-on expliquer ? Comment calculer le contenu d'une explication ? Qu'est-ce qu'un calcul d'explication efficace? Comment présenter une explication? Qu'est-ce qu'une explication intelligible pour l'utilisateur ? Etc. Nous proposons de s'intéresser à cette problématique de l'explication de solutions dans le cas d'une application : le problème de planification d'employés mobiles.

Mass customization and frequent market fluctuations push industrial companies to employ flexible and reconfigurable multi/mixed-model assembly lines instead of dedicated ones. This thesis focuses on this problem. It concentrates mainly on mixed-model assembly line design and balancing problems. The questions concerning the efficiency of such lines, the importance of optimal task assignment and use of walking workers are asked and studied. To increase the flexibility of the line, we account for different types of task assignments: fixed, model-dependent,and dynamic. We aim to design a line that can handle various entering product models. We use combinatorial optimization methods, and,in particular, robust optimization approaches. We present an extensive literature review on line balancing, workforce planning, and workforce reconfiguration strategies in different production systems. The first problem addresses a configuration selection problem between a single multi-model line and multiple dedicated lines. The second problem consists in designing and balancing a mixed-model assembly line with walking workers. We propose fixed and model-dependent task assignments for a given set of product mixes. The goal is to minimize the total cost of workers and equipment for the worst case. The third problem extends the second one. It considers the dynamic task assignment. In the last problem, we extend the third problem for the case where the sequence of products unfolds takt by takt. In this context, we minimize both the expected total cost and the worst-case cost. In order to solve the considered problems, we develop several exact methods and heuristics: mixed-integer linear programming models, greedy algorithm, local search,matheuristic and fixed-and-optimize heuristics among others. We also apply a Markov Decision Process to the proposed line balancing problem in the last chapter. It is the first study applying this method to a line balancing problem. Computational experiments evaluate the performance of the proposed approaches in terms of solution quality and time consumption. We draw managerial insights in each chapter. Our results show the superiority of the dynamic task assignment compared to model-dependent and fixed ones in different production situations.; Une forte personnalisation de produits et des fréquentes fluctuations du marché poussent les entreprises industrielles à utiliser des lignes d’assemblage à modèles multiples/mixtes, flexibles et reconfigurables plutôt que des lignes dédiées. Cette thèse de doctorat est consacrée à cette problématique. Elle est portée principalement sur la conception et l’équilibrage de lignes d’assemblage à modèles mixtes. Les questions de l’efficacité de telles lignes, l’importance d’affectation optimale de tâches et d’utilisation des opérateurs mobiles sont posées et étudiées. Pour augmenter la flexibilité de la ligne, nous prenons en compte différents types d’affectation des tâches : fixe, dépendant du modèle et dynamique. Nous cherchons à concevoir une ligne qui peut gérer la variété possible de produits entrants. Nous utilisons des techniques d’optimisation combinatoire, et, en particulier, des approches d’optimisation robuste. Nous présentons une revue extensive de la littérature sur l’équilibrage des lignes, la planification des opérateurs et les stratégies de reconfiguration de lignes via la réaffectation des opérateurs. Le premier problème de la thèse porte sur la sélection de configuration entre une ligne unique à multi-modèles et plusieurs lignes dédiées. Le second problème consiste à concevoir et à équilibrer une ligne d’assemblage à modèles mixtes avec des opérateurs mobiles. Nous proposons des affectations de tâches fixes et dépendantes du modèle pour une gamme donnée de produits entrants sur la ligne. L’objectif est de minimiser le coût total de la ligne composé des coûts d’opérateurs et d’équipement dans le pire des cas. Le troisième problème est une extension du deuxième, où les tâches peuvent être affectées de manière dynamique. Enfin, dans le dernier, quatrième problème, nous étendons le troisième problème au cas où la séquence de produits est découverte takt par takt. Dans ce contexte, nous minimisons à la fois l’espérance mathématique de coût total et le coût dans le pire des cas. Afin de résoudre ces problèmes, nous développons plusieurs méthodes exactes et des heuristiques : des modèles de programmation linéaire en variables mixtes, un algorithme glouton, une recherche locale, une matheuristique et une heuristique de type " fixer et optimiser ", entre autres. Nous appliquons également un processus de décision markovien au dernier problème, ce qui représente la première étude qui utilise cette approche pour l’équilibrage de lignes dans la littérature. Des expériences numériques évaluent la performance des modèles proposés en termes de la qualité de solution et du temps de calcul. Nous tirons des conclusions managériales dans chaque chapitre. Nos résultats montrent la supériorité de l’affectation dynamique des tâches par rapport aux affectations fixes et dépendantes de modèle dans différentes situations de production.

Cleaning debris in urban areas after major disasters is very relevant to inhabitants to recover from their effects. In natural disasters, an unexpected and large area can be affected. Moreover, the time and the costs to perform the cleaning operations can be very high. In this work, the integrated multi-period scheduling routing problem to clean debris (SRP-CD) after major disasters is investigated. The problem includes strategical (scheduling) and operational (routing) decisions, considering complex issues such as two levels of synchronization between work-troops and dump trucks, and between dump trucks necessary to load, transport and unload debris during limited working days. The goal of SRP-CD is twofold: minimizing the number of days for the overall cleaning, in the strategical level; and minimizing the total costs of vehicle routes in the operational level. A new mathematical model based on a dynamic multi-flow formulation, constructive heuristics, Large Neighborhood Search (LNS)-based metaheuristics and hybrid metaheuristics based on LNS and Simulated Annealing are proposed. Comparison experiments for the model and the approaches are carried out to measure performance and robustness of the proposed methods. To the best of our knowledge, these are the first contributions in the literature for SRP-CD, including all the aspects addressed in this thesis.; Le nettoyage des débris dans les zones urbaines après des catastrophes majeures est très important pour permettre aux habitants de se remettre de leurs effets. Lors de catastrophes, une zone inattendue et étendue peut être touchée. De plus, le temps et les coûts pour effectuer les opérations de nettoyage peuvent être très élevés. Cette thèse aborde le problème intégré multi-période de planification et de tournées de véhicules pour nettoyer les débris (SRP-CD) après des catastrophes majeures. Le problème comprend des décisions stratégiques (planification) et opérationnelles (tournées) et prend en compte des questions complexes telles que deux niveaux de synchronisation : entre les équipes de travail et les camions-bennes, et entre les camions-bennes nécessaires pour charger, transporter et décharger les débris pendant les journées de travail. L'objectif du SRP-CD est double : minimiser le nombre de jours pour le nettoyage global, au niveau stratégique, et minimiser le coût total de routage des véhicules, au niveau opérationnel. Un nouveau modèle mathématique basé sur une formulation dynamique multi-flot, des heuristiques constructives, des métaheuristiques basées sur la recherche par grand voisinage (LNS) et des métaheuristiques hybrides basées sur la LNS et le recuit simulé sont proposés. Des expérimentations pour le modèle et les approches sont réalisées, afin de mesurer la performance et la robustesse des méthodes proposées. A notre connaissance, ce sont les premières contributions dans la littérature pour le SRP-CD, incluant tous les aspects abordés dans cette thèse.

Truckload transportation is a common mode of freight transportation, which accounts for a substantial portion of transportation industry, where shippers procure transportation services from carriers. Transportation service procurement is often realized by auction. Through designing effective auction mechanisms and efficient methods for solving related bid generation problems, shippers and carriers can save costs and increase profits respectively. This thesis studies three problems raised in the procurement of truckload transportation services realized by combinatorial auctions. Firstly, two two-phase combinatorial auction mechanisms are designed with supplementary bundles of requests offered for bid generated by the auctioneer and the carriers respectively in the second phase. Secondly, a column generation algorithm is proposed to solve the bid generation problem appeared in the combinatorial auction. Finally, the bid generation problem is extended to one that considers both multiple periods and uncertainty in truckload transportation service procurement. This stochastic optimization problem is formulated through scenario optimization and deterministic equivalence. To solve this model, a Benders decomposition approach is proposed.; Le transport par camions entiers est un mode courant de transport de marchandises, qui représente une part importante de l’industrie de transport, où les expéditeurs achètent des services de transport auprès des transporteurs. L'achat de services de transport est souvent réalisé par des enchères. Par concevoir des mécanismes d'enchères efficaces et des méthodes efficaces pour résoudre les problèmes de génération d'enchères associés, les expéditeurs et les transporteurs peuvent réduire leurs coûts et augmenter leurs bénéfices respectivement. Cette thèse étudie trois problèmes soulevés dans l'achat de services de transport par camions entiers réalisé par une enchère combinatoire. Premièrement, deux mécanismes d'enchères combinatoires à deux phases sont conçus avec des paquets supplémentaires de demandes offerts à l’enchère générés respectivement par le commissaire-priseur et les transporteurs dans la deuxième phase. Deuxièmement, un algorithme de génération de colonnes est proposé pour résoudre le problème de génération d'enchères apparu dans l'enchère combinatoire. Enfin, le problème de génération d’enchères est étendu à un problème qui tient compte à la fois plusieurs périodes et l'incertitude dans l'achat de services de transport par camions entières. Ce problème d'optimisation stochastique est formulé par l’optimisation de scénario et l’équivalence déterministe. Pour résoudre ce modèle, une approche de décomposition de Benders est proposée.

We study the value of information in semi-online single machine scheduling problems. We propose semi-online algorithms to solve these problems and evaluate their performances. Unlike the classical offline scheduling problems where the decision maker knows all characteristics of the instance to be scheduled, in online scheduling problems the decision-making is performed without previous information or only with partial information about the instance. Our work consists in distinguishing information that can improve the decision-making in a semi-online scheduling context from information that, even if available, does not bring any improvement. We mainly deal with semi-online problems for minimising the total completion time on a single machine. We start by studying several semi-online models with partial information on processing times of jobs. Then, we consider the problem with information on jobs release dates and finally the combination of information on processing times and jobs release dates. For each studied problem where partial information is identified as useful, we propose a semi-online algorithm integrating the information into the decision-making. We then evaluate its performance using a competitive analysis or a comparative experimental study.; Nous étudions la valeur de l’information dans des problèmes d’ordonnancement semi-online sur machine unitaire. Nous proposons ainsi des algorithmes semi-online pour résoudre ces problèmes et nous évaluons leurs performances. Contrairement aux problèmes d’ordonnancement classiques offline où le décideur connaît toutes les caractéristiques de l’instance à ordonnancer, dans les problèmes d’ordonnancement online ou semi-online la prise de décision est effectuée sans aucune information ou uniquement avec des informations partielles sur l’instance. Notre travail consiste à distinguer les informations qui peuvent améliorer la prise de décision dans un contexte d’ordonnancement semi-online des informations qui, même disponibles, n’apportent aucune amélioration. Nous traitons principalement les problèmes semi-online dont la fonction objective est la minimisation de la somme des dates de fin des tâches sur machine unitaire. Nous commençons par étudier plusieurs modèles semi-online avec des informations partielles sur les temps de traitement des tâches. Ensuite, nous considérons le problème avec une information sur les dates d’arrivée et finalement la combinaison de l’information sur les temps de traitements et les dates d’arrivée des tâches. Pour chaque problème étudié où l’information partielle est identifiée comme utile, nous proposons un algorithme semi-online intégrant l’information dans la prise de décision. Ensuite, nous évaluons sa performance à l’aide d’une analyse de compétitivité ou par étude expérimentale comparative.

This thesis, presented in view of obtaining an accreditation to supervise research, describes the research work I carried out as an assistant professor at the Université Paris Saclay during the last ten years. This work deals with the development of mixed-integer linear programming approaches for difficult deterministic and stochastic combinatorial optimization problems, mainly coming from applications in manufacturing, supply chain management and telecommunication.Part I is devoted to the work carried out on lot-sizing problems. We first study an extension of the discrete lot-sizing and scheduling problem in which the setup costs are sequencedependent and propose a new family of multi-item multi-period valid inequalities to strengthen the mathematical formulation of this problem. We then consider an important aspect of production planning, namely the fact that it is based on input data which are relative to the near futureand, as a consequence, are not always perfectly known at the time when the production plan has to be built. We thus study several stochastic programming approaches for lot-sizing. The first proposed approach assumes a rather simplified setting for the decision process. It namely considers a single-stage decision process in which the whole production plan is built before any additional information on the stochastic demand realization becomes available and cannot be updated afterward as the demand unfolds over time. We formulate this stochastic problemas a joint chance-constrained program and propose a new approximate solution approach for this problem called the partial sample approximation approach. Then, in order to further improve the modeling of the actual decision process, we investigate a multi-stage stochastic programming approach which explicitly takes into account the fact that production decisions are usually not made once and for all but rather adjusted over time according to the actual realizations of the uncertain parameters. Our main contribution consists in the development of a new algorithm capable of providing good-quality solutions for large-size instances of the stochastic single-item uncapacitated lot-sizing problem. This algorithm combines a nested decomposition algorithm called the Stochastic Dual Dynamic integer Programming (SDDiP) algorithm with a cutting-plane generation approach based on known valid inequalities. Finally, in order to extend the previous work which focuses on single-item single-echelon single-resource production systems, we consider a multi-item multi-echelon multi-resource production system linked to the remanufacturing of used products and study a multi-stage stochastic programming model for this problem. We thus present a customized branch-and-cut algorithm basedon a new family of valid inequalities for this problem.In parallel to the above-mentioned work on lot-sizing, I studied among others two applied facility location problems through industrial collaborations. The corresponding work is reported in Part II of the manuscript. We first discuss a facility location problem linked to the design of the outbound logistics network of Renault. The main contribution of this work is related to the development of a tractable heuristic solution approach for this complex large-size location-routing problem. We also investigate the placement of virtual network functions in a telecommunication network to secure it against a distributed denial-of-service attack. The main novelty here consists in the development of a new robust optimization model and adversarial algorithm for this problem.

In order to qualify quantum algorithms for industrial NP-Hard problems, comparing them to available polynomial approximate classical algorithms and not only to exact exponential ones is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highly-trusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be “less difficult” than the worst-case ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smart-charging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal’s Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios as conventional approximation algorithms or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.

Esta tesis está dedicada a un estudio en profundidad del Problema de Tarificación basado en Preferencias (del inglés, Rank Pricing Problem (RPP)) y dos generalizaciones. El RPP es un problema de optimización combinatoria que tiene como objetivo fijar el precio de los productos de una compañía para maximizar su beneficio. En él, intervienen clientes unit-demand, es decir, clientes que están interesados en varios de los productos de la empresa, pero pretenden comprar como mucho uno de ellos. Los clientes tienen un presupuesto fijo y clasifican los productos que les interesan formando un ranking del “mejor” al “peor”. Cuando la compañía fije los precios, cada cliente comprará su producto preferido de entre los que se puede permitir. En el RPP, asumimos que los productos se ofertan en cantidad ilimitada, lo cual encaja si consideramos que la compañía tiene suficientes productos para satisfacer la demanda, o cuando los productos se pueden producir rápidamente con un coste despreciable (por ejemplo, los bienes digitales). Esta tesis doctoral consta de cuatro capítulos. El primero de ellos es un capítulo de introducción al problema y a los conceptos matemáticos presentes en la tesis, mientras que los tres siguientes se centran en cada uno de los problemas estudiados: el RPP y dos generalizaciones. Así, el tercer capítulo está dedicado al estudio del Problema de Tarificación basado en Preferencias con Empates (RPPT por sus siglas en inglés, Rank Pricing Problem with Ties). En esta extensión del problema, asumimos que los clientes pueden expresar su indiferencia entre productos de su interés mediante empates en su lista de preferencia. Y el último capítulo de la tesis comprende el estudio del Problema de Tarificación Capacitado basado en Preferencias o Capacitated Rank Pricing Problem (CRPP) con envidia. En esta extensión, hemos asumido precios de reserva en los clientes que reflejan lo que están dispuestos a pagar por cada producto, en vez de un solo presupuesto por consumidor. No obstante, la principal diferencia es que en el CRPP la compañía tiene un número limitado de productos y puede no ser capaz de satisfacer la demanda de todos los clientes. El objetivo de la tesis es obtener formulaciones lineales enteras mixtas para los tres problemas estudiados, y compararlas teórica y/o computacionalmente. Para ello, la metodología empleada se basa en la propuesta de variables de decisión y restricciones apropiadas que modelicen el problema. El siguiente objetivo es la mejora de estas formulaciones mediante desigualdades válidas que reducen la región factible de la relajación del problema y permiten obtener una mejor cota de la relajación lineal. Y finalmente, un tercer objetivo es la propuesta de algoritmos de resolución para cada uno de estos modelos, y su posterior comparativa mediante la realización de estudios computacionales y resolución mediante optimizadores comerciales. En el Capítulo 2 introducimos dos formulaciones no lineales para el RPP, una que surge de una formulación binivel y otra que está formulada directamente en un solo nivel. Las comparamos teóricamente, linealizamos su función objetivo (que es la misma en ambos casos) de dos formas distintas y proponemos técnicas de preprocesamiento que reducen el tamaño de las instancias fijando variables binarias a cero o a uno. También estudiamos el problema de empaquetamiento asociado a las variables binarias del mejor modelo, con lo que probamos que esta formulación es muy fuerte porque la mayoría de las restricciones que contiene definen facetas del subproblema asociado. Los resultados computacionales son consistentes con nuestra comparación teórica, ya que muestran la superioridad del modelo uninivel. También revelan que se obtienen mejores cotas y un mejor rendimiento en general con una de las linealizaciones propuestas, que se emplea en capítulos posteriores. En el Capítulo 3, proponemos la primera formulación con variables de tres índices para el RPPT. Luego incluimos un método de resolución basado en la introducción de un modelo más débil con un conjunto de variables y restricciones de menor tamaño (el modelo de dos índices), formulación que a continuación fortalecemos añadiendo desigualdades válidas. El segundo método de resolución propuesto está basado en la descomposición de Benders, un método ampliamente utilizado para problemas enteros mixtos. Así, proponemos un Modelo de Benders válido con un conjunto de variables y restricciones pequeño, que reforzamos mediante desigualdades válidas que surgen de la resolución de los subproblemas de Benders. En los experimentos computacionales, observamos que cada uno de los algoritmos de resolución propuestos destaca en una fase de la resolución del problema. En la fase de la relajación lineal, resulta más rápida la adición de cortes en el modelo de dos índices, ya que las desigualdades se pueden separar por productos (incluso si se incluyen más cortes). En la fase entera, sin embargo, el Modelo de Benders lleva a cabo la exploración de nodos más rápido que el otro modelo, probablemente debido a su reducido número de variables y restricciones. El Capítulo 4 comienza introduciendo una formulación con variables de tres índices para resolver el CRPP. Al contrario que en los capítulos precedentes, en este se incluyen varios conjuntos de desigualdades válidas para dicha formulación que utilizan las restricciones de capacidad y nuevas variables binarias. Estos conjuntos se utilizan después cuando se proyecta el modelo de tres índices en el modelo de dos índices, por lo que las desigualdades obtenidas son más difíciles de separar porque dependen de seis conjuntos de parámetros. Además de resolver el problema de separación con Xpress, también separamos teóricamente un conjunto de desigualdades que resulta muy efectivo en la práctica, y lo relacionamos con un conjunto de cortes propuesto para el RPP. La combinación de estas desigualdades con las últimas que proponemos da como resultado un algoritmo muy eficiente que reúne las ventajas de ambas: proporciona unas de las mejores cotas de la relajación lineal y las fases de inclusión de cortes en el nodo raíz y de ramificación son muy rápidas This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g., digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies. The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. In Chapter 2, we give two nonlinear formulations for the RPP, one that comes from a bilevel formulation and another one that is directly formulated as a single-level one. We compare them theoretically, linearize their objective functions (which are the same) in two different ways and propose preprocessing techniques that effectively reduce the size of the instances by fixing variables to either zero or one. By studying the Set Packing Problem associated to the binary variables of the strongest model, we prove that this formulation is very tight, since most of its constraints are facet-defining in the corresponding subproblem. The computational results are consistent with our theoretical comparison, given that they show the superiority of the single-level model. They also disclose that one of the linearizations (used in following chapters) outperforms the other. In Chapter 3, we propose the first formulation with three-index variables for the RPPT. Next, we propose a resolution method based on the introduction of a weaker model with much less variables and constraints (the two-index model) and its strengthening by means of valid inequalities. The second resolution method is based on the Benders decomposition, a widely used approach for solving mixed-integer programs. Thus, we introduce a valid Benders Model with a small number of variables and constraints. Next, we reinforce the model dynamically adding valid inequalities obtained solving the Benders subproblems. In the computational testing, each of the resolution algorithms proposed excels in a specific phase. In the linear relaxation phase, the separation procedure designed to add valid inequalities is faster for the two-index model, since these inequalities can be separated by products. In the integer phase, however, the Benders Model outperforms the two-index model in the tree search because the node exploration is faster, probably due to the small number of variables and constraints it has. Chapter 4 begins with the introduction of a model with three-index variables for the CRPP. Unlike in the previous chapters, here the capacity constraints and the inclusion of new variables associated to the capacity allow to derive several sets of valid inequalities for the three-index formulation. These sets are then included in the projection of the three-index formulation into the two-index one, so the resultant inequalities are more difficult to separate because they depend on six sets of parameters. Besides solving the separation problem with Xpress, we theoretically separate a particular set of inequalities that proves to be very effective in practice, and link it with a family proposed for the RPP. The combination of these inequalities with the last set proposed results in a very efficient resolution method that combines the best linear relaxation gap with a rather quick inclusion of cuts in the root node and an effective node search.

Scheduling problems are combinatorial optimization problems arising in project management: the aim is to schedule tasks execution under resource constraints or precedence constraints so as to minimize a cost or maximize a gain. An integer linear programm (ILP° consists in optimizing a linear objective function over the integer points satisfying linear constraints. A lot of operation research problems can be formulated as ILP, and then be solved by commercial ILP. This thesis focuses on a single machine scheduling problem where earliness and tardiness with respect to a common due date have to be minimized. Thanks to so-called dominance properties used in the scheduling field, we propose several ILP formulation for this problem. First formulations, which are based on continuous variables similar to completion times variables (natural variables), use non-overlapping inequalities. Last formulations, which are based on binary partition variables, rely on a new type of linear inequalities that translate dominance properties.; Les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire modélisant la gestion de projets: il s’agit de planifier l’exécution de tâches, sous des contraintes de ressources ou de précédence et de manière à minimiser un coût ou maximiser un gain. On appelle programmation linéaire en nombres entiers (PLNE) l’optimisation d’une fonction linéaire sur les points entiers vérifiant un lot de contraintes linéaires. Cet outil permet de modéliser de nombreux problèmes de recherche opérationnelle, qui peuvent alors être résolus par des solveurs implémentant l’algorithme du simplexe dans un schéma de branchement et évaluation. Cette thèse porte sur l’étude d’un problème d’ordonnancement où les tâches doivent être exécutées sur une machine de manière à minimiser les pénalités d’avance et de retard par rapport à une date de fin souhaitée commune. Grâce à des propriétés dites de dominance utilisées par la communauté de l’ordonnancement, nous avons fourni plusieurs formulations PLNE modélisant ce problème. Les premières formulations, basées sur des variables continues comparables à des dates de fin, dites variables naturelles, utilisent des inégalités de non-chevauchement. Les dernières formulations, basées sur des variables booléennes de partitions, reposent sur un type nouveau d’inégalités linéaires qui traduisant des propriétés de dominance.

With the emergence of Smart Grid and communication technology between customer and supplier, there has been a growing interest in Demand Response research with different electricity pricing such as “Time-of-Use” (ToU), “Critical-Peak-Pricing”. As a response to these circumstances, we study a two-machine flow shop scheduling problem with minimization of total electricity cost (TEC) under ToU. We deal with two sub-problems. The first one tackles the joint optimization of makespan and TEC in a two-machine flow shop scheduling problem under ToU. We optimize TEC without increasing the makespan. The resolution approach is based on the theory of equivalent solutions of (F2 || Cmax) which is applied for the first time in the optimization of electricity costs. The second problem minimizes the TEC of a two machines flow shop scheduling problem with the consideration of several machine operating states under ToU. We develop a property based on Johnson’s rule to determine the optimal sequence for general ToU pricing structures. We design a new linear programming and an exact method based on the Benders decomposition to solve the problem. The numerical tests show that our proposed approach significantly improves the quality of existing results in the literature. The thesis builds a decision support tool for managers to reduce the cost of electricity in production and opens up new perspectives for energy optimization in industry.; Avec l’émergence du Smart Grid et des outils de communication entre clients et compagnies d’électricité, la réponse à la demande attire de plus en plus attentions avec des tarification d’électricité tels que « Time-of-Use » (ToU), « Critical-Peak-Pricing ». Dans ce contexte, nous menons une étude sur l’optimisation de coût d’électricité (TEC) dans le problème d’ordonnancement de flow shop à deux machines sous la tarification d’électricité ToU. Nous traitons deux sous problèmes. Le premier minimise le TEC de la solution optimale de (F2||Cmax). Nous construisons un plan de production de coût d’électricité minimal avec le makespan optimal. L’approche de résolution repose sur la théorie des solutions équivalentes de (F2||Cmax) qui sera appliquée pour la première fois dans l’optimisation de coût d’électricité. Le deuxième minimise le TEC de flow shop à deux machines avec la prise en compte de plusieurs états de fonctionnement de machines. Nous développons une proposition fondée sur la règle de Johnson pour déterminer la séquence optimale pour les structures générales de ToU. Nous concevons une nouvelle programmation linéaire et une méthode exacte fondée sur la décomposition de Benders pour résoudre le problème. Les tests numériques montrent que l’approche proposée améliore d’une manière significative la qualité des résultats existants dans la littérature. La thèse permet de construire un outil d’aide de décision au manager de réduire le coût d’électricité de production, d’ouvrir de nouvelles perspectives pour l’optimisation énergétique dans l’industrie.

In present-day logistics, reducing negative impacts on society and on the environment is a difficult challenge for companies. In transportation, the main difficulty lies in the fact that most of the fleet used for inland shipping, is composed of conventional internal combustion vehicles. Thus, in order to reduce negative environmental impacts, nowadays electric vehicles are considered a suitable option to replace conventional vehicles in last mile operations. Although usage of electric vehicles comes with many benefits, it has some disadvantages that are restricting a massive adoption. Some of the disadvantages of electric vehicles are limited mileage range, low vehicle speed, relatively long charging times, limited payload, and lack of recharging facilities. This thesis is devoted to the joint location and routing decisions where the fleet is constituted of electrical vehicles. The location decisions concern where, when and how to recharge the vehicles while the routing optimization will decide which customers to serve and in which order. The main goal of this thesis is to continue the encouragement to the transition to EVs by proposing new strategies, and solution tools for transportation, namely routing problems, in a city logistics context. Additionally to promote the transition to EVs, the problems presented in this thesis aims to tackle two issues related to the usage of EVs, the impact of the idle times caused by recharging times and the issues related to availability of recharging infrastructure., Aujourd'hui, la réduction des impacts négatifs sur la société et sur l'environnement est un défi difficile pour les entreprises. La principale difficulté réside dans le fait que la majeure partie de la flotte utilisée est composée de véhicules à combustion interne. Afin de réduire les impacts négatifs sur l'environnement, les véhicules électriques sont aujourd'hui considérés comme une option appropriée pour remplacer les véhicules conventionnels dans les opérations du dernier kilomètre. Bien que l'utilisation de véhicules électriques présente de nombreux avantages, elle présente certains inconvénients qui limitent une adoption massive. Certains des inconvénients des véhicules électriques sont une autonomie limitée, une faible vitesse, des temps de charge relativement longs, une charge utile limitée et le manque d'installations de recharge. Cette thèse est consacrée aux décisions conjointes de localisation et de routage lorsque la flotte est constituée de véhicules électriques. L'objectif principal de cette thèse est de continuer à encourager la transition vers les VE en proposant de nouvelles stratégies et des outils de solution pour le transport, appelés les problèmes de transport dans un contexte logistique urbain. En plus de promouvoir la transition vers les VE, les problèmes présentés dans cette thèse visent à aborder deux questions liées à l'utilisation des VE, l'impact des temps d'inactivité causés par les temps de recharge et les questions liées à la disponibilité de l'infrastructure de rechargement.

National audience; The problem we study is inspired by an industrial collaboration between a third-party logistics, DHL Supply Chain, and a large French restaurant chain. As part of this partnership, DHL Supply Chain coordinates the actors of a domestic logistics network composed of suppliers, warehouses and restaurants. Over a certain time horizon, the restaurants issue requests of generic products (frozen products, beverages, etc.) that are manufactured by the suppliers. The mission of DHL Supply Chain is to ensure the supply of the restaurants. For that purpose, the company determines the shipping origin of each product ordered and designs a loading plan that characterizes the routes followed by the goods. DHL Supply Chain wants to develop innovative solutions to improve its competitiveness and optimize the profitability of its logistics operations. In this thesis, we present the Logistics Service Network Design Problem (LSNDP) which form! alizes the problematic of planning transportation operations in a supply chain. Our work aims to provide methodological solutions for solving industrial instances of the LSNDP. However, these industrial instances are too complex to be solved by generic operations research methods. We thus propose several algorithms that overcome the scaling of the parameters. In particular, we develop a graph reduction heuristic, as well as a dynamic Benders strategy that adapts to the increasing number of products. Through various computational studies, we evaluate the scalability of each algorithm with respect to the considered parameter. Finally, we combine these methods for the resolution of a real case.; La problématique que nous étudions est inspirée d’une collaboration industrielle entre un prestataire logistique, DHL Supply Chain, et une grande chaîne de restauration française. Dans le cadre de ce partenariat, DHL Supply Chain coordonne les acteurs d’un réseau logistique national composé de fournisseurs, d’entrepôts et de restaurants. Les restaurants émettent, sur un horizon temporel, des demandes de produits génériques (produits surgelés, boissons, etc.) fabriqués par les divers fournisseurs. La mission de DHL Supply Chain consiste à assurer l’approvisionnement des restaurants. Pour cela, l’entreprise détermine l’origine d’expédition de chaque produit commandé, et conçoit un plan de chargement caractérisant les itinéraires suivis par les marchandises. DHL Supply Chain souhaite développer des solutions innovantes afin d’améliorer sa compétitivité et d’optimiser la rentabilité de ses opérations logistiques. Dans cette thèse, ! nous présentons le Logistics Service Network Design Problem (LSNDP) qui formalise la problématique de planification des opérations de transport dans une chaîne d’approvisionnement. Nos travaux ont pour but d’apporter des solutions méthodologiques permettant la résolution d’instances industrielles du LSNDP. Or, ces instances industrielles sont trop complexes pour être résolues par des méthodes génériques de recherche opérationnelle. Nous proposons donc plusieurs algorithmes surmontant la mise à l’échelle des différents paramètres. Nous développons notamment une heuristique de réduction de graphe, ainsi qu’une stratégie de Benders dynamique adaptée à l’augmentation du nombre de produits. À travers diverses études expérimentales, nous évaluons la scalabilité de chaque algorithme par rapport au paramètre considéré. Enfin, nous hybridons ces méthodes pour la résolution d’un cas réel.

International audience; Par une méthode de sériation appliquéè a une matrice binaire, on essaye de retrouver l'ordre chro-nologique des Prêtres d'Hélios de l'île de Rhodes à la période hellénistique. La table binaire est celle de la correspondance entre ces magistrats changés chaque année et des fabricants de vin qui exportaient leur production dans des amphores marquées de leurs deux sceaux. L'optimisation d'un critère sur l'ensemble des ordres de 205 prêtres permet d'établir une chronologie compatible avec les données archéologiques connues.

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.; Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

In the last decades, the use of renewable energy sources reduced the effect of global warming. Biomass is a promising energy resource to produce heat, electricity, and biofuel. An efficient supply chain design and optimal inventory management could contribute to reduce biofuel prices significantly and improve competitiveness with fossil fuel. This thesis addresses two crucial problems: biomass supply chain optimization and inventory control for a perishable product (biomass). The former is devoted to an issue of supplier selection and operation planning in biomass supply chains under uncertainty. This problem is formulated as a deterministic (MILP) model and a two-stage stochastic programming model. The deterministic model is solved by using a MIP solver GUROBI. An enhanced L-shaped decomposition method is developed to find an optimal solution for the stochastic model. The second deals with a stochastic inventory problem of a perishable product with uncertainty in both supply and demand. After demonstrating its optimal inventory policy is an order-to-level policy, a Lagrangian relaxation based algorithm is developed to quickly find a near-optimal solution of the problem. The stochastic inventory problem is, then, extended to a product with a fixed lifetime. The Conditional scenario method is developed to solve approximately this problem., Au cours des dernières décennies, l’utilisation de sources d’énergie renouvelables a réduit les effets du réchauffement climatique. La biomasse est une ressource énergétique prometteuse pour la production de la chaleur, de l’électricité et des biocarburants. Une conception efficace de la chaîne d’approvisionnement et une gestion optimale des stocks permettent à réduire significativement les prix des biocarburants et à améliorer la compétitivité contre des combustibles fossiles. Cette thèse aborde deux problèmes cruciaux : l’optimisation d’une chaîne logistique et la gestion des stocks périssables (biomasse). Le premier problème est consacré à la sélection des fournisseurs et la planification des opérations dans une chaîne logistique en biomasse. Ce problème est formulé sous forme de modèle déterministe (MILP) et de modèle stochastique à deux étapes. Le premier modèle est résolu de manière optimale par le solveur GUROBI. Une méthode de décomposition « L-shaped » est développée pour traiter le deuxième modèle. Le second problème consiste à la gestion des stocks d'un produit périssable sous incertitudes d’approvisionnement et de demande. Après avoir démontré que sa politique de gestion des stocks est une politique "order-up-to level", un algorithme basé sur la relaxation lagrangienne est développé pour trouver rapidement une solution quasi-optimale du problème. Ensuite, ce problème est étendu pour un produit à durée de vie fixe. La méthode « Conditional scenario » est développée pour résoudre approximativement ce problème.

Our research work was motivated by a real problem of optimizing logistics transport at the Troyes Hospital Centre (CHT). The CHT is currently involved in the review and improvement of processes and the implementation of operational research techniques in order to provide solutions to the joint problems of product transport and driver scheduling. The objective of this study is to propose effective solutions to ensure the daily transport of food trolleys, linens, pharmaceuticals and warehouse products. After the problem was formalized, we proposed a three-phase resolution approach: the first deals with the known problem of collections and deliveries with a time window and a homogeneous fleet of vehicles, the second considers a heterogeneous fleet of vehicles, and the third phase integrates the assignment and sizing of the driver team. We have resulted in the development and implementation of a decision support tool. Following our work, we have developed and implemented in partnership with the start-up OPTA-LP, a software at the CHT. Throughout our work, we have developed accurate and approximate resolution methods, and also some techniques to reduce resolution time in an accurate resolution approach, or to improve a given solution in the case of an approximate method., Nos travaux de recherche ont été motivés par une problématique réelle d'optimisation du transport logistique du Centre Hospitalier de Troyes (CHT). Le CHT s'inscrit actuellement dans la revue et l'amélioration des processus et l'implémentation des techniques de recherche opérationnelle afin d’apporter des solutions aux problèmes conjoints de transports de produits et planification des chauffeurs. L'objectif de cette étude est de proposer des solutions efficaces afin d'assurer au quotidien le transport des chariots de repas, de linge, de produits pharmaceutiques et de produits magasiniers. Après la formalisation du problème, nous avons proposé une démarche de résolution composée de trois phases : la première traite du problème connu de collectes et livraisons avec fenêtre de temps et flotte homogène de véhicules, la seconde considère une flotte hétérogène de véhicules, et la troisième phase intègre l'affectation et le dimensionnement de l'équipe des chauffeurs. Nous avons abouti au développement et à la mise en place un outil d'aide à la décision. Nous avons suite à nos travaux, développé et mis en place en partenariat avec la start-up OPTA-LP un logiciel au CHT. Tout au long de nos travaux, nous avons développé des méthodes de résolution exactes et approchées, et aussi élaborer des techniques pour diminuer le temps de résolution dans une approche de résolution exacte, ou encore pour améliorer une solution donnée dans le cas d'une méthode approchée.

In this thesis, freight buses are introduced as a new public transportation means for city logistics. Like passenger buses, freight buses are standardized vehicles with fixed routes and time schedules. With stable and accurate services provided by freight buses, both shippers and customers can flexibly arrange their order delivery times. The route planning problem of freight buses for urban distribution is studied, where each freight bus repeatedly performs a tour that leaves from a distribution center, visits multiple depots, and returns to the center. This problem is a new variant of periodic vehicle routing problem, which was never studied in the literature. We have studied three variants of the freight bus routing planning problem: the basic freight bus routing problem with only deliveries, the freight bus routing problem with both pickups and deliveries, and the freight bus routing problem with stochastic demands. For each variant of the problem, after establishing its mathematical model, we have developed a metaheuristic algorithm to solve it. These metaheuristic algorithms include a memetic algorithm, an adaptive large neighborhood search algorithm, and an immune genetic algorithm combined with scenario-based optimization for cost evaluation. The choice of each algorithm considers the characteristics of the corresponding variant of the problem studied. The relevance of the mathematical models and the effectiveness of the proposed algorithms are proved by intensive numerical experiments., Dans cette thèse, les bus de fret sont introduits comme un nouveau moyen de transport collectif pour la logistique urbaine. Tout comme les autobus, les bus de fret sont des véhicules normalisés avec les itinéraires et les horaires fixes. Grace aux services stables et précis fournis par ces bus de fret, les expéditeurs et les consommateurs peuvent organiser de manière flexible les délais de livraison et de ramassage de leurs commandes. Le problème de planification d'itinéraires de bus de fret pour la distribution urbaine est étudié, où chaque bus de fret effectue répétitivement un circuit partant d'un centre de distribution, se rendant à plusieurs dépôts et retournant au centre. Ce problème est une nouvelle variante du problème de tournées périodiques de véhicules, qui n'a jamais été étudiée dans la littérature. Nous avons étudié trois variantes du problème de planification d’itinéraires de bus de fret : le problème de base avec demandes de livraison uniquement, le problème avec ramassages et livraisons, et le problème avec demandes de ramassage et de livraison stochastiques. Pour chaque variante du problème, après avoir établi un modèle mathématique, nous avons développé un algorithme métaheuristique pour la résoudre. Le choix de chaque algorithme prend en compte les caractéristiques de la variante correspondante du problème étudiée. La pertinence des modèles et l'efficacité des algorithmes proposés sont prouvées par des expérimentations numériques intensives.

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns., Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

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., 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 Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.

The Min-up/min-down Unit Commitment Problem (MUCP), is to find a minimum-cost production plan on a discrete time horizon for a set of units producing electric power. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up and down time constraints. We show that the MUCP is strongly NP-hard, thus highlighting that the dynamic coupling of demands by minimum up and down time constraints represents one major source of difficulty. To cope with this difficulty, we introduce interval up-set inequalities, a new class of valid inequalities for the MUCP polytope, generalizing both min-up and extended cover inequalities from the 0-1 knapsack polytope. Facet defining cases are characterized and a Branch & Cut algorithm is devised. To deal with the symmetries impairing the solution process, we define sub-symmetries, as symmetries arising from a solution subset. We focus on integer linear programs whose (sub-)symmetry groups are symmetric groups acting on sub-columns of solution matrices. We propose a general framework to handle sub-symmetries in such problems. On this basis, two symmetry-breaking techniques are introduced. The first technique is an orbitopal fixing algorithm for the full (sub-)orbitope. The second technique is based on sub-symmetry breaking inequalities. Experimental results on MUCP instances show that the proposed techniques outperform state-of-the-art techniques. Finally we compare various Dantzig-Wolfe structures for the MUCP. We show that good quality lower bounds can be obtained by dualization of time-coupling constraints. Branch & Price results show that interval up-set inequalities are useful in this context.; Le Min-up/min-down Unit Commitment Problem (MUCP) consiste à trouver un plan de production de coût minimum pour un ensemble d’unités de production électrique sur un intervalle de temps discrétisé. A chaque pas de temps, la production totale doit satisfaire la demande prévue. Chaque unité respecte des temps minimum de marche et d’arrêt. Nous montrons que le MUCP est fortement NP-difficile, mettant ainsi en valeur l’impact du couplage dynamique des contraintes de demande sur la difficulté du problème. Pour appréhender cette difficulté, nous introduisons les inégalités interval up-set, généralisant les contraintes de min-up et les extended cover du sac à dos. Les facettes sont caractérisées, et un Branch & Cut est implémenté. Afin de briser les symétries du problème, nous définissons les sous-symétries comme des symétries apparaissant dans des sous-ensembles de solution. Nous considérons des PLNE dont les groupes de sous-symétrie sont des groupes symétriques agissant sur certaines sous-colonnes des matrices solutions. Nous proposons un cadre générique pour gérer les sous-symétries apparaissant dans ce type de problèmes. Deux techniques pour briser les sous-symétries sont proposées : la première est un algorithme de fixing orbitopal pour le full sub-orbitope, la seconde est basée sur des inégalités. Les résultats expérimentaux montrent que les techniques proposées sont plus performantes que les techniques de la littérature. Enfin, nous comparons différentes structures de décomposition pour le MUCP. Des bornes de bonne qualité sont obtenues par dualisation des contraintes dynamiques. Notre Branch&Price&Cut montre que les interval up-set sont utiles dans ce contexte.

Large-scale optimisation problems are usually hard to solve optimally. Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred. This thesis focuses on multi-objective local search (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself.While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms.We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.; Les problèmes d’optimisation à grande échelle sont généralement difficiles à résoudre de façon optimale. Des algorithmes d’approximation tels que les métaheuristiques, capables de trouver rapidement des solutions sous-optimales, sont souvent préférés. Cette thèse porte sur les algorithmes de recherche locale multi-objectif (MOLS), des métaheuristiques capables de traiter l’optimisation simultanée de plusieurs critères. Comme de nombreux algorithmes, les MOLS exposent de nombreux paramètres qui ont un impact important sur leurs performances. Ces paramètres peuvent être soit prédits et définis avant l’exécution de l’algorithme, soit ensuite modifiés dynamiquement.Alors que de nombreux progrès ont récemment été réalisés pour la conception automatique d’algorithmes, la grande majorité d’entre eux ne traitent que d’algorithmes mono-objectif et l’optimisation d’un unique indicateur de performance. Dans cette thèse, nous étudions les relations entre la conception automatique d’algorithmes et l’optimisation multi-objective.Nous passons d’abord en revue les stratégies MOLS possibles et présentons un framework MOLS général et hautement configurable. Nous proposons également MO-ParamILS, un configurateur automatique spécialement conçu pour gérer plusieurs indicateurs de performance. Nous menons ensuite plusieurs études sur la conception automatique de MOLS sur de multiples problèmes combinatoires bi-objectifs. Enfin, nous discutons deux extensions de la configuration d’algorithme classique : d’abord l’intégration des mécanismes de contrôle de paramètres, pour bénéficier de multiples prédictions de configuration; puis l’utilisation séquentielle de plusieurs configurations.

Production is always in perpetual evolution. Indeed, company needs to adapt its performance to market fluctuations (random requests) and internal perturbations within its systems (breakdowns, absenteeism, etc.). To cope with these uncertainties, permanent production management benefiting from the power of computer technology is fundamental. The scheduling of production is one of optimization’s tools contributing to the improvement of productivity in front of hazards. In this context, the objective is to define scheduling policies, taking into account the unavailability of resources (management of maintenance, human resources, etc.). In this thesis, we are particularly interested in the study of the two-machine job shop scheduling problems with resources not always available. The aim of our work is to propose methods for exact and approximate resolution for this type of problem, exploiting as much as possible theoretical properties for the minimization of the total completion time (makespan) which is to maximize the productivity, Dans un contexte de production en perpétuelle évolution, l’entreprise est tenue à s’adapter en permanence aux fluctuations des marchés (demandes aléatoires) et aux perturbations internes de ses systèmes (pannes, absentéisme, ...). Face à ces incertitudes, la gestion de production permanente bénéficiant également de la puissance de la technologie informatique est indispensable. L’ordonnancement des ateliers de production est l’un des axes d’optimisation contribuant à l’amélioration de la productivité face aux aléas. Il s’agit dans ce contexte de définir les politiques d’ordonnancement avec la prise en compte de l’indisponibilité des ressources (gestion de la maintenance, de ressources humaines ...). Dans cette thèse, nous nous intéressons plus particulièrement aux problèmes d’ordonnancement d’atelier à chemins multiples (Job shop) à deux machines avec des ressources non disponibles en permanence. Le but de nos travaux est de proposer des méthodes de résolution exactes et approchées pour ce type de problèmes, exploitant autant que possible des propriétés théoriques pour la minimisation du makespan qui revient à maximiser la productivité

This thesis studies Stochastic Vehicle Routing Problems (SVRPs) in the context of maintenance tasks scheduling. Stochastic programming under an A Priori paradigm is used to incorporate the uncertainties. Two SVRPs are addressed, the first one deals with Stochastic Demands which is solved by a hybrid approach combining a memetic algorithm (MA) and a Greedy Randomized Adaptive Search Procedure (GRASP). The designed hybrid method is shown to be competitive compared to other published approaches. Second, the SVRP with stochastic travel and service times and hard time windows investigated. A parallel Memetic Algorithm is designed to solve efficiently this last problem. A third problem devoted to maintenance scheduling in wind farm context is also studied in this work. First the problem is formulated as a deterministic linear bicriteria mixed integer program, then an epsilon constraint is developed to solve it. An extension to a maintenance planning problem involving a long horizon is also addressed using a simulation approach. This last part also considers maintenance strategies selection. Both developed approaches show the existing conflicts between energy production maximization and maintenance costs minimization, Cette thèse est dédiée aux problèmes de tournées de véhicules stochastiques (SVRP) abordés dans un contexte de planification de tâches de maintenance. Le paradigme de solutions À Priori est choisi pour inclure les incertitudes au moment de la planification. Deux SVRP sont étudiés, d’abord le problème avec demandes stochastiques, qui est résolu par un algorithme mémétique (MA) hybridé avec une procédure de recherche adaptative randomisée. La méthode s’est montrée compétitive en comparaison à d’autres approches disponibles dans la littérature. Ensuite le SVRP avec fenêtre de temps sur le service, et temps de trajets et de services stochastiques est considéré. Un algorithme mémétique parallèle est conçu pour le résoudre efficacement. Un troisième problème traitant de l’ordonnancement de la maintenance pour un parc d’éoliennes est étudié dans cette thèse. D’abord une version déterministe et bi-objective est modélisée sous forme d’un programme linéaire à variables mixtes, puis résolue par une méthode de type epsilon contraintes. Une extension du problème sur un horizon de planification long et considérant les stratégies de maintenance est également proposée, et le problème est résolu par une méthode basée sur la simulation. Les méthodes développées mettent en évidence, pour les deux derniers problèmes, le conflit entre la minimisation des coûts de maintenance et la maximisation de la production énergétique

The increase of the traffic flow in urban areas has a strong impact on the infrastructures of transportation networks. The situation becomes more complex whenever disruptions occur on the road networks, which often reduce the traffic capacity. This thesis comprises two major goals. The first objective consists of an academic study on Road Network problems with Disruptions and connecting requirements (RND). The other one is dedicated to the software engineering of a decision-support system, named Optimal traffic Deviation System (ODS). Depending on the network structure, RND is specialized into two problems: Unidirectional RND and Multidirectional RND. Multi-flow mathematical models are proposed for both problems, i.e. URND and MRND. Moreover, a Biased Random Key Genetic Algorithm (BRKGA) and an Iterated Local Search (ILS) metaheuristics are developed for the mono-objective RND versions, and then adaptations of these methods are proposed for the URND and MRND bi-objectives. In addition, classical bi-objective methods such as Non-dominated Sorting Genetic Algorithm II and -constraint are also developed. Results indicate mono and bi-objective ILS overcome the other methods. The decision-making system ODS is connected to heterogeneous systems for collecting the geographical data and to get a set of disruptions from Troyes city. Moreover, several constraints and optimization criteria are taken into account in the dedicated algorithms in order to propose detouring solutions, L'augmentation du flux de trafic dans des zones urbaines a un fort impact sur les infrastructures de réseaux de transport. La situation devient encore plus compliquée lorsqu’il y a des interruptions qui perturbent la circulation. Dans cette thèse, deux objectifs majeurs sont ciblés : le premier consiste à l’étude du problème de conception de réseau routier avec des interruptions tout en assurant la forte connexité du réseau (RND) ; le second porte sur le développement du système d’aide à la décision : Optimal traffic Deviation System (ODS). En fonction de la nature du réseau, RND est spécialisé en Unidirectionnel RND et Multidirectionnel RND. Des modèles mathématiques multi-flot sont proposés pour ces problèmes. De plus, des méta-heuristiques du type Biased Random Key Genetic Algorithm (BRKGA) et Iterated Local Search (ILS) sont développées pour les problèmes en versions mono-objectif. Des adaptations pour ces méthodes sont ensuite proposées pour traiter les problèmes en version bi-objectif. En outre, des méthodes multi-objectif classiques sont également développées, telles que la méthode -constraint et Non-dominated Sorting Genetic Algorithm II. Les résultats numériques indiquent que l’ILS dans les versions mono et bi-objectif produit les meilleurs résultats que les autres méthodes. Enfin, le système ODS est connecté à des systèmes hétérogènes de données géographiques et à la base des arrêtés municipaux de la ville de Troyes, incluant plusieurs contraintes, critères d’optimisation et algorithmes dédiés permettant de proposer des déviations

Biomass can play a crucial role as one of the main sources of renewable energies. As logistics holds a significant share of biomass cost, efficient biomass supply chains must be designed to provide bio-refineries with adequate quantities of biomass at reasonable prices and appropriate times. This thesis focuses on modeling and optimization of multi-biomass supply chains for several bio-refineries. A data model is developed to list, analyze and structure the set of required data, in a logical way. The result is a set of tables that can be loaded into mathematical models for solving optimization problems. Then, a multi-period mixed integer linear programming model is proposed to optimize a multi-biomass supply chains for several bio-refineries, at the tactical and strategic level. Refineries can be already placed or located by the model. The aim is to minimize the total costs, including biomass production, storage, handling, refineries setup and transportation costs, while satisfying the demand of refineries in each period. Additionally, a multi-objective model is developed to optimize simultaneously the economic and environmental performance of biomass supply chains. The model is solved by using the ε-constraint method. Furthermore, large-scale tests on real data for two regions of France (Picardie & Champagne-Ardenne) are prepared to evaluate the proposed models. Finally, two-phase approaches are proposed to solve large-scale instances in reasonable running times, while evaluating the loss of optimality compared to the exact model, La biomasse peut jouer un rôle crucial comme source d'énergie renouvelable. La logistique représentant une part importante du coût, des chaînes d'approvisionnement efficaces doivent être conçues pour fournir aux bio-raffineries les quantités demandées, à des prix raisonnables et à des moments adéquats. Cette thèse porte sur la modélisation et l'optimisation de chaînes logistiques de biomasse pour plusieurs raffineries. Un modèle de données est élaboré pour structurer les informations nécessaires à une base de données alimentant les modèles mathématiques. Ensuite, un modèle linéaire multi-période à variables mixtes est proposé pour optimiser au niveau tactique et stratégique une chaîne logistique multi-biomasse. Les emplacements des raffineries peuvent être prédéfinis ou déterminés par le modèle. L'objectif est de minimiser un coût total incluant la production de biomasse, le stockage, la manutention, la création des raffineries et le transport, tout en satisfaisant les besoins des raffineries dans chaque période. Une version multi-objective est développée pour optimiser simultanément des critères économiques et environnementaux. Elle est résolue par une méthode de type ε-contrainte. Des grandes instances avec des données réelles pour deux régions de France (Picardie et Champagne Ardenne) sont préparées pour évaluer des modèles proposés. Enfin, des approches en deux phases sont appliquées pour résoudre les grands cas en un temps raisonnable, tout en évaluant l’écart à l’optimum fourni par la méthode exacte

Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs.For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases.The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.; L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs.

Our research focuses on the optimization of the activities of a hospital emergency department in order to improve the quality of services offered to patients. We have decomposed our approach into two areas: demand forecasting and optimization of activities. The first axis consists in forecasting the daily inflow of patients into the department. To this end, a new emergency classification of emergency patients, named EP, is introduced, taking into account the medical resources needed to treat the patient and post-emergency affiliation. We developed predictive models to forecast the daily inflow by EP class in the long-term and short-term. The second axis is to optimize service activities to minimize the average waiting time of patients in the service. To achieve this purpose, a system performance evaluation tool based on discrete event simulation was developed. This tool allowed us to evaluate the average waiting time of patients for different organizations of the service. Afterwards, we focused on optimizing the allocation of human resources (doctors, interns, nurses and caregivers). A meta-heuristic approach has been developed to solve the problem, since the objective function is not linear, which is based on the coupling of a genetic algorithm with the simulation model to evaluate the solutions. This approach also optimizes service in the future by injecting patient forecasts into the simulator, Notre travail de recherche traite la problématique de l’optimisation des activités d’un centre d’urgences hospitalières dans le but d’améliorer la qualité des services offerts aux patients. Nous avons décomposé notre approche en deux axes : prévision de la demande et optimisation des activités. Le premier axe consiste à prévoir l’afflux journalier des patients dans le service. Pour cela, on a introduit une nouvelle classification pratique des patients des urgences, qu’on a nommé EP, qui prend en considération la charge des soins nécessaires au traitement du patient et l’affiliation après le passage dans le service des urgences. Ensuite, on a développé des modèles de prévision adaptés pour prédire l’afflux quotidien par classe d’EP à long terme et à court terme. Le deuxième axe consiste à optimiser les activités du service pour minimiser le temps moyen d’attente dans le service. Pour y parvenir, on a développé, dans un premier temps, un outil d’évaluation des performances du système basé sur la simulation à évènements discrets. Cet outil nous a permis d’évaluer le temps d’attente moyen des patients pour différentes organisations du service. Par la suite, on s’est intéressé à l’optimisation de l’affectation des ressources humaines du service (médecins, internes, infirmières, aides-soignants). Pour cela, on a développé une approche méta-heuristique qui se base sur le couplage d’un algorithme génétique avec le modèle de simulation. Cette approche permet également l’optimisation du service dans le futur en injectant les prévisions des patients dans le simulateur

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.; 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.; 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.

Thesis of "habilitation à diriger des recherches" about the question of flexibility in combinatorial optimization and some answers through declarative hybrid decomposition approaches, including global constraints in constraint programming and decomposition methods in mixed integer linear programming.

Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of terminals, and a weight function w, associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-terminal vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-terminal vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-terminal vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.; Étant donné un graphe G = (V U T, E), tel que V U T représente l'ensemble des sommets où T est un ensemble de terminaux, et une fonction poids w associée aux sommets non terminaux, le problème du séparateur de poids minimum consiste à partitionner V U T en k + 1 sous-ensembles {S, V1,..., Vk} tel qu'il n'y a aucune arête entre deux sous-ensembles différents Vi et Vj, chaque Vi contient exactement un terminal et le poids de S est minimum. Dans cette thèse, nous étudions le problème d'un point de vue polyèdral. Nous donnons deux formulations en nombres entiers pour le problème, et pour une de ces formulations, nous étudions le polyèdre associé. Nous présentons plusieurs inégalités valides, et décrivons des conditions de facette. En utilisant ces résultats, nous développons un algorithme de coupes et branchement pour le problème. Nous étudions également le polytope des séparateurs dans les graphes décomposables par sommets d'articulation. Si G est un graphe qui se décompose en G1 et G2, alors nous montrons que le polytope des séparateurs dans G peut être décrit à partir de deux systèmes linéaires liés à G1 et G2. Ceci donne lieu à une technique permettant de caractériser le polytope des séparateurs dans les graphes qui sont récursivement décomposables. Ensuite, nous étudions des formulations étendues pour le problème et proposons des algorithmes de génération de colonnes et branchement ainsi que des algorithmes de génération de colonnes, de coupes et branchement. Pour chaque formulation, nous présentons un algorithme de génération de colonnes, une procedure pour le calcul de la borne duale ainsi qu'une règle de branchement. De plus, nous présentons quatre variantes du problème du séparateur. Nous montrons que celles-ci sont NP-difficiles, et pour chacune d'elles nous donnons une formulation en nombres entiers et présentons certaines classes d'inégalités valides.

The work presented in this thesis concerns the formulation and the resolution of two holistic multi-objective optimization problems associated with the selection of the best product and hybrid assembly line configuration out of a set of products, processes and resources alternatives. Regarding the first problem, a cost model was developed in order to translate the complex interdependencies between the selection of specific product designs, processes and resources characteristics. An empirical study is proposed, which aimed at comparing, according to several multi-objective quality indicators, various resolution methods – including variants of evolutionary algorithms, ant colony optimization, particle swarm optimization, bat algorithms, cuckoo search algorithms, and flower-pollination algorithms. Several dominance rules and a problem-specific local search were applied to the most promising resolution methods. Regarding the second problem, which also considers the buffer sizing, the developed algorithms were enhanced with a genetic discrete-event simulation model, whose primary function is to evaluate the value of the various objective functions. The demonstration of the associated resolution frameworks for both problems was validated through two industrial-cases., Le travail présenté dans cette thèse concerne la formulation et la résolution de deux problèmes d'optimisation multi-objectifs. Ces problèmes de décision, liés à une approche holistique, ont pour but de sélectionner la meilleure configuration « produit/ligne d’assemblage » à partir d'un ensemble de design produits, et de ressources. Concernant le premier problème, un modèle de coût a été développé afin de traduire les interdépendances complexes entre la sélection d’un design produit et les caractéristiques des ressources. Une étude empirique est proposée et vise à comparer, selon plusieurs indicateurs de qualité multi-objectifs, différentes méthodes de résolution - comprenant des algorithmes génétiques, de colonies de fourmis, d’optimisation par essaims particulaires, des chauves-souris, de recherche du coucou et de pollinisation des fleurs. Plusieurs règles de dominance et une recherche locale spécifique au problème ont été appliquées aux méthodes de résolution les plus prometteuses. Concernant le second problème, qui se penche également sur le dimensionnement des stocks tampons, les méthodes de résolution sont à un modèle de simulation à événements discrets, dont la fonction première est l’évaluation des valeurs des différentes fonctions objectives. L’approche holistique associée aux deux problèmes a été validée avec deux cas industriels.

This manuscript presents the synthesis of research works in optimization and simulation with the aim of developing flexible and performant software tools. The contributions are centered on three main domains:(i) combinatorial optimization, with the resolution of problems of hypermedia documents synchronization and resources optimization in cloud computing;(ii) numerical simulation, with an original outline of optimization-simulation coupling for solving a bus routing design problem in an urban transportation network, and a methodology to minimize the vulnerability of a grassland ecosystem facing climate changes;(iii) generic software development, with design patterns for developing optimization algorithms, and a library to extend generic programming to "concepts" and thus to allow improving the quality of computer codes.This multidisciplinary approach is explained by the complementarity of these domains when tackling the studied problems. Notably, combinatorial optimization allows designing very efficient algorithms to solve operational research problems, but is based on a usually too simplistic modeling of the studied system. Numerical simulation, which generally allows representing more precisely the system, can be coupled with the optimization process to identify better applicable solutions.The studied systems can also be very complex and can need extremely time-consuming optimization algorithms and simulation models. Software development becomes thereby a crucial element where usual software engineering methods are not always enough to meet high performance computing needs. It seems thus relevant to study the possibilities offered by generic programming and metaprogramming to combine, with few compromises, flexibility and performance in computer codes., Ce manuscrit présente la synthèse de travaux de recherche en optimisation et simulation dont l’objectif est le développement d’outils logiciels flexibles et performants. Les contributions s’articulent autour de trois grands domaines:(i) l’optimisation combinatoire, avec la résolution de problèmes de synchronisation de documents hypermédia et d’optimisation de ressources dans les nuages informatiques;(ii) la simulation numérique, avec un schéma de couplage optimisation-simulation original pour la résolution d’un problème de conception de tournées de bus dans un réseau de transport urbain, et une méthodologie pour la minimisation de la vulnérabilité d’un écosystème prairial face aux changements climatiques;(iii) le développement logiciel générique, avec des patrons de conception pour le développement d’algorithmes d’optimisation, et une bibliothèque pour étendre la programmation générique aux "concepts" et permettre ainsi d’améliorer la qualité des codes de calcul.Cette démarche pluridisciplinaire s’explique par la complémentarité de ces domaines pour répondre aux problématiques étudiées. Notamment, l’optimisation combinatoire permet l’élaboration d’algorithmes très efficaces pour résoudre des problèmes de recherche opérationnelle, mais en s’appuyant sur une modélisation souvent trop simpliste du système étudié. La simulation numérique, qui permet généralement une représentation plus fine du système, peut être couplée au processus d’optimisation afin d’identifier de meilleures solutions applicables.Les systèmes étudiés peuvent aussi être très complexes et nécessiter des algorithmes d’optimisation et des modèles de simulation très coûteux en temps de calcul. Le développement logiciel devient alors un élément crucial où les méthodes usuelles de génie logiciel ne sont pas toujours suffisantes pour répondre aux besoins de calcul intensif. Il semble alors pertinent d’étudier les possibilités offertes par la programmation générique et la métaprogrammation pour combiner, avec peu de compromis, flexibilité et performance dans les codes de calcul.

In this thesis, we deal with the production planning problem in a flow-shop system with energy consideration. The manufacturing system is composed of reliable machines separated by buffers with infinite capacities. The planning horizon is defined by a set of periods where each one is characterized by a length, an electricity price, a maximal allowed power and an external demand of each product. The purpose is to minimize the total production cost composed of electricity, inventory, set-up (or product series change) costs and a required power per period.In the first step, we propose mathematical models for a single item capacitated lot-sizing problem in a flow-shop system. Since this problem is known to be NP-hard, approximating methods are developed in order to provide solutions with good quality in a reasonable time (dedicated heuristics, Fix and Relax heuristic, genetic algorithm).In the second step, a generalization of the model for multi-items is considered. Similarly to the first case, approximating methods are proposed to solve this problem; Dans cette thèse, nous abordons le problème de la planification de la production dans un système de type flow-shop, en tenant compte de l’aspect énergétique. Le système de production est composé de différentes machines fiables, séparées par des zones de stockage à capacité infinie. L’horizon de planification est composé de différentes périodes, chacune étant caractérisée par une durée, un coût d’électricité, une puissance maximale et des demandes de chaque produit. L’objectif consiste en la minimisation du coût total de production en terme d’électricité, stockage, mise marche (ou changement de série) et puissance demandée par période. Dans un premier temps, nous proposons une modélisation pour le problème de lot-sizing dans un système de type flow-shop, à capacité finie, dans le cas mono-produit. Étant donné que ce type de problème est NP-difficile, des méthodes approchées ont été développées afin de fournir des solutions de bonne qualité dans un temps réduit (heuristiques dédiées, heuristique de type Fix and Relax, algorithme génétique). Dans un deuxième temps, une généralisation du modèle pour le cas multi-produits a été considérée. De même, des méthodes approchées ont été proposées pour la résolution de ce type de problème

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; 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

International audience

The research works of this thesis address the problem of modeling and optimizing biomass supply chains for biorefineries. Indeed, efficient supply chains are essential to provide conversion facilities with sufficient quantities of quality biomass at reasonable prices. The problem is described and modeled.A network model and a data model are developed to allow to describe the structure of the supply chain and its data, without affecting the underlying mathematical model. The latter is a mixed-integer linear programming that combines for the first time various aspects, either original or tackled separately in the literature. For given refinery needs, its exact resolution by CPLEX specifies the logistic activities in the network (amounts harvested, baled, transported, stored etc.) and the necessary equipment, in order to minimize a total cost including harvesting costs, transport costs and storage costs. Case studies are described to illustrate this multi-biomass and multi-period tactical planning model.A more compact model is also elaborated to cope with large-scale instances. It is illustrated using a real case study for a bio-refinery planned near Compiègne, France.Finally, the developments conducted for the implementation of a prototype of decision-support application are presented and recommendations for coming to a commercial software are proposed, Les travaux de cette thèse concernent la modélisation et l'optimisation de chaînes d’approvisionnement en biomasses pour de futures bio-raffineries. En effet, des chaînes d'approvisionnement efficaces sont essentielles pour fournir aux installations de conversion, de façon régulière, des quantités suffisantes de biomasse de qualité à des prix raisonnables. Le problème est tout d'abord décrit puis modélisé.Un modèle de réseau et un modèle de données sont ensuite développés pour permettre de décrire la structure de la chaîne d'approvisionnement et ses données, sans affecter le modèle mathématique sous-jacent. Ce dernier (MILP) combine pour la première fois divers aspects, soit originaux, soit gérés séparément dans la littérature. A partir des demandes de la raffinerie, une résolution exacte précise les activités logistiques dans le réseau et les équipements nécessaires, afin de minimiser le coût total composé des coûts de récoltes, de transport et de stockage. Des études de cas sont décrites pour illustrer ce modèle de planification tactique multi-biomasse et multi-période. Un modèle plus compact est aussi élaboré pour traiter des instances de très grandes tailles. Il est illustré par une étude de cas réelle pour une bio-raffinerie prévue près de Compiègne. Pour finir, les développements effectués pour la mise en place d’un prototype logiciel d’aide à la décision sont présentés et des recommandations d’un futur logiciel commercial sont proposées

Nowadays, transportation has become an indispensable part in modern life. However, heavy traffic congestion due to high urbanization and rapid increase of vehicles has caused low transportation efficiency and huge amounts of urban pollution. In this context, to meet special transportation requirements and improve the performance of transportation systems, lane reservation, as a flexible and economic traffic management strategy, has been widely implemented in real life. The majority of studies about lane reservation in the literature focus on the impact at a microscope level, e.g., a single link or corridor.In this thesis, we focus on optimally reserving lanes at a macroscopic network level with the objective of minimizing negative impact for two categories of problems. We firstly investigate the large-size and robust lane reservation problems in the contexts of future automated truck freight transportation and large-scale special events. Then, we study lane reservation for improving the performance of bus transit system under different assumptions. For all problems studied in this thesis, appropriate models are provided and their complexities are analyzed. Different resolution approaches are developed according to the characteristics of problems, including exact two-phase method, exact epsilon-constraint based method, cut-and-solve method, and kernel search method. The performance of the proposed algorithms is evaluated by benchmark and randomly generated instances. Extensive numerical experiments show the proposed algorithms outperform the state-of-the-art algorithms and the commercial software CPLEX., Aujourd'hui, le transport est devenu indispensable dans la vie quotidienne. Cependant, la congestion du trafic du fait de la forte urbanisation et de l'augmentation rapide du nombre de véhicules a réduit l'efficacité du système de transport et a causé d'énorme pollution urbaine. Dans ce contexte, pour répondre aux besoins spécifiques de transport et améliorer la performance des systèmes de transport, la réservation de voie, en tant que stratégie de gestion du trafic flexible, a été largement mise en œuvre. La majorité des études existantes sur la réservation de voie se focalisent au niveau microscopique, par exemple, un segment de route principale. Dans cette thèse, nous nous concentrons sur la réservation optimale des voies dans un réseau de transport au niveau macroscopique en minimisant son impact négatif pour deux catégories de problèmes. Nous étudions d'abord des problèmes de réservation robuste de voie et de grande taille pour les futurs poids lourds intelligents et les grands événements spéciaux. Ensuite, nous étudions la réservation de voie dans le but d'améliorer la performance du transport public avec des hypothèses spécifiques. Pour chaque problème étudié dans cette thèse, des modèles appropriés sont construits et leurs complexités sont analysées. Différentes approches de résolution sont élaborées en fonction des caractéristiques des problèmes, à savoir : une méthode exacte à deux phases, une méthode de epsilon-contrainte, une méthode de "cut-and-solve", et une méthode de "kernel search". La performance des algorithmes proposés est évaluée à l'aide de benchmarks et d'instances générées aléatoirement. Les expériences numériques montrent que les algorithmes proposés sont plus performants que les algorithmes existant dans la littérature et le progiciel commercial CPLEX.

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.; 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.; 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.

Constraint programming is an approach regularly used to treat a variety of scheduling problems. Cumulative scheduling problems represent a class of problems in which non-preemptive tasks can be performed in parallel. These problems appear in many contexts, such as for example the allocation of virtual machines, the ordering process in the "cloud", personnel management or a port. Many mechanisms have been adapted and offered in constraint programming to solve scheduling problems. The various adaptations have resulted in reasoning that appear a priori significantly different. In this thesis we performed a detailed analysis of the various arguments, offering both a theoretical unified caracterization but also dominance rules, allowing a significant improvement in execution time of algorithms from the state of the art, up to a factor of seven. we also propose a new framework for robust cumulative scheduling, to find solutions that support at any time one or more tasks to be delayed while keeping a satisfactory end date of the project and without calling into question the generated scheduling. In this context, we propose an adaptation of an algorithm of the state of the art, Dynamic Sweep.; La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port. De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement. Les différentes adaptations ont abouti à des raisonnements qui semblent à priori significativement distincts. Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep.

This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem.; Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale.