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.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/28302 |
| Date | 24 April 2018 |
| Creators | Kadri, Roubila Lilia |
| Contributors | Boctor, Fayez F., Renaud, Jacques |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | thèse de doctorat, COAR1_1::Texte::Thèse::Thèse de doctorat |
| Format | 1 ressource en ligne (xvi, 169 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0035 seconds