Dissertationen zum Thema „Ordonnancement de projet“

Dans cette thèse, nous traitons un problème d’ordonnancement de projet, dans lequel une équipe d’opérateurs doit accomplir un ensemble de tâches où chaque tâche est exécutée dans un ensemble de centres de travail. Une tâche peut avoir un ou plusieurs modes d’exécution et chaque mode est défini par une durée et une consommation pour chacune des ressources (humaine, centre de travail). Une solution de ce problème consiste à trouver la séquence de réalisation des tâches, les modes d’exécution et les opérateurs à affecter à chaque tâche, de sorte que la durée totale de l’ordonnancement soit minimisée. Notre démarche a été d'abord d'introduire brièvement la théorie de l'ordonnancement de projet, avant d'aborder les différentes méthodes de résolution relevées dans la littérature. Dans une seconde étape, nous avons discuté et proposé deux méthodes de résolution approchée. La première est constructive : dans un premier temps, quatre heuristiques sérielles et une heuristique parallèle fondée sur un algorithme de génération des combinaisons non-dominées, ont été proposées. Dans un second temps, un algorithme sériel basé sur une approche par insertion de tâches et une procédure d’amélioration locale, ont été conçus. La seconde approche de résolution est itérative : trois méthodes heuristiques sont étudiées et expérimentées, la Recherche Tabou et l’Algorithme Génétique ainsi qu'une hybridation de ces deux méthodes. L’apport original de cette thèse est de proposer une fonction de voisinage basée sur un algorithme de réinsertion de tâche optimale qui pourra servir de base pour de nouvelles approches de résolution
The scheduling problem under study may be viewed as an extension of the standard Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP) including Multi-Skilled Labor and will be called as MRCPSP-MS. This problem requires an integration of resource limitation, labor skills, and multiple possible execution modes for each task, and the objective is to minimize the overall project duration. Our approach was first to introduce briefly the project scheduling theory, then to address the different resolution procedures which have been reported in literature for the RCPSP problem. In a second step, we have discussed and proposed two constructive heuristics. The first one, is a parallel scheduling heuristic, called MMSH, which enumerates at each time decision all the non-dominated schedulable activity-mode combinations and schedule the one with the best performance. The second approach is serial heuristic which optimally insert activities one by one into a partial schedule. This shows that insertion techniques have great importance in solving RCPSP and its extensions. In the second step of the problem resolution, three metaheuristics are designed, namely, Tabu Search, Genetic Algorithm and the hybridization of these two methods. The effectiveness of the methods is demonstrated through extensive experimentation on different standard and new benchmarks instances and proves that our results are competitive

Cette thèse entre dans le cadre du projet Hélimaintenance ; un project labellisé par le pôle de compétitivité Français Aérospace-Valley, qui vise à construire un centre dédié à la maintenance des hélicoptères civils qui soit capable de lancer des travaux en R&D dans le domaine. Notre travail consiste à prendre en considération les incertitudes dans la planification et l'ordonnancement de projets et résoudre les problèmes Rough Cut Capacity Planning, Resource Leveling Problem et Resource Constraint Project Scheduling Problem sous incertitudes. L'incertitude est modélisée avec l'approche floue/possibiliste au lieu de l'approche stochastique ce qui est plus adéquat avec notre cas d'étude. Trois types de problèmes ont été définis dans cette étude à savoir le Fuzzy Rough Cut Capacity Problem (FRCCP), le Fuzzy Resource Leveling Problem (FRLP) et le Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). Un Algorithme Génétique et un Algorithme "Parallel SGS" sont proposés pour résoudre respectivement le FRLP et le FRCPSP et un Recuit Simulé est proposé pour résoudre le problème FRCCP.

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

Cette thèse porte sur la résolution multi-objectif du problème d’ordonnancement de projet avec contraintes de ressources. Après avoir dressé un état de l’art sur le problème, nous le résolvons dans un premier temps avec les approches exactes : la méthode à deux phases et la méthode de partitionnement parallèle. Face à un problème NP-difficile, les méthodes exactes ne permettent de résoudre que des instances de petites tailles. Par conséquent, les méthodes approchées sont mises en œuvre pour traiter les problèmes de plus grandes tailles. Les algorithmes génétiques sont d’abord adoptés pour résoudre notre problème. Au-delà des schémas de base, nous proposons d’améliorer les solutions par plusieurs hybridations. Une recherche locale avec la méthode de Mapping est appliquée pour une meilleure exploration de l’espace de recherche. Nous considérons ensuite un cas spécial où les décideurs souhaitent réduire le nombre de solutions afin de faciliter leur travail. Nous avons donc réalisé les pré-sélections vis-à-vis d’un ensemble de solutions de grande taille. Pour ce faire, plusieurs alternatives de dominance de Pareto sont intégrées. Ces règles de dominances sont implémentées dans les schémas des algorithmes génétiques classiques et hybridés avec des recherches locales. Les résultats montrent que les hybridations considérées permettent d’améliorer significativement les méthodes de base. Nos recherches dans le futur proche s’appuient sur la résolution des problèmes plus complexes et en relation avec les cas industriels au plus proches de la réalité
This thesis deals with the multi-objective Resource Constraint Project Scheduling Problem (RCPSP). After a specific literature review, we solve the problem with exact approaches in the first place: the Two Phases Method and the Parallel Partitioning Method. Due to the NP-hardness of the problem, the exact methods are only able to solve small instances. For this reason, we apply the approximated methods to deal with larger problems. The genetic algorithms are firstly adopted to solve large-scaled instances. Moreover, we propose to improve the basic scheme with several hybridizations. A local search with Mapping Method is applied for a better exploration of the solution space. Next, we consider a special case where the decision-makers wish to reduce the number of solutions. Thus, in this part of the thesis, we try to select the most interesting solutions among the whole non-dominated front. For this purpose, several dominance relationships are considered as alternatives of the Pareto dominance. These dominance rules are implemented in the basic genetic algorithm schemes, as well as those with local search. The results show that the considered hybridizations enhance highly the basic method results. Our future research will highlight more complex multi-objective RCPSP problems and the industrial application

L’objet de cette thèse est l’étude et la résolution d’un problème industriel de gestion de projet sous contraintes de ressources. Notre problème intègre des contraintes rencontrées dans des ateliers d’assemblage d’avions et essaie de se rapprocher des pratiques et des méthodes de travail dans ces ateliers. Nous introduisons les problèmes dits d’ordonnancement sous conditions d’admissibilité des modes. Nous caractérisons d’abord notre problème comme une nouvelle extension du problème RCPSP (Resource-Constrained Project Scheduling Problem). Ensuite, nous proposons pour le cas non préemptif, un modèle mathématique pour résoudre des instances de petites tailles. Ce modèle peut s’étendre au problème d’ordonnancement sous conditions d’admissibilité des modes sous réserve que les conditions d’admissibilité soient linéaires. Différentes formulations du modèle mathématique opèrent sur des problèmes relaxés et permettent d’obtenir des bornes inférieures pour le problème global (ou non relaxé). Nous présentons également notre générateur d’instances et les bornes inférieures utilisées. Enfin, nous présentons deux heuristiques et une métaheuristique pour la résolution de notre problème. Les méthodes proposées sont comparées avec une problématique de la littérature qui est proche de notre problème
We discuss the problem of project scheduling encountered in aircraft assembly workshop. The scheduling problem under study may be viewed as a new extension of the standard Ressource Constrained Project Scheduling Problem (RCPSP for short). We generalize the multi resource and multi mode RCPSP with resource flexibility by additionally including calendars, skill constraints, transfers resources and specifics constraints. A mathematical formulation, two heuristics and a metaheuristic are proposed to solve this strongly NP hard problem, and they are compared with some methods of the literature

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d'ordonnancement du projet multi-compétences (MSPSP). L'objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d'un projet, composé d'un ensemble d'activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu'il y a encore un certain nombre d'instances pour lesquelles l'optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique.

Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats montrent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. .
In this thesis, we studied two types of scheduling problems. The major part concerns the Resource-Constrained Project Scheduling Problem (RCPSP). The scheduling problem of handling operations in a warehouse of Crossdocking is also dealt. First, from models using mixed integer linear programming, we proposed two new formulations of this problem, using variables indexed by events. In one of them, we use a binary variable to mark the beginning of the performing of each activity and another variable to mark its end. In the second proposal, a single variable is used. It identifies events in which the activity starts or continues its performing. Overall, compared to other models in the literature on various types of instances, our proposals show more interesting results on the instances with long scheduling horizons containing activities with disparate durations. In particular, on the highly cumulative instances (basic characteristics of RCPSP) of these types of instances, they are the most efficient. We also treat the resolution of the extension of the RCPSP which consists in taking into account specific resources that can be consumed during the performing of each activity, but also produced in another quantity at the end of performing of each activity: it is the RCPSP with consumption and production of resources. To make a comparison between different experimental models, we proposed an adaptation of our event-based formulations, the discrete-time formulations of Pritsker and Christofides, and the flow-based continuous-time formulation (proposed by Artigues on basis of the work of Balas). Overall, the results show that our event-based formulations are most successful on many types of instances. Second, in one less extensive part, we proposed a branch-and-bound using some cuts based on the Pareto frontier for the resolution of the scheduling problem of handling operations in a warehouse of Crossdocking. The excellent results obtained, which had strengthened our questions about the non-proved complexity of this problem, have contributed to establish later that this problem is of polynomial complexity

Pour représenter les activités d'une entreprise, la structure projet est de plus en plus fréquemment rencontrée. Ces projets se partagent généralement des ressources humaines, matérielles et de sous-traitance. Cette thèse s'attache à étudier plus particulièrement un centre de décision dans son environnement immédiat, c'est-à-dire étudier la prise de décision locale dans l'ordonnancement d'un projet en tenant compte des interactions et des dépendances du projet avec les autres centres de décisions. Après avoir identifié les besoins industriels et effectué un état de l'art dans les domaines de la gestion de projet en univers certain et incertain et de l'ordonnancement multi-projet, nous avons choisi de nous intéresser à deux problèmes : la détection et l'explication des incohérences et des conflits (dans le but d'aider à leur résolution) et la gestion de l'incertitude. En effet, l'aspect dynamique du problème peut amener le décideur dans une situation où son ordonnancement n'est plus valable. Le décideur doit alors trouver un nouvel ordonnancement pour son projet. A ce niveau là, nous envisageons l'outil d'aide à la décision comme un outil de mise en évidence des conflits. L'outil suggère donc des voies de décision et/ou de négociation avec les autres projets. Nous avons ensuite étendu cette méthode de recherche des explications de l'incohérence aux problèmes d'ordonnancement de projet lorsque des données sont mal connues. Les éléments imprécis ou incertains sont représentés à l'aide d'ensembles flous. Ce travail sur des données incertaines nous a amené à nous intéresser au problème du PERT flou pour lequel nous avons proposé une méthode de résolution lorsque le graphe représentant le projet est série-parallèle, ainsi qu'une heuristique lorsqu'aucune hypothèse n'est faite sur la typologie du graphe. A partir du problème industriel dont s'inspirent ces travaux (le problème de gestion de l'intégration d'un satellite dans la division Assemblage, Intégration et Essais de la société Astrium), les composants du problème type ont été exhibés et ont servi à définir un ensemble de problèmes sur lesquels une maquette logiciel de l'outil d'aide (développée en C++) a été testée.

La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité.
La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.

Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe.

Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.

Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.
Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound.
Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

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

Pour répondre aux attentes de clients de plus en plus exigeants, les entreprises d'aujourd'hui doivent accroître leur compétitivité, leur productivité et leur réactivité. Pour répondre à ces exigences, la fonction ordonnancement se doit d'être plus réactive, plus performante et plus adaptée aux spécificités des compagnies. Parmi les différentes possibilités d'évolution de l'ordonnancement, la voie de l'ordonnancement interactif semble répondre à ces besoins, et parmi les approches possibles de l'interactivité, l'utilisation d'indicateurs permet au gestionnaire d'atelier de connaître toutes les données nécessaires à la mise au point d'un ordonnancement performant. Quatre types d'indicateurs ont été définis : - des indicateurs de contexte décrivant l'état général de l'atelier, - des indicateurs de diagnostic aidant à identifier les causes de problèmes courants, - des indicateurs d'action renseignant sur la pertinence et l'efficacité de l'utilisation des degrés de liberté, - des indicateurs de performance, évaluant les performances de l'ordonnancement par rapport aux objectifs de l'entreprise. Cette approche de l'ordonnancement interactif a été appliquée à deux problématiques actuelles. Des indicateurs spécifiques à ces deux problèmes ont été définis. La première application concerne la prise en compte dans l'ordonnancement de commandes incertaines, encore en cours de négociation. La deuxième application concerne la gestion des opérateurs de production à court terme, au niveau de l'ordonnancement. Un outil de construction de tableaux de bord mettant en oeuvre ces différents indicateurs a été réalisé dans le cadre d'un projet européen (le projet ASPIRE).

Dans ce travail de thèse, nous avons étudié deux types de problèmes d'ordonnancement. La majeure partie concerne le problème d'ordonnancement de projet à moyens limités (RCPSP). Le problème d'ordonnancement des opérations de manutention dans un entrepôt de transbordement ("crossdocking") est également traité avec une moindre importance. Dans une première partie (la plus étendue), nous abordons le RCPSP. À partir de modélisations utilisant la programmation linéaire en nombres entiers, nous avons proposé deux nouvelles formulations de ce problème, utilisant des variables indicées par des événements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le début de l'exécution de chaque activité et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisée. Elle identifie les événements après lesquels l'activité reste en cours ou débute son exécution. De façon générale, comparées à d'autres modèles de la littérature sur divers types d'instances, nos propositions affichent des résultats plus intéressants sur les instances contenant des activités aux durées disparates et associées à de longs horizons d'ordonnancement. En particulier, sur ces mêmes types d'instances mais hautement cumulatives (caractéristiques de base du RCPSP), elles sont également les plus performantes. Nous avons également abordé la résolution d'une extension du RCPSP consistant à prendre en compte des ressources particulières, qui peuvent être consommées en début d'exécution de chaque activité, mais aussi produites à leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison expérimentale entre différents modèles, nous avons proposé une adaptation de nos formulations basées événements, des formulations à temps discret de Pritsker et de Christofides, et de la formulation à temps continu basée sur les flots (proposé par Artigues sur la base des travaux de Balas). Globalement, les résultats mon trent que nos formulations basées événements obtiennent les meilleurs résultats sur bon nombre de types d'instances. Dans la seconde partie (plus réduite), nous avons également proposé un branch-and-bound utilisant des coupes basées sur la frontière de Pareto, pour la résolution du problème d'ordonnancement des opérations de manutention au sein d'un entrepôt de transbordement ("crossdocking"). Les excellents résultats obtenus ont renforcé nos interrogations sur la complexité non-prouvée de ce problème, et ont permis d'établir par la suite que le problème est de complexité polynomiale.

Notre thèse a pour but de proposer des méthodes de résolution exacte pour les problèmes à ressources cumulatives, dans le cas de la minimisation de la date d'achèvement du projet. En particulier, nous nous sommes intéressés à deux problèmes qui sont : le flow-shop hybride et le problème de gestion de projet à contraintes de ressources (ressource constrained project scheduling problem), noté par la suite r. C. P. S. P. Les résultats obtenus, qu'ils soient pratiques ou théoriques, au cours de cette thèse sont : - deux nouvelles méthodes de résolution exactes du flow-shop hybride. La première, dont le schéma de séparation non chronologique est original, permet de traiter des problèmes de taille importante. Une nouvelle borne basée sur des dates de disponibilité-machine est présentée. Deux techniques reposant sur l'énumération des solutions pour des sous-problèmes, ont permis d'améliorer les performances de la méthode. La seconde méthode pour la résolution exacte du flow-shop hybride, repose sur l'ajustement des dates de disponibilité et des durées de latence des taches en utilisant l'approche énergétique. Les méthodes ainsi conçues améliorent les résultats obtenus pour des problèmes n'ayant pas de centre goulet. - une nouvelle relaxation pour le problème cumulatif. À partir de celle-ci une formulation en programmation linéaire est déduite prenant en compte le fait que certains sous-ensembles de taches ne peuvent pas être exécutés simultanément sans violer la contrainte de ressource. Le programme linéaire dual peut être résolu paramétriquement pour des ressources de petite capacité. Une méthode de génération de ressources redondantes est également proposée. - un ensemble de bornes pour le r. C. P. S. P. Elles sont déduites de la relaxation obtenue pour le problème cumulatif et adaptées avec succès, sur certaines instances de type r. C. P. S. P. La technique de génération de ressources redondantes s'avère utile pour obtenir de bons résultats sur des jeux-test génèrés.

L’importance de gérer la crise provoquée par une catastrophe naturelle, et plus particulièrement par les inondations, nécessite le développement de systèmes d’évacuation efficaces. Un système d’évacuation efficace doit tenir compte de certaines contraintes, notamment celles liées au trafic sur le réseau, à l’accessibilité, aux ressources humaines nécessaires et aux équipements matériels (véhicules, points de rassemblent, etc ..). L’objectif principal de ce travail est d’apporter une assistance aux services techniques et aux forces de secours en termes d’accessibilité en proposant des itinéraires relatifs aux opérations de secours et d’évacuation des biens et des personnes. Nous considérons dans cette thèse, l’évacuation d’une zone urbaine de taille moyenne, exposée à l’aléa d’inondation. En cas d’inondation, la plupart des habitants seront évacués en utilisant leurs propres véhicules. Deux sites d’étude sont sélectionnés dans le projet ACCELL 1, val de Tours (Fr, 37) et val de Gien (Fr, 45). Protégé de l’aléa d’inondation par un ensemble de digues, le site du val de Tours est doté d’un système de prévision de crues fournie par le SPC 2 (DREAL 3) et le SCHAPI 4 permettant aux décideurs d’anticiper une crise majeure par une évacuation préventive. Contrairement au site tourangeau, le val de Gien peut bénéficier d’une évacuation de la population avant et pendant la catastrophe. L’inondation sur ce second val est du type lente par débordement (site partiellement digué), les coupures de routes au cours du temps sont prises en compte lors d’une évacuation pendant la crise. Notre objectif est de construire, pour chacun de ces deux sites, un plan d’évacuation, i.e., fixer pour chaque individu la date de départ et le chemin pour atteindre le point de rassemblement associé. Le plan d’évacuation doit éviter la congestion sur le réseau routier. Nous présentons ici un modèle d’optimisation spatio-temporel (STOM5) dédié à l’évacuation de la population exposée à une catastrophe naturelle et plus particulièrement à un risque d’inondation
The importance of managing an urban site threatened or affected by flooding requires the development of effective evacuation systems. An effective evacuation system has to take into account some constraints such as the transportation traffic which plays an important role as well as others such as the accessibility, necessary human resources and material equipment (vehicles, assembly points, etc...). The main objective of this work is to bring assistance to the technical services and brigade forces in terms of accessibility by providing itineraries with respect to rescue operations and the evacuation of people and goods.We consider the evacuation of a middle size area, exposed to a risk, and more precisely to a risk of flooding. In case of flooding event, the most of inhabitants will be evacuated by themselves, ie., using their personal vehicles. Considered case here, the flooding can be forecast in advance, and then the population has few days (2-4) to evacuate. Our aimis to build an evacuation plan, ie., fixing for each individual the date of departure and the path to reach the assembly point (also called shelter) associated. Evacuation plan must avoid congestion on the roads of evacuation network.Here, we present a spatio-temporal optimization model for the evacuation of the population exposed to natural disasters, and more particularly to a flood risk

La plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamique
This thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem

Si les données d'un problème d'optimisation combinatoire changent, une solution initiale peut devenir sous-optimale ou infaisable. Il est alors nécessaire de calculer une nouvelle solution, mais aussi souhaitable de maintenir les décisions prises dans la solution initiale. Dans cette thèse nous proposons le critère d'ancrage pour favoriser les décisions inchangées entre solutions. En réoptimisation, il s'agit de trouver une solution conservant un nombre maximal de décisions d'une solution initiale. En optimisation robuste à deux étapes, nous proposons l'approche robuste-ancrée, qui consiste à calculer en avance une solution baseline et un sous-ensemble de décisions dites ancrées. Pour toute réalisation des données dans l'ensemble d'incertitude considéré, on peut réparer la solution baseline en une nouvelle solution sans changer les décisions ancrées. Cette approche permet un compromis entre le coût de la solution et les garanties sur les décisions. Les problèmes d'ancrage sont formalisés et déclinés sur deux classes de problèmes. La première est celle des programmes linéaires en variables binaires, et notamment des problèmes polynomiaux classiques comme l'arbre couvrant. La deuxième est celle des problèmes d'ordonnancement de projet, où des tâches doivent être ordonnancées sous des contraintes de précédences ou de ressources. La complexité algorithmique des problèmes d'ancrage est analysée. Les propriétés combinatoires des solutions ancrées sont étudiées, et permettent la conception d'approches algorithmiques et polyédrales dédiées. Des techniques de programmation linéaire en nombres entiers sont mises en œuvre, démontrant l'implémentabilité des problèmes d'ancrage
If the instance of an optimization problem changes, an initial solution may become suboptimal or infeasible. It is then necessary to compute a new solution, but it is also desirable to keep some decisions from the initial solution unchanged. In this thesis we propose the anchoring criterion to favor unchanged decisions between solutions. In a reoptimization setting, the goal is to find a new solution while keeping a maximum number of decisions from the initial solution. In a robust 2-stage optimization setting, we propose the anchor-robust approach to compute in advance a baseline solution, along with a subset of so-called anchored decisions. For any realization in the considered uncertainty set, it is possible to repair the baseline solution into a new solution without changing anchored decisions. The anchor-robust approach allows for a trade-off between the cost of a solution and guaranteed decisions. Anchoring problems are formally defined and studied on two problem classes. The first one is the class of integer programs in binary variables, including classical polynomial problems such as spanning trees. The second one is project scheduling, where jobs must be scheduled under precedence only, or precedence and resource constraints. The complexity of anchoring problems is analyzed. Combinatorial properties of anchored solutions are exhibited, and dedicated algorithmic and polyhedral approaches are devised. Mixed-integer programming techniques are investigated, that highlight the practical implementability of anchoring problems

De nos jours, pour maîtriser la complexité structurelle et fonctionnelle associées à la conception et au développement d'un système complexe tel qu'un avion, les entreprises mettent en place des organisations elles aussi complexes, à la fois hiérarchisées et distribuées. Ainsi le développement du système est confié à différentes équipes provenant d'entreprises aux métiers différents mais complémentaires. Ces équipes fonctionnent en ingénierie concourante et doivent se coordonner lors de la conception (échanges de résultats intermédiaires concernant des sous-systèmes à différents niveaux de maturité) et lors de l'intégration (travail en " plateaux "). Ce travail se focalise plus particulièrement sur le pilotage des activités d'ingénierie au sein d'une équipe, compte tenu de contraintes globales sur les ressources (nombres de personnes allouées) et sur les délais (fenêtres temporelles des activités), mais aussi compte tenu des contraintes de synchronisation que traduisent l'interdépendance des équipes. L'originalité de ce travail est de proposer une caractérisation énergétique des activités et des contraintes qui les lient et de valider la cohérence des décisions de pilotage (avance ou retard des activités, allocation de ressources supplémentaires) par l'utilisation d'un outil rigoureux basé sur la programmation par contraintes. Les mécanismes de propagation de contraintes peuvent être utilisés pour valider différentes simulations afin de servir de références pour la renégociation de contraintes lorsque celle-ci devient obligatoire. Une première spécification des modes d'utilisation d'un outil d'aide à la décision est également proposée. Nous concluons sur les extensions du modèle et sur les travaux d'expérimentation et de validation qui doivent prolonger ce travail afin de parvenir à un outil opérationnel diffusable à l'ensemble des équipes partenaires d'un projet de développement d'un système complexe.

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d’ordonnancement du projet multi-compétences (MSPSP). L’objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d’un projet, composé d’un ensemble d’activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu’il y a encore un certain nombre d’instances pour lesquelles l’optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique
In this Phd Thesis we introduce several procedures to solve the Multi-Skill Project Scheduling Problem (MSPSP). The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. Precedence relations and resource constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Furthermore, we give a particula rimportance to exact methods for solving the Multi-Skill Project Scheduling Problem (MSPSP), since there are still several instances for which optimality is still to be proven. Nevertheless, with the purpose of solving big sized instances we also developed and implemented a heuristic approach

Afin de résoudre de manière efficace des problèmes d'ordonnancement (de type disjonctif) NP-difficiles, nous avons conçu une famille de méthodes hybrides intégrant des algorithmes génétiques dans des méthodes classiques de recherche opérationnelle (procédure par séparation et évaluation ou PSE). Un nouveau codage direct (à tout chromosome correspond une et une seule solution du problème) ternaire (et non pas binaire) sert de structure de données à toutes les méthodes utilisées. De nouveaux operateurs génétiques définis sur ce codage permettent de conserver des sous-ensembles de contraintes de précédence imposés par la PSE ou par des propriétés de dominance. Ces nouveaux concepts ont été implémentés de manière différente sur un problème d'ordonnancement de projet avec des ressources existant en un seul exemplaire (minimisation de la durée totale) et sur le problème de base à une machine pour la minimisation de la somme des retards. Par ailleurs, nous avons étudié la conservation des (bons) schémas symboliques pour les problèmes de permutation de manière analytique et expérimentale (espérance mathématique d'indicateurs de performance appliqués à des croisements génétiques), ceci afin d'améliorer les performances de l'algorithme génétique par le bon choix de ses opérateurs internes.

Les nouvelles formes de projet, les projets d'innovation par exemple, demandent une prise de risque de plus en plus grande qui se traduit par le besoin de gestion des informations incertaines et des processus complexes et mal connus. Or une mauvaise gestoin de ce risque conduit très souvent à des conséquences graves pour la poursuite du projet le modele RAIH (Réseau d'Activités Incertaines Hiérarchisées) est une réponse en terme de modélisation et de planification de projets complexes. Il propose un cadre formel de modélisation des activités et de leurs compositions. Cette approche repose sur la formulation initiale proposée par le modèle GAN (Gereralized activity network - ELM77). Nous l'enrichissons d'une sémantique liée à la notion d'incertitude d'une structuration hiérarchique et de règles de réduction adaptées. En sus de cet outil de modélisation graphique et formel. Le modèle RAIH intègre une démarche de modélisation dont le but est de permettre la définition d'un projet en terme d'organisation humaine et technique. Une collection d'indicateurs calculés permet aux décideurs de prévoir la probable configuration du projet à une date et de définir un ensemble de dates cruciales. L'introduction des contraintes de ressources dans le modèle RAIH est ensuite le problème central. Nous devons simplifier le problume, par relaxation de certaines contraintes induites par le modèle, pour permettre la planification. On introduit alors la notion de scenario. L'introduction de décalages temporiels et le calcul de la probabilité de conflit à l'instant autorisent finalement le développement d'une première méthode de résolution supportée par une procédure par séparation et évaluation et un algorithme génétique. Un environnemnt informatique réparti reposant sur le concept de client/serveur temps reel supporte l'ensemble du modèle et fournit un environnement operationnel.

Ce travail concerne la decomposition temporelle du probleme d'ordonnancement a une machine avec contraintes de dates limites. Deux approches differentes sont proposees. La premiere s'inscrit dans un contexte de caracterisation des solutions admissibles vis-a-vis du respect des contraintes de temps et de ressources. Elle s'appuie sur la deduction de conditions d'admissibilite temporelles et sequentielles, a l'aide de regles d'analyse sous contraintes. Les conditions d'admissibilite sequentielles sont exprimees en associant a chaque tache un intervalle de rangs defini comme l'ensemble des positions non demontrees interdites dans une sequence admissible. Des principes d'agregation bases sur des comparaisons d'intervalles de rangs sont introduits ; ils permettent de regrouper les taches de localisation proche dans toute sequence admissible. Les conditions d'admissibilite mises en evidence sont ensuite exploitees par une procedure de generation de solutions fondee sur le respect des intervalles de rangs et dediee au probleme a une machine. Dans le cadre de cette premiere approche, une extension au probleme du flow-shop est ebauchee. La seconde approche par decomposition observe une demarche plus classique de recherche d'une solution heuristique a un probleme d'optimisation combinatoire. Des techniques de classification des donnees sont utilisees pour decomposer l'ensemble des taches, en exploitant d'eventuelles zones de faibles couplages entre les intervalles de temps que definissent les dates limites. Une procedure de gestion des liens residuels entre les groupes ainsi constitues est proposee ; elle construit des sous-problemes a partir de la partition de l'ensemble des taches, ordonnance chacun d'eux de facon optimale et forme une solution en coordonnant les ordonnancements locaux. Des resultats experimentaux relatifs a des problemes generes aleatoirement permettent d'evaluer les performances des deux approches, en confrontant leurs resultats a ceux obtenus par une methode de resolution exacte

De nos jours, pour maîtriser la complexité structurelle et fonctionnelle associées à la conception et au développement d’un système complexe tel qu’un avion, les entreprises mettent en place des organisations elles aussi complexes, à la fois hiérarchisées et distribuées. Ainsi le développement du système est confié à différentes équipes provenant d’entreprises aux métiers différents mais complémentaires. Ces équipes fonctionnent en ingénierie concourante et doivent se coordonner lors de la conception (échanges de résultats intermédiaires concernant des sous-systèmes à différents niveaux de maturité) et lors de l’intégration (travail en « plateaux »). Ce travail se focalise plus particulièrement sur le pilotage des activités d’ingénierie au sein d’une équipe, compte tenu de contraintes globales sur les ressources (nombres de personnes allouées) et sur les délais (fenêtres temporelles des activités), mais aussi compte tenu des contraintes de synchronisation que traduisent l’interdépendance des équipes. L’originalité de ce travail est de proposer une caractérisation énergétique des activités et des contraintes qui les lient et de valider la cohérence des décisions de pilotage (avance ou retard des activités, allocation de ressources supplémentaires) par l’utilisation d’un outil rigoureux basé sur la programmation par contraintes. Les mécanismes de propagation de contraintes peuvent être utilisés pour valider différentes simulations afin de servir de références pour la renégociation de contraintes lorsque celle-ci devient obligatoire. Une première spécification des modes d’utilisation d’un outil d’aide à la décision est également proposée. Nous concluons sur les extensions du modèle et sur les travaux d'expérimentation et de validation qui doivent prolonger ce travail afin de parvenir à un outil opérationnel diffusable à l’ensemble des équipes partenaires d’un projet de développement d’un système complexe
At the present time, in order to manage the functional and structural complexity associated with the design and development of a complex system such as an aircraft, companies put in place organisations that are themselves highly complex – both hierarchical and distributed. Thus, system development is outsourced to different teams from companies that are specialised in different, complementary areas. These teams work according to the principle of concurrent engineering and must coordinate their activities during the design phase (exchange of intermediary results concerning sub-systems at various levels of maturity) and the integration phase (working together on “plateaux”). The present study focuses primarily on the steering of engineering activities within a team, taking into account general constraints related to resources (number of people allocated) and lead times (time slots assigned to activities), as well as the synchronisation constraints inherent to interdependency between the teams. The originality of this study lies in the energetic characterisation it offers of the activities and the constraints that link them, and the fact that it validates the consistency of the steering decisions (activities brought forward or set back, allocation of additional resources) through a rigorous tool based on constraints programming. The constraints propagation devices can be used to validate different simulations in order to be used as a reference for the renegotiation of constraints when such renegotiation becomes mandatory. We also offer an initial specification of the operating procedure for a decision support system tool. We conclude by studying possible extensions of the model as well as the experimentation and validation work that must accompany this study in order to obtain an operational tool that can be circulated among all the teams that are partners in a complex system development project

Ce travail porte sur l'ordonnancement de tâches interdépendantes en présence de contraintes sur les ressources utilisées et sur les intervalles de temps alloués. Ces modèles sont l'extension de ceux résolus par les méthodes PERT et potentiels au cas où les tâches requièrent des ressources comme des machines ou du personnel. Bien que NP-difficiles, ils sont néanmoins d'un grand intérêt pratique. Ils interviennent en particulier pour la détermination des cycles de fabrication dans les ateliers, pour la gestion de projets, dans le cadre des télécommunications par satellite et plus généralement lors de la mise en place de SIAD. L'analyse bibliographique montre que leur résolution est basée sur des techniques d'optimisation combinatoire telles que les méthodes exactes ou approchées. Nous avons développé une méthode de type « Branch and Bound » avec un parcours SES ou SEP. Les résultats obtenus sont comparés, sur des benchmarks, à ceux de la littérature. Nous avons également testé une nouvelle heuristique qui permet la résolution de problèmes industriels. Ces techniques ont ensuite été appliquées au cas télématique du système européen de télécommunications par satellite utilisant la planification de trafic en AMRT/CNC et destiné à retransmettre les communications téléphoniques intra-européennes. La NP-difficulté de ce problème a été établie. Nous avons implémenté un logiciel graphique interactif comprenant une méthode sérielle dynamique répétitive qui procède par perturbations infinitésimales de la liste lexicographique. Ses performances sont analysées sur les prévisions de trafic des prochaines années. Les techniques développées sont très générales et leur application aux 2 ms d'une trame AMRT souligne leur universalité dans des domaines très variés.

Le problème de gestion de projet à contraintes de ressources est un des problèmesles plus étudiés dans la littérature. Il consiste à planifier des activités soumises à desrelations de précédence, et nécessitant des ressources renouvelables. L’objectif est deminimiser la durée du projet, soit le makespan. Nous étudions le problème de gestion deprojet à contraintes de ressources. Nous nous sommes intéressées à la résolution exactedu problème. Dans la première partie de la thèse, nous élaborons une série de bornesinférieures basées sur le raisonnement énergétique et des formulations mathématiques.Les résultats montrent que les bornes proposées surpassent ceux de la littérature. Dansla deuxième partie, nous proposons des procédures par séparation et évaluation utilisantles bornes inférieures dévelopées dans la première partie
Resource Constrained Project Scheduling Problem is one of the most studied schedulingproblems in the literature. It consists in scheduling activities, submitted to precedencerelationship, and requiring renewable resources to be processed. The objective isto minimize the project duration, i.e., the makespan. We study the Resource ConstrainedProject Scheduling Problem. We are interested on the exact resolution of the problem.In the first part of the thesis, we develop a series of lower bounds based on energeticreasoning and mathematical formulations. The computational results show that theproposed lower bounds outperform the ones of the literature. In the second part, wepropose Branch-and-Bound procedures using the lower bounds developed on the firstpart

Les 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

Le problème de gestion de projet sous contraintes de ressources (Resource Constrained Project Scheduling Problem) consiste en l'ordonnancement de tâches, également appelées activités, à l'aide d'une ou plusieurs ressources renouvelables ou non, en quantité limitée. Le but visé par la résolution de ce problème est la détermination des dates d'exécution des activités en fonction de la disponibilité des ressources et de façon à satisfaire des objectifs fixés. Les activités sont liées entre elles par des contraintes de préséance qui doivent être respectées lors de l'ordonnancement. Depuis plus de 30 ans, de nombreuses études ont été consacrées au RCPSP qui est un problème NP-difficile au sens fort. L'aspect pratique de ce problème dans des contextes industriels divers a conduit à de nombreuses recherches et ainsi à des résolutions par des méthodes heuristiques et métaheuristiques. Les algorithmes génétiques (AG) figurent parmi les métaheuristiques qui perforaient le mieux pour la résolution de ce problème. L'optimisation par essaims particulaire (OEP), quant à elle, est une méthode émergente qui intéresse de plus en plus de chercheurs dans le domaine de l'optimisation discrète et qui donne d'assez bons résultats. Ce mémoire propose une hybridation de ces.deux méthodes dans le but d'améliorer leurs performances individuelles sur des instances de taille moyenne. L'hybridation se fait au niveau du croisement en combinant deux méthodes de croisement, l'une étant le croisement classique à deux points largement répandu au sein de la littérature. La seconde méthode de croisement est nouvelle et se base sur un concept de distances entre deux solutions emprunté à un algorithme d'OEP de la littérature traitant du problème de minimisation du retard total pondéré sur une machine unique. Cet algorithme a d'abord été reproduit et adapté au RCPSP. La comparaison des performances obtenues avec celles des deux autres algorithmes d'OEP connus dans la littérature du RCPSP a été favorable à cette adaptation. Cela a donné lieu à la conception d'une méthode de croisement qui s'inspire des principes de l'OEP et du concept de distances pour générer de nouvelles solutions. Les performances observées lors de l'hybridation des deux méthodes de croisement ci-dessus énumérées montrent bien l'apport de cette technique innovatrice que constitue l'OEP discrète pour la résolution du RCPSP. Ce travail de recherche représente surtout une première exploration du potentiel offert par la technique de l'OEP et sa combinaison avec deux autres champs de recherche en évolution continue : le RCPSP et les AG. L'association de ces trois domaines de recherche laisse entrevoir des possibilités intéressantes pouvant mener à la conception de nouveaux algorithmes plus performants pour la résolution du RCPSP. Ce mémoire constitue une contribution non seulement vers une meilleure connaissance de l'OEP mais aussi vers l'amélioration des outils d'optimisation en gestion de projet.