182 research outputs found
A note on the complexity of flow shop scheduling with transportation constraints
No full textInternational audienceThis note investigates two-machine flow shop scheduling with transportation constraints to minimize makespan. Recently, Soukhal et al. [A. Soukhal, A. Oulamara, P. Martineau, Complexity of flow shop scheduling problems with transportation constraints, European Journal of Operational Research 161 (2005) 32-41] proved that this problem is strongly NP-hard when the capacity of the truck is limited to two or three parts. The considered problem with blocking constraints is also proved to be strongly NP-hard by Soukhal et al. Unfortunately, their proofs contain mistakes. We point out their proofs' invalidity and then show that, when the capacity of the truck is limited to two parts, the problem is binary NP-hard, and when the capacity of the truck is limited to three parts the problem is strongly NP-hard even if the jobs have a common processing time on machine one and all jobs have the same transportation time. We show also that the last result can be generalized to any fixed c (c ⩾ 3) parts
A multicriteria sectorization problem in cartography
No full textInternational audienceThis is a summary of the author's Ph.D. thesis supervised by Vincent T'kindt and Ameur Soukhal, defended on November 28, 2012 at the University François Rabelais Tours, France. The thesis is written in French and is available from the author (tangx- [email protected]). The thesis has been prepared under the French Cifre Conventions with collaboration between the Laboratoire d'Informatique in Tours and the Articque Software Company in Fondette. This work deals with the solution of sectorization problems occurring in statistical cartography
No title available
No full textNous étudions des problèmes d'ordonnancement multiagent non disjoint. Ces modèles considèrent différents agents associés à des sous-ensembles de travaux non nécessairement disjoints, chacun d'eux vise à minimiser un objectif qui ne dépend que de ses propres travaux. Deux types de critères sont considérés : minimisation du makespan et du nombre de travaux en retard. NNous cherchons donc les meilleurs compromis entre les critères des agents. Ces problèmes sont une classe particulière des problèmes d'ordonnancement multi-agents qui ont connu une grande expansion par leurs intérêts dans le domaine de l'ordonnancement et l'optimisation combinatoire. Dans nostravaux, nous nous sommes intéressés aux problèmes à machines parallèles identiques. Dans une première partie, nous étudions le cas d'une seule machine et celui ou les travaux ont des durées identiques. Ainsi, des problèpmes polynomiaux sont identifités. Dans une seconde partie de nos travaux , nous abordons le problème à machine parallèles identiques avec deux agents..Notre étude porte surl'énumération du front de Pareto par l'approche e-contrainte en utilisant des modèles mathématiques à variables mixtes. Les résultats des expériemnetations montrent les limites de ces méthodes. Pour résoudre des problèmes de grande taille, des heuristiques gloutones, hybrides, des métaheuristiques ou encore matheuristique sont développées. Des expériemntations sont menées afin de montrer leur performances par rapport aux méthodes exactes ou par rapport à la borne inférieure proposée.We are studying non-disjoint multi-agent scheduling problems. These models consider different agents associated with non-disjoint subset of jobs, each of them aims to minimize an objective function that depends only on its own jobs. Two types of criteria are considered : minimization of the marketspan and minimization of the number of late jobs. We are therefore looking for the best compromise solution between the agents. These problems constitutes particular class of multiagent scheduling problems that have developped considerably due to their interests in scheduling and combinatorial optimization domains. In our work, we focused on problems with identical parallel machines. In a first part, we study the case of single machine, then the case wwhere the jobs are equal length. Thus, polynomial scheduling problems are identified. In a second part, we address the identical parallel machine schedulling problems with two agents.Our study focuses on the enumeration of the Pareto front by the e-constraint approach using mathematical miexed integer programming. The computational rsults show the limitations of these methods. To sole large instances, greedy heuristics, hybrid heuristics, metaheuristic or even matheuristic are developped. The computational results show their performance compared to exact methods or to be proposed lower bound
Exact and heuristic algorithms for fixed-interval multi-resource job scheduling problems in distributed systems : monocriterion and multiagent approaches
No full textLes 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
Multicriteria sectorization problems in cartography
No full textLes travaux présentés dans cette thèse visent à proposer des méthodes pour résoudre les problèmes de la sectorisation multicritère en cartographie. En premier temps, nous avons défini les problèmes différents de la sectorisation et nous avons établi les liens entre ces problèmes avec les problèmes classiques qui sont bien étudiés dans la littérature : le problème de découpage de district politique, les problèmes de localisation et le problème du partitionnement de graphe. Deux types de méthodes ont été abordés pour résoudre les problèmes de sectorisation. Des heuristiques ont été développées et elles consistent à calculer un optimum de Pareto pour les différents problèmes. Et pour le problème de sectorisation à partir de pôles, nous avons aussi utilisé et expérimenté un algorithme de boîte pour trouver une représentation du front de pareto. La méthode exacte branch and bound a été utilisée pour résoudre le problème de sectorisation sans pôle prédéfini optimalement. Avant que nous appliquons cette procédure, nous ajoutons quelques inégalités valides dans la formulation mathématique pour restreindre l'espace des solutions et nous développons une procédure de prétraitement pour réduire la taille du problème.The work presented in this thesis aims to propose methods to solve the multicriteria map sectorization problem in cartography. Firstlly, we have defined the different sectorization problems and we have established the links between these problems with some classical problems which are well studied in the literature : political districting problem, locationallocation problems and constrained graph partitioning problems. Two types of methods have been proposed to solve the sectorization problem. Heuristics have been developed and they compute an optimum Pareto for the different sectorization problems. And for the sectorization problem with predefined centers, we have used a box algorithm and experimented it to find a representation of the Pareto front. The branch and bound method was used to solve optimally the sectorization problem without predefined centers. Before we apply this procedure, we add some valid inequalities in the mathematical formulation for restrict the space of solutions and we develop a preprocessing procedure to reduce the size of the problem
Study and resolution methods for multi-skill projects scheduling problems : intégration à un progiciel intégrée libre
No full textLes travaux de cette thèse réalisée sous contrat CIFRE portent sur des problématiques d’ordonnancement de projets mufti-compétences. Définis en collaboration avec des experts de gestion de projet au sein de la société Néréide, deux modèles d’ordonnancement de projet font l’objet de cette étude. Dans le premier modèle, une tâche est définie par l’ensemble des compétences dont elle a besoin, la charge nécessaire de chaque compétence ainsi que la possibilité d’être interrompue ou non. Pour l’élaboration d’un planning prédictif respectant toutes les contraintes et minimisant la date de fin du projet, nous proposons des heuristiques de liste et métaheuristiques. Un modèle mathématique linéaire en nombres entiers ainsi que des bornes inférieures sont également développés. Dans un second temps, nous proposons, à partir d’un planning prédéfini, des méthodes pour ajuster le planning et répondre aux aléas survenus lors du déroulement du projet. Pour résoudre ce problème réactif, nous proposons une approche exacte itérative basée sur une formulation linéaire en nombres entiers ainsi qu’un algorithme génétique de type NSGA-II. Il s’agit donc d’une approche réactive bicritère où les solutions calculées doivent minimiser à la fois la date d’achèvement du projet et le nombre maximum de changements d’affectation de tâches aux employés. Dans le deuxième modèle, un cas particulier du modèle préemptif précédent est étudié. Nous nous intéressons au cas où une tâche nécessite une seule compétence avec possibilité de préemption seulement si les ressources ne sont pas disponibles (absence, congés, etc.). Dans ce modèle, une tâche est définie également par sa date de disponibilité et une date de fin souhaitée. Un coût d’utilisation personne/compétence est introduit. Pour ce dernier modèle, il s’agit d’un problème d’ordonnancement de projet bicritère, pour lequel les solutions calculées doivent minimiser le retard maximum et le coût global d’affectation des personnes aux tâches. Des heuristiques et métaheuristiques sont proposées pour ce modèle. Certaines méthodes de résolution proposées ont été implémentées sous forme d’add-ons intégrables au framework OFBiz.The work presented in this thesis deals with multi-skill project scheduling problems. We have studied two models of project scheduling which are defined in collaboration with project management experts in Néréide company. In the first model, a task is defined by a set of required skills, the load needed for each skill as welI as the possibility of preemption. To build a predictive planning which respects aIl problem constraints and minimize the project completion time (makespan), we propose heuristics and meta-heuristics methods. A mixed integer mathematical linear programming model and lower bounds are also proposed. From a predefined planning, we propose an exact method based on a mathematical program as weIl as a genetic algorithm of type NSGA-II allowing to deal with disruptions occurred during the project realization. It is, therefore, a reactive approach in which we look for feasible solutions minimizing both the project completion date and the maximum number of resources assignment changes. In the second studied model, we focus on a case where a task exactly requires one skill with preemption possibility only in case of resources unavailability. In this model, a task is also characterized by its release and due date. A cost per person/skill is given. It is, therefore, a bi-objective problem in which the computed solutions must minimize both the maximum tardiness and the project global cost. Heuristics and meta-heuristics are proposed for solving this problem. Some proposed methods are integrated in the framework OFBiz as add-ons
Complexity and algorithms for multicriteria scheduling of independent jobs : just-in-time scheduling and interfering jobs scheduling
No full textNous abordons dans cette thèse deux types de problèmes d’ordonnancement sur une machine ou sur des machines parallèles : 1. les problèmes d’ordonnancement de type juste-à-temps : il s’agit de déterminer un ordonnancement de sorte que les travaux se terminent le plus près possible de leur date de fin souhaitée. On considère le cas où la date de fin souhaitée commune est connue et le cas où elle est à déterminer. De nouveaux algorithmes exacts sont proposés. Des schémas d’approximation sont élaborés. 2. les problèmes d’ordonnancements de travaux interférants : il s’agit de déterminer un ordonnancement qui permet d’optimiser un critère pour tous les travaux, sachant que la solution trouvée doit permettre également l’optimisation d’un autre critère défini uniquement sur un sous-ensemble des travaux. Il s’agit ici d’un nouveau problème d’ordonnancement multicritère, différent de la notion classique. Les approches considérées pour trouver une solution non dominée sont l’approche e-contrainte, la combinaison linéaire de critères et le goal programming. De nouveaux résultats de complexité sont montrés et des algorithmes exacts sont développés.In this thesis, we consider two kinds of scheduling problems on a single machine or on parallel machines : 1. just-in-time scheduling problems : it aims to determine a schedule so that a job completes as close as possible to its due date.We consider the case where the common due date is known and the case where the common due date has to be fixed. New exact algorithms based on greedy algorithms and dynamic programming are proposed. Approximation schemes are given. 2. scheduling problems with interfering jobs : the aim is to determine a schedule that optimizes a criterion for the whole set of jobs and so that the solution optimizes another objective only for a subset of jobs. It is here a new multi-criteria scheduling problem, different from the classical notion. The approaches considered for finding a non-dominated solution are the e-constraint approach, the linear combination of criteria and the goal programming approach. New complexity results are proposed and exact algorithms are developed
Exact and approximate algorithms for multi-agent scheduling problems on parallel machines
No full textLes travaux de cette thèse s’articulent autour des « problèmes d’ordonnancement multiagent avec une fonction objectif globale ». Ces modèles considèrent différents agents associés à des sous-ensembles de travaux disjoints, chacun d’eux vise à minimiser un objectif qui ne dépend que de ses propres travaux. Un critère global est aussi considéré, qui est appliqué à la totalité des travaux. La résolution de ces problèmes revient à trouver les meilleurs compromis entre les critères des agents et le critère global. Ces problèmes sont une classe particulière des problèmes d’ordonnancement « multi-agents » qui ont connu une grande expansion, reflétant leurs intérêts dans le domaine de l’ordonnancement.This thesis addresses the multi-agent scheduling problems with a global objective function. We consider the problems featured by various agents, each of which is associated with a distinct subset of jobs. Each agent aims at minimizing a certain objective function, which only operates on its assigned jobs. A global criterion associated with a global agent is applied on the whole set of the jobs. Solving these problems involves finding the best compromises between the requirements of agents and that of the global agent. These problems belong to a particular class of multi-criteria scheduling problems. Such a class has drawn a significant interest to researchers in the area of scheduling and operational research
Multiagent scheduling
No full textScheduling theory has received a growing interest since its origins in the second half of the 20th century. Developed initially for the study of scheduling problems with a single objective, the theory has been recently extended to problems involving multiple criteria. However, this extension has still left a gap between the classical multi-criteria approaches and some real-life problems in which not all jobs contribute to the evaluation of each criterion. In this book, we close this gap by presenting and developing multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. Several scenarios are introduced, depending on the definition and the intersection structure of the job subsets. Complexity results, approximation schemes, heuristics and exact algorithms are discussed for single-machine and parallel-machine scheduling environments. Definitions and algorithms are illustrated with the help of examples and figures
Ordonnancement simultané des moyens de transformation et de transport
No full textOn s'intéresse à la résolution des problèmes d'ordonnancement dans les Systèmes Flexibles de Production (SFP). L'établissement d'une typologie, de notations claires et non ambiguës des problèmes réellement présents dans les ateliers de production est nécessaire pour résoudre efficacement les problèmes. Dans la première partie de cette thèse, nous utilisons une technique pour identifier automatiquement et précisément les problèmes d'ordonnancement, avec un minimum d'hypothèses simplificatrices. Dans la deuxième partie, nous nous préoccupons de la résolution des problèmes identifiés. Certains sont connus pour être NP-difficiles, et pour les autres de nouveaux résultats de complexité sont proposés. Compte tenu de la taille des problèmes à résoudre, nous nous sommes intéressés aux méthodes de résolution approchées de type métaheuristiques. Les méthodes ont été implémentées et testées pour quelques ateliers. Finalement, l'ordonnancement obtenu est traduit directement en consignes de pilotage du système de production. Plusieurs exemples servent d'illustration tout au long de la thèse, en particulier : le flowshop robotisé, le flowshop hybride classique et le flowshop hybride avec recirculation et temps de préparation. L'ensemble de ce travail contribue au développement du logiciel OCEA (Outil de Comparaison et d'Elaboration d'Algorithmes) à différents niveaux : - dans le DeSAP (Description de la Structure d'un Atelier de Production), le problème d'ordonnancement présent dans l'atelier est identifié précisément de façon automatique, à partir de sa description iconique ; - la bibliothèque électronique des références bibliographiques LEBO est enrichie ; - nous apportons à la bibliothèque d'algorithmes de résolution LCA (Logiciel de Comparaison d'Algorithmes) nos propres algorithmes basés principalement sur des méthodes comme le Recuit Simulé, la Recherche Tabou, les Algorithmes Evolutionnaires ou encore les Algorithmes de Fourmis Artificielles.TOURS-BU Sciences Pharmacie (372612104) / SudocTOURS-Polytech'Informat.Product. (372612209) / SudocSudocFranceF
- …
