Letteratura scientifica selezionata sul tema "Ordonnancement multiagent"

Les travaux de cette thèse proposent un pont entre les méthodes d'optimisation et les problèmes d'ordonnancement de travaux multiressources et à intervalle fixe sur machines parallèles identiques. Les "problèmes d'ordonnancement monocritère" et "problèmes d'ordonnancement multiagent" sont considérés. Nous développons un panel d'ordonnanceurs basés sur des méthodes exactes et approchées pour déterminer des solution réalisables où l'objectif est de maximiser la somme totale pondérée des travaux ordonnancés (ou équivalent, minimisant le coût total pondérée des travaux rejetés), durant un horizon de planification. L'application des méthodes d'optimisation exactes s'avère illusoire dans la pratique en raison du temps de calcul, plus particulièrement lorsqu'il s'agit des systèmes distribués. En revanche ces méthodes exactes serviront comme références pour évaluer les méthodes approchées.La première partie est consacrée à l'étude des problèmes d'ordonnancement monocritère. Après l'analyse de complexité, trois programmes linéaires en nombres entiers (PLNEs), un modèle basé sur la programmation par contrainte (PPC), une méthode hybride entre la PPC et un PLNE sont proposés pour résoudre à l'optimum le problème d'ordonnancement. Nous développons également une méthode exacte de type génération de colonnes basée sur la décomposition de Dantzig-Wolfe qui nous conduit à proposer un algorithme de type Branch & Price. Branch & Price offre de meilleures performances que les autres méthodes exactes sur des instances allant jusqu'à 150 travaux. Pour résoudre des instances de très grandes tailles, des heuristiques de liste basées sur des règles de priorité sont proposées. Afin d'éviter les choix myopes de ces algorithmes gloutons, nous introduisons une heuristique constructive PILOT combinant deux ou plusieurs règles d'ordonnancement et d'affectation ainsi qu'un algorithme évolutionnaire (AE). Les résultats expérimentaux mettent en évidence les performances de PILOT et AE.La seconde partie de nos travaux est dédiée à l'étude de l'ordonnancement multiagent des travaux multiressources à intervalle fixes. Ce modèle considère plusieurs agents associés à des sous-ensembles de travaux disjoints, chacun d'eux cherche à maximiser la somme totale pondérée de ses travaux ordonnancés. Les trois approches suivantes sont considérées : combinaison linéaire des critères, l'approche epsilon-contrainte et l'énumération de l'ensemble des optima de Pareto. Après une analyse de la complexité des problèmes étudiés, des programmes dynamiques polynomiaux ont été développés pour résoudre des cas particuliers. Les fronts optimaux de Pareto sont obtenus par l'approche epsilon-contrainte utilisant le PLNE, la méthode hybride PPC & PLNE ou encore la méthode Branch & Price. Les résultats des expérimentations montrent que les méthodes exactes sont beaucoup moins performantes. Pour résoudre des problèmes de grande taille, des heuristiques de liste et une méthode évolutionnaire de type NSGAII sont développées. Toutes ces méthodes ont été implémentées et testées
The work of this thesis deals with optimization methods and scheduling problems of multiresource and fixed-interval jobs on identical parallel machines. Both "monocriterion scheduling problems" and "multiagent scheduling problems" are considered. We develop a panel of schedulers based on exact and heuristic methods to determine feasible solutions where the objective is to maximize the total weighted sum of scheduled jobs (or equivalently, minimizing the total weighted cost of rejected jobs), during a scheduling horizon. The application of exact optimization methods proves to be illusory in practice due to the computational time, especially when dealing with distributed systems. On the other hand, these exact methods will be used as references to evaluate the heuristic methods.The first part is devoted to the study of monocriterion scheduling problems. After the complexity analysis, three integer linear programs (ILPs), a model based on constraint programming (CP), a hybrid method between CP and a ILP are proposed to solve optimally the scheduling problem. We also develop a column generation method based on the Dantzig-Wolfe decomposition which leads us to propose a Branch & Price algorithm. Branch & Price outperforms other exact methods (solves instances up to 150 jobs). To solve very large instances, heuristics based on priority rules are proposed. To avoid the myopic choices of these greedy algorithms, we design a constructive PILOT heuristic combining two or more scheduling and assignment rules and an evolutionary algorithm (EA). Experimental results highlight the performance of PILOT and AE.The second part of our work is dedicated to the study of multi-agent scheduling problem of fixed intervals multiresource jobs. This model considers several agents associated with disjoint subsets of jobs, each of which seeks to maximize the total weighted of its scheduled jobs. The following three approaches are considered: linear combination of criteria, the epsilon-constraint approach and the enumeration of the set of optimal Pareto solutions. After an analysis of the complexity of the studied problems, polynomial dynamic programming algorithms have been developed to solve particular cases. The optimal Pareto fronts are obtained by the epsilon-constraint approach using the ILP, the hybrid PPC & ILP or the Branch & Price method. Experimental results show that the exact methods are less efficient. To solve large problems, heuristics and an evolutionary methods (NSGA-II) are developed. All these methods have been implemented and tested

De nos jours, les plateformes portuaires cherchent à massifier leurs capacités de projection de conteneurs vers et à partir de leurs réseaux hinterland en misant sur les modes ferroviaires et fluviaux. Cela pour évacuer plus rapidement un volume quasi croissant de conteneurs livré par voie maritime et d’éviter les situations indésirables, tels que les situations d'asphyxie. De plus, les plateformes portuaires ont pris conscience que leur attractivité aux yeux des prestataires logistiques dépend non seulement de leur fiabilité et de leurs qualités nautiques mais également de leur capacité à offrir une desserte massifiée de leur hinterland. Contrairement à ce qui a pu être observé en Europe, la part du transport massifié a quasiment stagné au Havre dans les dernières années. A cet effet, le port du Havre a mis en place un terminal multimodal de conteneurs lié par rail et par voie navigable à un hinterland riche et dense en population (Bassin parisien, Marchés européens), et par des navettes ferroviaires aux autres terminaux maritimes du port Havre. L’intérêt économique et stratégique de ce nouveau terminal est de renforcer la position du Grand Port Maritime du Havre au niveau national, européen et mondial, et d’un point de vue écologique, diminuer l’utilisation excessive du routier en misant sur les modes moins polluants. Dans cette thèse, les efforts se focalisent sur la modélisation et la simulation du déroulement des opérations de manutention et d’allocation de ressources dans un terminal à conteneurs et particulièrement l’ordonnancement des portiques de manutention. Étant donné qu’un terminal à conteneurs est un système complexe, nous avons d’abord défini une démarche de modélisation qui facilite le processus de construction du modèle de simulation. Cette démarche est un processus itératif permettant de raffiner le modèle au fur et à mesure des étapes de développement réalisées. Les différentes étapes de développement sont liées par une série de diagrammes qui permet d’exprimer de façon claire les éléments et les relations formant le modèle de simulation. Ensuite, nous avons intégré dans notre modèle deux stratégies de non-croisement de portiques au niveau de la cour ferroviaire du terminal multimodal. Le but de ces stratégies est la minimisation des temps et des mouvements improductifs pour améliorer la performance et la productivité des portiques de manutention. La première stratégie est basée sur des règles de mouvement et sur la collaboration et coopération entre agents portiques. Tandis que la deuxième stratégie est basée sur une heuristique. Ces deux solutions ont été testées en utilisant l’outil de simulation AnyLogic et les résultats obtenus montrent la qualité de nos solutions. Concernant le problème d’ordonnancement des portiques de la cour fluviale, nous l’avons étudié en utilisant un couplage Optimisation-Simulation. Dans ce problème les temps de chargement et de déchargement de conteneurs et les temps de déplacement des portiques entre les baies sont considérés comme incertains. Le couplage est composé d’une méta-heuristique colonie de fourmis et d’un modèle de simulation à base d’agents. Chaque solution (une séquence de tâches) trouvée par l’algorithme d'optimisation est simulée et évaluée pour déterminer les nouvelles durées des tâches qui seront ensuite injectées comme données d’entrée de l’algorithme avant l’itération suivante
Nowadays, seaports seek to achieve a better massification share of their hinterland transport by promoting rail and river connections in order to more rapidly evacuate increasing container traffic shipped by sea and to avoid landside congestion. Furthermore, the attractiveness of a seaport to shipping enterprises depends not only on its reliability and nautical qualities but also on its massified hinterland connection capacity. Contrary to what has been observed in Europe, the massification share of Le Havre seaport has stagnated in recent years. To overcome this situation, Le Havre Port Authority is putting into service a multimodal hub terminal. This terminal is linked only with massified modes to a rich and dense geographical regions (Ile de France, Lyon), and with rail shuttles to the maritime terminals of Le Havre seaport. The aim of this new terminal is to restrict the intensive use of roads and to provide a river connection to its maritime terminals (MTs) that do not include a river connection from the beginning. In this study, we focus on the modeling and the simulation of container terminal operations (planning, scheduling, handling …) and particularly crane scheduling in operating areas. Designing multi-agents based simulation models for the operation management of a complex and dynamic system is often a laborious and tedious task, which requires the definition of a modeling approach in order to simplify the design process. In this way, we defined a top-down approach with several steps of specification, conception, implementation and verification-validation. This approach is an iterative process that allows the model to become more complex and more detailed. In this thesis, we pay more attention to crane scheduling problem in operating areas. For the rail-rail transshipment yard of the multimodal terminal, we designed two anti-collision strategies that aim to minimize unproductive times and moves to improve crane productivity and to speed up freight train processing. These strategies are tested using multi-method simulation software (Anylogic) and the simulation results reveal that our solutions are very satisfactory and outperform other existing solutions. With regard the fluvial yard, the stochastic version of crane scheduling problem is studied. The problem is solved with a mixed Optimization-Simulation approach, where the loading and unloading times of containers and travel times of cranes between bays are considered uncertain. The used approach is composed of an Ant Colony Optimization (ACO) metaheuristic coupled to an agent-based simulation model. Each solution (a tasks sequence) found by the optimization algorithm is simulated and evaluated to determine the new tasks’ periods which will then be injected as input to the ACO algorithm before the next iteration. The coupling is executed until the difference between the last iterations is too low

Dans ce travail de thèse, nous abordons les problèmes liés au partitionnement et à la distribution des grands volumes d’entrepôts de données distribués avec Mapreduce. Dans un premier temps, nous abordons le problème de la distribution des données. Dans ce cas, nous proposons une stratégie d’optimisation du placement des données, basée sur le principe de la colocalisation. L’objectif est d’optimiser les traitements lors de l’exécution des requêtes d’analyse à travers la définition d’un schéma de distribution intentionnelle des données permettant de réduire la quantité des données transférées entre les noeuds lors des traitements, plus précisément lors phase de tri (shuffle). Nous proposons dans un second temps une nouvelle démarche pour améliorer les performances du framework Hadoop, qui est l’implémentation standard du paradigme Mapreduce. Celle-ci se base sur deux principales techniques d’optimisation. La première consiste en un pré-partitionnement vertical des données entreposées, réduisant ainsi le nombre de colonnes dans chaque fragment. Ce partitionnement sera complété par la suite par un autre partitionnement d’Hadoop, qui est horizontal, appliqué par défaut. L’objectif dans ce cas est d’améliorer l’accès aux données à travers la réduction de la taille des différents blocs de données. La seconde technique permet, en capturant les affinités entre les attributs d’une charge de requêtes et ceux de l’entrepôt, de définir un placement efficace de ces blocs de données à travers les noeuds qui composent le cluster. Notre troisième proposition traite le problème de l’impact du changement de la charge de requêtes sur la stratégie de distribution des données. Du moment que cette dernière dépend étroitement des affinités des attributs des requêtes et de l’entrepôt. Nous avons proposé, à cet effet, une approche dynamique qui permet de prendre en considération les nouvelles requêtes d’analyse qui parviennent au système. Pour pouvoir intégrer l’aspect de "dynamicité", nous avons utilisé un système multi-agents (SMA) pour la gestion automatique et autonome des données entreposées, et cela, à travers la redéfinition des nouveaux schémas de distribution et de la redistribution des blocs de données. Enfin, pour valider nos contributions nous avons conduit un ensemble d’expérimentations pour évaluer nos différentes approches proposées dans ce manuscrit. Nous étudions l’impact du partitionnement et la distribution intentionnelle sur le chargement des données, l’exécution des requêtes d’analyses, la construction de cubes OLAP, ainsi que l’équilibrage de la charge (Load Balacing). Nous avons également défini un modèle de coût qui nous a permis d’évaluer et de valider la stratégie de partitionnement proposée dans ce travail
In this manuscript, we addressed the problems of data partitioning and distribution for large scale data warehouses distributed with MapReduce. First, we address the problem of data distribution. In this case, we propose a strategy to optimize data placement on distributed systems, based on the collocation principle. The objective is to optimize queries performances through the definition of an intentional data distribution schema of data to reduce the amount of data transferred between nodes during treatments, specifically during MapReduce’s shuffling phase. Secondly, we propose a new approach to improve data partitioning and placement in distributed file systems, especially Hadoop-based systems, which is the standard implementation of the MapReduce paradigm. The aim is to overcome the default data partitioning and placement policies which does not take any relational data characteristics into account. Our proposal proceeds according to two steps. Based on queries workload, it defines an efficient partitioning schema. After that, the system defines a data distribution schema that meets the best user’s needs, and this, by collocating data blocks on the same or closest nodes. The objective in this case is to optimize queries execution and parallel processing performances, by improving data access. Our third proposal addresses the problem of the workload dynamicity, since users analytical needs evolve through time. In this case, we propose the use of multi-agents systems (MAS) as an extension of our data partitioning and placement approach. Through autonomy and self-control that characterize MAS, we developed a platform that defines automatically new distribution schemas, as new queries appends to the system, and apply a data rebalancing according to this new schema. This allows offloading the system administrator of the burden of managing load balance, besides improving queries performances by adopting careful data partitioning and placement policies. Finally, to validate our contributions we conduct a set of experiments to evaluate our different approaches proposed in this manuscript. We study the impact of an intentional data partitioning and distribution on data warehouse loading phase, the execution of analytical queries, OLAP cubes construction, as well as load balancing. We also defined a cost model that allowed us to evaluate and validate the partitioning strategy proposed in this work

Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plusieurs backtracks simultanés venant de différents agents vers différentes destinations sont autorisés. En deuxième lieu, nous exploitons les caractéristiques intrinsèques du réseau de contraintes pour exécuter plusieurs processus de recherche AFC-ng d'une manière asynchrone à travers chaque branche du pseudo-arborescence obtenu à partir du graphe de contraintes dans l'algorithme Asynchronous Forward-Checking Tree (AFC-tree). Puis, nous proposons deux nouveaux algorithmes de recherche synchrones basés sur le même mécanisme que notre AFC-ng. Cependant, au lieu de maintenir le forward checking sur les agents non encore instanciés, nous proposons de maintenir la consistance d'arc. Ensuite, nous proposons Agile Asynchronous Backtracking (Agile-ABT), un algorithme de changement d'ordre asynchrone qui s'affranchit des restrictions habituelles des algorithmes de backtracking asynchrone. Puis, nous avons proposé une nouvelle méthode correcte pour comparer les ordres dans ABT_DO-Retro. Cette méthode détermine l'ordre le plus pertinent en comparant les indices des agents dès que les compteurs d'une position donnée dans le timestamp sont égaux. Finalement, nous présentons une nouvelle version entièrement restructurée de la plateforme DisChoco pour résoudre les problèmes de satisfaction et d'optimisation de contraintes distribués.