Integration flows are increasingly used to specify and execute data-intensive integration tasks between heterogeneous systems and applications. There are many different application areas such as near real-time ETL and data synchronization between operational systems. For the reasons of an increasing amount of data, highly distributed IT infrastructures, as well as high requirements for up-to-dateness of analytical query results and data consistency, many instances of integration flows are executed over time. Due to this high load, the performance of the central integration platform is crucial for an IT infrastructure. With the aim of throughput maximization, we propose the concept of multi-flow optimization (MFO). In this approach, messages are collected during a waiting time and executed in batches to optimize sequences of plan instances of a single integration flow. We introduce a horizontal (value-based) partitioning approach for message batch creation and show how to compute the optimal waiting time. This approach significantly reduces the total execution time of a message sequence and hence, it maximizes the throughput, while accepting moderate latency time.

Dans ce travail nous considérons des problèmes de planification de production sur plusieurs sites avec transport de produits entre ces sites. L’objectif est de synchroniser les deux problèmes (planification et transport) et de construire une solution globale. Le système de production sur chaque site est modélisé comme un problème de Capacitated Lot-Sizing où nous travaillons avec stock et ressources. Le transport de produits entre les sites se ramène à une version simplifiée du Vehicle Routing Problem où le temps est discrétisé. D’abord nous proposons un modèle linéaire en nombres entiers que nous appelons le « Lot-Sizing and Vehicle Routing Problem » (LSVRP). Puis nous présentons deux cas particuliers : le Single-item LSVRP (SLSVRP) et le Single-level LSVRP (1-LSVRP). Les problèmes sont traités ici par six heuristiques que nous avons développé. Quatre de ces méthodes sont des heuristiques qui utilisent la programmation en nombres entiers et prennent en compte la relaxation linéaire de quelques variables du problème. Elles s’appuient sur l’exploration partielle de l’arbre de décision et la fixation de variables. Les deux autres sont spécifiques pour les cas particuliers. La première, qui traite le S-LSVRP, est basée sur la propagation des ordres de production sur chaque site. Puis à chaque itération elle calcule le plan de transport compatible et essaie d’améliorer la solution en modifiant la production sur les sites. L’autre méthode consiste en une relaxation lagrangienne qui travaille sur une modélisation du 1-LSVRP en un problème de flot. Des résultats numériques et des analyses sont présentés pour évaluer l’efficacité de ces heuristiques. / In this work we consider some problems of scheduling both a production distributed on several sites and the transportation of items between those sites. By doing so, the objective is to synchronize the two components and to build a better overall solution. The production system on each site is modeled as a Capacitated Lot-Sizing Problem where stock both on resources and produced items is available. The inter-site items transportation is a simplified version of the Vehicle Routing Problem where time is discretized. We first propose a mixed integer linear programming formulation that we call “The Lot-Sizing and Vehicle Routing Problem” (LSVRP). Then we present two particular cases : The Single-item LSVRP (S-LSVRP) and The Single-level LSVRP (1-LSVRP). All those cases are treated here by the six heuristics we develloped. Four of those methods are MIP based heuristics and take in account the the linear relaxation of some variables of the problem. They rely on partial decision tree exploration along with variable fixing. The other two are specifics for the two particular cases. The one who treats the S-LSVRP is based on production order propagation over the sites. Then, at each iteration, it computes a compatible transportation schedule and it tries to improve the solution by modifying the production on the sites. The other method consists in a lagrangian relaxation that works with an adaptation of the 1-LSVRP into a flow problem. Computational results and analysis are presented to evaluate the efficiency of those heuristics.

Le but de ce travail est l'étude du problème de gestion de flot de conteneurs et de véhicules dans un réseau multimodal. Nous proposons une formulation du problème sous forme d'un modèle mathématique réaliste qui prend en considération les différents aspects liés au transport et au stockage des conteneurs et dont l'objectif est de minimiser le coût global de transport. Pour la résolution des grandes instances une approche de résolution bi-niveaux est proposée. Dans un premier niveau nous construisons un modèle agrégé plus facile à résoudre pour en extraire les décisions liées aux déplacements des trains et des barges ainsi qu'une borne duale de notre problème de base. Ces informations sont utilisées dans un deuxième niveau pour avoir des solutions de bonne qualité de notre problème par rapport aux solutions données par CPLEX en résolvant directement le modèle de base. Des résultats numériques sur des instances générées aléatoirement sont présentés et ils prouvent l'intérêt de l'approche de résolution proposée dans cette thèse. / The aim of this work is the study of the problem of managing the flow of containers and vehicles in a multimodal network. We propose a formulation of the problem under the form of a realistic mathematical model that takes into account the different aspects related to container transport and storage and whose objective is to minimize the overall cost of transport. For large-scale resolution, a two-level resolution approach is proposed. In a first level we build an aggregated model easier to solve to extract the decisions related to the movements of trains and barges as well as a dual terminal of our basic problem. This information is used in a second level to have good quality solutions of our problem compared to the solutions given by CPLEX by directly solving the basic model. Numerical results on randomly generated instances are presented and prove the value of the proposed resolution approach.

Les nouveaux acteurs, les nouveaux services et les nouveaux contenus multimédias qui transitent sur le réseau internet génèrent un trafic et des débits de plus en plus élevés. Ceci peut occasionner une congestion, source de latence et de dépréciation de la qualité de service ressentie par les utilisateurs. Un fournisseur d'accès à internet dont l'objectif est de garantir un réseau d'excellence doit donc prendre des mesures pour améliorer sans cesse la fluidité de son réseau. Cela passe notamment par la mise en place d'un réseau de distribution de contenus (déploiement de dispositifs sur le réseau existant). Dans un premier temps cette thèse s'articule à présenter des approches de programmation dynamique de localisation de serveurs optimales dans des arborescences. Nous présentons également un approche pour résoudre le problème de déploiement de CDN et de k serveurs/caches à l'aide de l'algorithme exact et polynomial d'intersection de matroïdes. Nous explicitons ensuite ce qu'est un cache et quelles sont ses caractéristiques. Nous définissons ensuite les hypothèses effectuées et la modélisation associée pour le déploiement de caches transparents dans une arborescence, et le liens avec les algorithmes existants présentés précédemment. Nous présentons alors un modèle complet pour un programme linéaire en nombres entiers (PLNE) et un nouveau paradigme de programmation dynamique pour résoudre ce même problème. Nous montrons alors en quoi cette approche se généralise à des problèmes connexes de localisation dans les arborescences, ainsi que les performances pratiques d'une telle approche. D'un regard plus théorique, nous mesurons la capacité d'un réseau donné par le routage optimal de ses demandes, et, de ce fait, ses liens critiques. Nous manipulons alors le problème de flot concurrent maximal (FCM), un problème classique de la littérature de recherche opérationnelle. Nous exhibons alors de nouvelles formulations exactes pour résoudre ce problème, ainsi que les problèmes de multi-flots de manière plus générale. Une heuristique de construction de formulation pour le FCM est également proposée, pour tirer parti de la distribution spécifique des capacités d'une instance. Nous montrons alors la supériorité des performances de ces nouvelles formulations par le biais de comparaisons. Enfin, nous décrivons le premier algorithme exact et fortement polynomial pour résoudre le problème de flot concurrent maximal dans le cas d'une seule source; et nous montrons l'efficacité pratique d'une telle approche, comparée aux meilleures formulations explicitées précédemment / Streaming requirements on internet network are even more driven by new actors, new services and new digital contents. This leads to high probability of congestion, latency and therefore, a critical decrease of quality of service and/or experience for customers. An internet service provider (ISP) whose goal is to guarantee a first-class performance, needs to take measures to constantly enhance the fluidity of the traffic streaming on its network. One way to face the problem, is to build a Content Delivery Network (CDN). A CDN mainly consists in the deployment of different devices on an existing network. First of all, this thesis presents dynamic programming approaches to tackle server location problems in tree networks. Then, we address a variation of the matroïd intersection algorithm to solve the k-server/cache location problem. We start by giving the definition and characteristics of transparent-caching, as well as the hypothesis that we will use it to build models for transparent cache location in tree network. We tract it to a Mixed Integer Program, and formulate a new paradigm of dynamic programming. We show the relevance of such approach for our problem, and to what extent it can be tractable in other related problems. From a more theoretical point of view, we manage to measure the capacity of a network which is given by the optimal routing strategy, and hence, to identify its critical links. We deal with the Maximum Concurrent Flow (MCF), a classical combinatorial optimization problem. We propose new models and formulations to solve this problem exactly, and more general multi-flows problems as well. A heuristic is also given, to adapt the model to the specific instance values. We experiment these formulations to show the improvements they can provide. Finally, we describe the first strongly polynomial algorithm to solve the maximum concurrent flow to optimality, in the single source case. We show the efficiency of such an approach, even compared to the best models previously presented