Littérature scientifique sur le sujet « Ordonnancement de projet »

Résumé Les images d’utopie qui accompagnent L’Utopie de More et L’architecture considérée sous le rapport de l’art, des moeurs et de la législation, que Ledoux consacre au plan de la saline d’Arc-et-Senans, fonctionnent, au-delà de leurs singularités, comme des analogons (indices, icônes, symboles) de tensions internes au projet utopique. Ces tensions, qui font système, correspondent à des stylèmes de la pensée utopique : clôture/coupure d’avec le monde réel versus ouverture sur le monde extérieur ; ordonnancement totalisant/totalitaire versus pensée de la liberté par le fonctionnalisme ; monde fini versus monde ouvert. Seule la saisie de l’ensemble de ces tensions peut faire émerger un usage théorique et pratique anti-dogmatique de l’utopie, fidèle à la visée émancipatrice originelle.

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.